AcWing 143. 最大异或对
原题链接
简单
作者:
xyAC
,
2024-01-17 08:52:55
,
所有人可见
,
阅读 36
// 这题目主要是将每一个数字都成二进制数来存然后利用Trie树来存储每一个二进制数结点的分支只有两个就是0和1
// 然后依次判断 先存入再查找每一次查找的时候都是尽量找与当前数的二进制位相反的分支如果没有就将就着用现有的
// 那么最后就可以找到当前数异或后最大的数
//因为题目要求是在这些数中任意找两个所以为了避免重复只寻找当前数前面的数即可
// 最后就是时刻更新结果数返回即可
#include <bits/stdc++.h>
using namespace std;
// 最大结点数M
const int N = 100010,M = 31*N;
int a[M][2],n,idx;
// 插入就是判断当前的位数是否存在值
void insert(int x){
int q = 0;
for(int i = 30;i >= 0;i--) {
// 获取当前二进制位的数字
int u = x >> i & 1;
if(!a[q][u]) a[q][u] = ++idx;
q = a[q][u];
}
}
// 查找
int query(int x){
int q = 0,res = 0;
for(int i = 30;i >= 0;i--) {
int u = x>>i&1;
// 查找就是判断与当前相反的节点是否存在
// 如果存在就将根节点移动到当前节点
if(a[q][!u]) {
q = a[q][!u];
// 通过*2来获取当前的数 跟十进制*10 的原理一样然后再加上当前节点的值
res = res*2+!u;
}else{
q = a[q][u];
res = res*2+u;
}
}
return res;
}
int main(){
cin>>n;
int res = 0;
while(n--){
int x;
cin>>x;
insert(x);
int t = query(x);
res = max(t^x,res);
}
cout<<res<<endl;
return 0;
}