AcWing 143. 最大异或对+详细注释
原题链接
简单
作者:
邓汪涛
,
2021-01-21 17:20:17
,
所有人可见
,
阅读 693
trie树题解
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6+10;
int trie[maxn][2];
int tot;
void insert(int x)
{
int p=0;
for(int i=31;i>=0;--i)
{
int u = x>>i&1; // 取二进制数的从右到左第i位
if(!trie[p][u]) trie[p][u] = ++tot;
p=trie[p][u];
}
}
int query(int x)
{
int p=0;
int Xor=0;
for(int i=31;i>=0;--i)
{
int u = x>>i&1; //每次取二进制第从左到右第i位数
int cur; //先判断不存在的情况,如果当前trie树为空的话,就一直不存在与u相异的数,那么cur总是=u ,那么最后计算出的 Xor就是0
if(!trie[p][!u]) cur=u; //如果trie[p][!u]!=0 那么就是与当前位相异的数字是不存在的 那么cur就等于当前位
else cur=(!u); //否则 cur等于与当前位相异的数字
p=trie[p][cur];
Xor+= (1<<i)*(u^cur); //Xor += pow(2,i)*(u^cur)
}
return Xor;
}
int main()
{
std::ios::sync_with_stdio(false);
int n,x;
cin>>n;
int maxE = 0;
for(int i=0;i<n;++i)
{
cin>>x;
maxE = max(maxE , query(x)); //先查询 再判断 ,上面的query()方法在trie树为空时总是返回0
insert(x);
}
cout<<maxE<<endl;
return 0;
}