AcWing 143. 最大异或对
原题链接
简单
作者:
阿蹭
,
2024-12-18 18:39:55
,
所有人可见
,
阅读 1
可以用一个num数组存储数据,可以直接得出与这个数异或值最大的那个数。
#include <iostream>
using namespace std;
const int N = 100010, M = 3000000;
int n, a[N], num[M];
int son[M][2], idx;
int ans;
void insert(int x)
{
int p = 0;
for(int i = 30; ~i; i--)
{
int &s = son[p][x >> i & 1];
if(!s) s = ++idx;
p = s;
}
num[p] = x;
}
int query(int x)
{
int p = 0;
for(int i = 30; ~i; i--)
{
int s = x >> i & 1;
if(son[p][!s])p = son[p][!s];
else p = son[p][s];
}
return num[p];
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
insert(a[i]);
}
for(int i = 0; i < n; i++)
ans = max(ans, a[i] ^ query(a[i]));
printf("%d", ans);
}