AcWing 143. 最大异或对
原题链接
简单
作者:
刘杰
,
2024-02-23 10:53:58
,
所有人可见
,
阅读 33
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10, M = 31 * N;
int n;
int a[N];
int ne[M][2], idx;
//形成字典树
void insert(int x){
int p = 0;
for(int i =30; i >=0; i--){
int u = x >> i & 1; //取第i位
if(!ne[p][u]) ne[p][u] = ++ idx;
p = ne[p][u];
}
}
//重点 查询
int query(int x){
int p =0, res = 0;
for(int i = 30; i >=0; i--){
int u = x >> i & 1; //取第i位
if(ne[p][!u]){ //另外一个方向存在
p = ne[p][!u];
res = res *2 + !u; //左移+ 最后一位
}
else{ //将就一下 同方向
p = ne[p][u];
res = res *2 + u; //左移+ 最后一位
}
}
return res;
}
int main(){
scanf("%d", &n);
for(int i =0; i < n; i++) scanf("%d", &a[i]);
int res = 0;
for(int i = 0; i < n; i++){
insert(a[i]);
//方便处理边界问题 保证非空
int t = query(a[i]);
//更新答案 t 即 a[i] 的最大异或数
res = max(res, a[i] ^ t);
}
printf("%d\n", res);
}