AcWing 143. 最大异或对
原题链接
简单
作者:
Value
,
2020-06-22 15:42:32
,
所有人可见
,
阅读 496
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1E5 + 10;
int son[N * 31][2], idx;
void insert(int t){
int u = 0;
for(int i = 30; i >= 0; i -- ){
int v = t >> i & 1;
if(!son[u][v]) son[u][v] = ++ idx;
u = son[u][v];
}
}
int query(int t){
int u = 0, res = 0;
for(int i = 30; i >= 0; i -- ){
int v = t >> i & 1;
if(son[u][!v]){
u = son[u][!v];
res = res * 2 + !v;
}else{
u = son[u][v];
res = res * 2 + v;
}
}
return res ^ t;
}
int main(){
int n, res = 0;
cin >> n;
int tmp;
for(int i = 0; i < n; i ++ ){
cin >> tmp;
insert(tmp);
res = max(query(tmp), res);
}
cout << res << endl;
return 0;
}