AcWing 143. 最大异或对
原题链接
简单
作者:
aqbqlgh
,
2021-01-21 23:14:03
,
所有人可见
,
阅读 377
最大异或对 (贪心,字典树)
思路
- 给你一堆数想要求其中两个最大的异或值 可以思考贪心,只有高位异或为 1 值才大
- 可以使用字典树 将 n 个数,按从高位到低位存到字典树里
- 循环每次都查找在字典数中与本次a[i]从高位到低位相反最大 (即异或值最大)取个max
小技巧
- 可以用 res 存 本次异或的值 res = res * 2 + (x >> i & 1)
优化(相对于暴力循环)
- 每次循环先插入,再查找即可,a[i]与a[j]异或 与 a[j]与a[i]一样;所以只需查找当前字典树里有的就行
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int son[M][2], idx, a[N];
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 query(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;
}
else
{
p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
int res = 0;
for(int i = 0; i < n; i++)
{
insert(a[i]);
int t = query(a[i]);
res = max(res, a[i] ^ t);
}
cout << res << endl;
}