给定 n 个数,请选出两个数让它们的异或值最大,n≤106。
已知这道题是 Trie 树,思路没问题,但是后面 6 个点老是 RE 啊啊啊!求求了,悬关。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct Node{long long c; map <long long,int> p;} trie[N];
long long cnt=1,a[N]; string s[N];
void change(long long x,long long y) {
long long len=0;
while(x) {
a[++len]=x%2; x/=2;
}
for(int i=1;i<=len/2;i++) swap(a[i],a[len-i+1]);
for(int i=1;i<=32-len;i++) s[y]+='0';
for(int i=32-len+1;i<=32;i++) s[y]+=(a[i-(32-len)]+'0');
return;
}
void insert(string s) {
long long i=0,u=1;
while(s[i]) {
if(trie[u].p.count(s[i]))
u=trie[u].p[s[i++]];
else
trie[u].p[s[i++]]=++cnt,u=cnt;
++trie[u].c;
}
return;
}
long long ask(string s) {
long long i=0,u=1,sum=0,k=31;
while(s[i]) {
char op;
if(s[i]=='0') op='1';
else op='0';
if(trie[u].p.count(op))
u=trie[u].p[op],sum+=1<<k;
else
u=trie[u].p[s[i]];
i++,k--;
}
return sum;
}
int main() {
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
long long n,m,ans=0; cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
change(a[i],i),insert(s[i]);
}
for(int i=1;i<=n;i++) {
ans=max(ans,ask(s[i]));
}
cout<<ans;
return 0;
}