AcWing 143. 最大异或对
原题链接
简单
作者:
Reliable
,
2024-01-25 22:05:05
,
所有人可见
,
阅读 34
C++ 代码
//2024-01-25 最满意的版本
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,son[31 * N][2],idx = 0;
int x[N],result = 0;
void insert(int x)
{
int p = 0;
for(int i = 30;~i;i--)
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x)
{
int p = 0 ,res = 0;
for(int i = 30 ; ~i ; i--)
{
int u = x >> i & 1;
if(son[p][!u])
{
p = son[p][!u];
res = res * 2 + !u;
}
else
{
p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
int main()
{
cin >> n;
for(int i = 0 ;i < n;i++)
{
cin >> x[i];
insert(x[i]);
}
for(int i = 0 ;i < n;i++)
{
int res = x[i] ^ query(x[i]);
result = max(res,result);
}
cout << result;
return 0;