题目描述
最大异或对
根据所输入数字的二进制异或
求最大值,则转换为二进制为每个位与原来的数字二进制相反
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
//son[]存的是trie数一共有多少节点,存储的是N=100000个数,每个数循环31次,那就是31*100000=310w,因为会有复用的节点,用不上这么多,300w就可以了
const int M=3000000;
int son[M][2],idx; //idx依旧是节点的序号
int n;
int a[N]; //所取的数字
void insert(int x)
{
int p=0;
//当i=-1时,i的二进制全部都是1,~i即为0
for(int i=30;~i;i--) //题目中规定了 0≤Ai<2^31,所以循环到30 要从最高位开始比较才有意义,所以从30开始
{
//因为s的值需要被修改,加上引用符号之后,s的值改变时,son[][]的值也会改变
int &s=son[p][x>>i&1]; //x>>i右移i位,&1表示判断第i位是1还是0
if(!s) s=++idx; //如果左边没有结点,则在左边开辟一个节点
p=s;
}
}
int query(int x)
{
int p=0;
int res=0;
for(int i=30;~i;i--)
{
int s=x>>i&1;
if(son[p][!s]) //该位为0,则选择的数为1
{
res+=1<<i; //+1左移i位,逐渐恢复原来的数字
p=son[p][!s];
}
else
{
//res+=0<<i; //+0相当于没有操作
p=son[p][s];
}
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i],insert(a[i]);
int res=0;
for(int i=0;i<n;i++)
res=max(res,query(a[i]));
cout<<res;
return 0;
}