AcWing 143. 最大异或对(Trie树解决)
原题链接
简单
作者:
小赵想滑板
,
2024-03-05 19:53:40
,
所有人可见
,
阅读 27
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=31*N;
int n;
int son[M][2],idx;
int a[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]){
res=res*2+1;
p=son[p][!u];}
else{
res=res*2;
p=son[p][u];}
}
return res;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int res=0;
for(int i =0;i<n;i++){
insert(a[i]);
res=max(res,query(a[i]));
}
cout<<res;
return 0;
}