AcWing 143. 最大异或对
原题链接
简单
作者:
_如鲸向海
,
2022-05-28 19:46:07
,
所有人可见
,
阅读 142
C++ 代码
//每个数均用二进制去表示
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const int M = 3100010;
int idx;
int son[M][2];
int num[N];
void insert(int num){
int p = 0;
for(int i = 30;i>=0;i--){
int u = (num>>i)&1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int search(int num){
int p = 0;
int res = 0;
for(int i = 30;i>=0;i--){
int u = (num>>i)&1;
if(son[p][!u]){//这一层出现的情况是 0异或1或者1异或0
p = son[p][!u];
res = 2*res +1;
}
else{//1异或1 0异或0
p = son[p][u];
res = 2*res +0;
}
}
return res;
}
int main(){
int n;
int res = 0;
cin>>n;
for(int i = 0;i<n;i++){
cin>>num[i];
insert(num[i]);
}
for(int i = 0;i<n;i++)
res = max(res,search(num[i]));
cout<<res<<endl;
}