AcWing 143. 最大异或对
原题链接
简单
作者:
橙外
,
2021-02-06 09:49:49
,
所有人可见
,
阅读 511
trie树问题: 把每一个数都转化为二进制,并且把每一位的数都用trie储存,找最大异或的话就尽量走与当前这位不同的数
异或 : 两位一样就为0,不一样就为1
题目描述
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010,M = 31 * N;
int a,n,cnt;
int son[M][2];
void insert(int x)
{
int root = 0; // 根节点
for (int i = 30; i >= 0; i--)
{
int now = x >> i & 1; // 找到这个数二进制第i位的数
if (!son[root][now]) son[root][now] = ++cnt; // 如果没有这个节点,就创造
root = son[root][now]; // 不断转化为子树的根节点
}
}
int find(int x)
{
int root = 0,ans = 0;
for (int i = 30; i >= 0; i--)
{
int now = x >> i & 1;
if (son[root][!now]) // 如果存在和当前这位不一样的子节点,就走这条路
{
root = son[root][!now];
ans = ans * 2 + 1; // 异或后,这一位就成1了
}
else // 只有一条不想走的路,只能走下去
{
root = son[root][now];
ans = ans * 2 + 0;
}
}
return ans;
}
int main()
{
cin >> n;
int ans = 0;
while ( n-- )
{
cin >> a;
insert(a);
ans = max(ans , find(a));
}
cout << ans;
return 0;
}