在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例:
3
1 2 3
输出样例:
3
思路:
将所有的数看成二进制,建一棵字典树,查询所有数在字典树中每个二进制位时尽量往相反位置走的结果,不断更新
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 5;
int a[maxn], tree[35*maxn][2];
int idx;
void build(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
//x>>i&1
//第i为是0还是1
//看一下x的二进制表示里面向右移(相当于去掉后i位)i位的个位是0还是1
//根据当前的点看看他的儿子是否存在
int &s = tree[p][x >> i & 1];
//如果不存在就创建一个新的节点
if (!s)
s = ++idx;
//当前节点向下移一位
p = s;
}
}
int solve(int x) {
int res = 0, p = 0;
for (int i = 30; i >= 0; i--) {
int s = x >> i & 1;
//看看和他不相同的节点是否存在
if (tree[p][!s]) {
res += 1 << i;
p = tree[p][!s];
}
//如果相同
else
//当前这一位贡献为0;
p = tree[p][s];
}
return res;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
build(a[i]);
}
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, solve(a[i]));
cout << ans << endl;
return 0;
}