分析
找一个与 $a_i$ xor 最大的数,那就从最高位开始尽量不一样(0^1或者1^0)都是1,而相同则为0。
例如:
代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int n, son[31 * N][2], idx; // 每个数为31位,每位数为0或者1
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i--)
{
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int search(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i--)
{
int u = x >> i & 1;
if (son[p][!u]) p = son[p][!u], res = res * 2 + !u; //相当于<<1(左移一位),再加上一位数
else p = son[p][u], res = res * 2 + u;
}
return res;
}
int main()
{
cin >> n;
int res = 0; // 初始化最小为xor为0
for (int i = 0; i < n; i++)
{
int x; scanf("%d", &x);
insert(x);
res = max(res, x ^ search(x));
}
cout << res << endl;
return 0;
}
这图是哪本书的呀