AcWing 143. 最大异或对
原题链接
简单
作者:
静态规划
,
2021-02-09 09:42:10
,
所有人可见
,
阅读 308
#include <iostream>
using namespace std;
const int N = 1e5+10, M = 3e6+10;
int son[M][2], a[N];
int idx, n;
void insert(int x) {
int p = 0;
for (int i = 30; ~i; i--) {
int s = x >> i & 1;
if (son[p][s] == 0) son[p][s] = ++ idx;
p = son[p][s];
}
}
int query(int x) {
int p = 0, sum = 0;
for (int i = 30; ~i; i--) {
int s = x >> i & 1;
if (son[p][!s]) { // 有这一位
sum += 1 << i;
p = son[p][!s];
}
else
p = son[p][s];
}
return sum;
}
int main () {
int 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(query(a[i]), res);
}
cout << res;
return 0;
}