算法基本思想(字典树)
位运算可以存储二进制位,利用字典树
树中每个结点表示一个数的其中一个二进制,两个状态表示是0还是1
贪心的思想
要让一个数的异或值最大,从最高位开始,尽量往它相反的方向遍历
设当前数为x,x前面的数已经被我们存储到字典树中了,所以就直接可以遍历字典树,设当前数的其中一个二进制位为u,访问它的相反数位!u是否存在
如果存在,就加入!u,不存在,只能勉为其难加树中存在的数位,即u
答案更新
res=max(res,x^query(x))
其中res表示x与之前数异或的最大值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e5+10;
int p[N*31][2],idx;
//有N个树,每个数有31位,两个状态0,1
//31位的原因:A最大为2^31
int n;
int res;
void insert(int x)
{
int pp=0;
//取到第二位:右移1位然后与1,以此类推
for(int i=30;i>=0;i--)
{
int u=(x>>i)&1;
if(!p[pp][u]) p[pp][u]=++idx;
pp=p[pp][u];
}
}
int query(int x)
{
//算法的思想是经常往相反的数位走,存在相反数位就接受,没有只能勉为其难
int res=0;
int pp=0;
for(int i=30;i>=0;i--)
{
int u=(x>>i)&1;
if(!p[pp][!u])
{
//相反数位不存在,勉为其难
pp=p[pp][u];
res=res*2+u;
}
else
{
//存在相反数位,接受
pp=p[pp][!u];
res=res*2+!u;
}
}
return res;
}
int main()
{
cin>>n;
while (n -- )
{
int x;
scanf("%d", &x);
insert(x);
res=max(res,query(x)^x);
}
cout<<res<<endl;
return 0;
}