AcWing 143. 最大异或对
原题链接
简单
作者:
Yg_trece
,
2024-10-26 23:04:32
,
所有人可见
,
阅读 3
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int MAX_BITS = 30;
const int root = 0;
int trie[N * 31][2], idx = 1;
int nownum[32], nowp, ans;
void entrie(int x)
{
int i = MAX_BITS, p = root;
while (i >= 0)
{
int a = (x >> i) & 1;
if (!trie[p][a])
trie[p][a] = idx++;
p = trie[p][a];
i--;
}
}
void getans(){
int res = 0,p=root;
for (int i = 0; i < nowp;i++){
int a = trie[p][0], b = trie[p][1];
if(nownum[i]&&a){
res += 1 << (MAX_BITS - i);
p = a;
}else if(!nownum[i]&&b){
res += 1 << (MAX_BITS - i);
p = b;
}else
p = max(a, b);
}
ans = max(ans, res);
}
void dfs(int p)
{
if (nowp==31)
{
getans();
return;
}
int a = trie[p][0], b = trie[p][1];
if (a)
{
nownum[nowp++] = 0;
dfs(a);
nowp--;
}
if (b)
{
nownum[nowp++] = 1;
dfs(b);
nowp--;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n;
while (n--)
{
cin >> m;
entrie(m);
}
dfs(root);
cout << ans;
return 0;
}