题目描述
在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
样例
输入样例:
3
1 2 3
输出样例:
3
看代码
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int p=10000010;
int son[p][2],idx;//son数组储存每个数的二进制数
//第一个p表示所有数的二进制数的个数,因为二进制只有1和0
//所有用2储存即可
int a[p];//a数组储存输入的数
void insert(int x)//建立每个数的二进制trie树
{
int p=0;
for(int i=30;~i;i--)//从最高位开始,~i等价于i>=0
{
int u=x>>i&1;//用u取得这个位置二进制的大小
if(!son[p][u]) son[p][u]=++idx;//如果这个点没有被访问,idx加1创建一个位置
p=son[p][u];//用p来连接每个点
}
}
int query(int x)//查询与x异或的最大值
{
int p=0,res=0;//res储存最大值
for(int i=30;~i;i--)//从最高位的二进制开始异或
{
int u=x>>i&1;
if(son[p][!u])//若这个点与x的二进制的这个点正好相反,则异或最大
{
res+=1<<i;//res加上1左移i位相当于这个二进制点转换为十进制
p=son[p][!u];//这个点存在,继续访问这个分叉的剩下的点看是否能异或最大值
}
else//如果找不到与这个点相反的点
{
res+=0<<i;//这一步可以省略,相加与于加个寂寞
p=son[p][u];//没找到这个点只能访问x分叉上的点
}
}
return res;
}
int main()
{
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}
for(int i=0;i<n;i++)
{
ans=max(ans,query(a[i]));
}
cout<<ans;
return 0;
}