题目描述
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
样例
输入样例:
3
1 2 3
输出样例:
3
算法1
(暴力枚举) $O(n)$
会超时
C++ 代码
#include<bits/stdc++.h>//O(n)
using namespace std;
const int N=1e6+10;
int n,res;
int a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
res=max(res,i^j);
}
}
printf("%d\n",res);
return 0;
}
算法2 $O(nlogn)$
(Trie)
C++ 代码
#include<bits/stdc++.h>//O(nlogn)
using namespace std;
const int N=1e6+10;
int n,res,idx;
int a[N];
int son[N*31][2];
void insert(int x)
{
int p=0;
for(int j=30;j>=0;j--)
{
int u=x>>j&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x)
{
int p=0;
int ans=0;
for(int j=30;j>=0;j--)
{
int u=x>>j&1;
if(son[p][!u]) p=son[p][!u],ans+=1<<j;
else p=son[p][u];
}
return ans;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
insert(a[i]);
int t=query(a[i]);
res=max(res,t);
}
printf("%d\n",res);
return 0;
}