AcWing 143. 最大异或对
原题链接
简单
作者:
一路向北_8
,
2025-01-16 20:14:56
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N], cst[N];
int son[N * 30][1], idx;
void Insert(int x)
{
int q = 0;
for(int i = 30; i >= 0 ; i --)
{
int u = x >> i & 1;
if(!son[q][u]) son[q][u] = ++ idx;
q = son[q][u];
}
cst[q] ++;
}
int Search(int x)
{
int q = 0, res = 0;
for(int i = 30; i >= 0; i --)
{
int u = x >> i & 1;
if(son[q][!u]){
res += 1 << i;
q = son[q][!u];
}
else{
q = son[q][u];
}
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
Insert(a[i]);
}
int r = 0;
for(int i = 0; i < n; i ++)
{
r = max(r, Search(a[i]));
}
printf("%d", r);
return 0;
}