题意:在给定的(n)个整数(a_1,a_2,...,a_n)之中选出两个并进行异或运算,得到的最大结果是多少?(n<=1e5.a_i<2^{31}.)
把n个数转化成二进制数,看成长度为32的字符串,不足的前面补上0,插入(Trie)树中.然后对于每一个数,去(Trie)树中查询,尽量沿着相反的边走(即当前这个数的这一位为1,我要优先向0走),这样才能保证异或值最大.
(ch)数组要看大点.
本题是这题的弱化版.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1e7+5;
int tot=1,a[N],ch[N][2];
inline void insert(int x){
int u=1;
for(int i=31;i>=0;--i){
int c=(x&(1<<i))>>i;
if(!ch[u][c])ch[u][c]=++tot;
u=ch[u][c];
}
}
inline int query(int x){
int u=1,ans=0;
for(int i=31;i>=0;--i){
int c=(x&(1<<i))>>i;
if(ch[u][c^1])ans+=1<<i,u=ch[u][c^1];
else u=ch[u][c];
}
return ans;
}
int main(){
int n=read(),ans=0;
for(int i=1;i<=n;++i){
a[i]=read();
insert(a[i]);
}
for(int i=1;i<=n;++i)
ans=max(ans,query(a[i]));
printf("%d
",ans);
return 0;
}