AcWing 143. 最大异或对
原题链接
简单
作者:
szywdwd
,
2021-05-21 17:35:55
,
所有人可见
,
阅读 291
#include <iostream>
using namespace std;
const int N = 100010, M = 3100010;
int son[M][2], idx;
int a[N];
void insert(int a) {
int p = 0;
for(int i = 30; i >= 0; --i) {
int u = a >> i & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
// 寻找字典树中所有值和a异或的值的最大值
int query(int a) {
int p = 0, res = 0;
// 非符号位的最高位必为0(小于2^31)
for(int i = 30; i >= 0; --i) {
int u = a >> i & 1;
// 某位相异时,异或值才为1,结果才尽可能大
if(son[p][!u]) {
res += 1 << i;// res加上相应值
p = son[p][!u];
}
else p = son[p][u];
}
return res;
}
int main()
{
int n, res = 0;
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i];
insert(a[i]);
}
for(int i = 0; i < n; ++i)
res = max(res, query(a[i]));
cout << res << endl;
return 0;
}