解题思路
如果想要两个异或的值最多,最好就是两个数从二进制的高位到地位,尽可能的满足一个是1一个是0。把每个数都转换成31位二进制串的形式,然后存到trie树中。然后一个一个的枚举每一个数,在trie树中找尽可能可以异或出最大值的数。
代码
const int maxn = 1e5+10;
const int maxm = 3e6+10;
int a[maxn], trie[maxm][2], tot, n;
void insert(int num) {
int p = 0;
for (int i = 30; i>=0; --i) {
int t = num>>i&1;
if (!trie[p][t]) trie[p][t] = ++tot;
p = trie[p][t];
}
}
ll solve(int x) {
ll res = 0, p = 0;
for (int i = 30; i>=0; --i) {
res <<= 1;
int t = x>>i&1;
if (trie[p][t^1]) {
res |= 1;
p = trie[p][t^1];
}
else p = trie[p][t];
}
return res;
}
int main() {
scanf("%d",&n);
for (int i = 0; i<n; ++i) {
scanf("%d",&a[i]);
insert(a[i]);
}
ll res = 0;
for (int i = 0; i<n; ++i) res = max(res,solve(a[i]));
printf("%lld\n",res);
return 0;
}