异或每一位相同为0,不同为1,所以可以得到贪心的策略:对于u选择!u
将所有数存入字典树中,每次通过上面的贪心策略查找,即可找到最大值
1e5的数据范围,每个数31位,所以M=31*N
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=N*31;
int a[N];
int son[M][2],idx;
int n;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(son[p][!u]){
p=son[p][!u];
res+=1<<i;
}else{
p=son[p][u];
}
}
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++){
int t=query(a[i]);
res=max(res,t);
}
cout<<res<<endl;
}