AcWing 143. 最大异或对
原题链接
简单
作者:
Winkel
,
2020-11-01 15:25:49
,
所有人可见
,
阅读 334
#include<iostream>
using namespace std;
const int N = 100010, M = 3100000;
int son[M][2], a[N], idx;
void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; i--)
{
int num = x >> i & 1; //得到x二进制形式第i位的数
if(!son[p][num]) son[p][num] = ++idx;
p = son[p][num];
}
}
// 查找与x异或后最大的数
int query(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i--)
{
int num = x >> i & 1; //得到当前位上的数
if(son[p][!num])
{
p = son[p][!num]; //1.判断是否存在与当前位上数字不同的结点,尽量找不同的使异或最大
res = res * 2 + !num; //更新res,先左移一位然后加上这一步经过的数
}
else
{
p = son[p][num]; //2.找不到,取与当前位相同的
res = res * 2 + num; //更新res
}
}
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int res = 0;
for(int i = 0; i < n; i++)
{
insert(a[i]);
int num = query(a[i]);
res = max(res, a[i] ^ num);
}
cout << res;
return 0;
}