AcWing 143. 最大异或对
原题链接
简单
作者:
术
,
2021-01-07 17:28:51
,
所有人可见
,
阅读 359
#include <iostream>
using namespace std;
const int M=3100005;//31*10e5
const int N=100005;
int son[M][2];
int cnt[M];//这里也是M 否则会sf
int a[N];
int idx;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){//从后往前
int t=x>>i&1;//从最高位开始取
if(!son[p][t]) son[p][t]=++idx;
p=son[p][t];
}
cnt[p]=x;
}
int search(int x){
int p=0,ans=0;
for(int i=30;i>=0;i--){
int t=x>>i&1;
if(son[p][!t]) {//每次往取反方向找
p=son[p][!t];
//ans+=1<<i;
}
else p=son[p][t];
}
return x^cnt[p];
//return ans;
}
int main()
{
int n;
cin>>n;
int res=0;
for(int i=0;i<n;i++){
cin>>a[i];
insert(a[i]);
}
for(int i=0;i<n;i++){
res=max(res,search(a[i]));
}
cout<<res;
return 0;
}