链接
题意 : 给n个数 求x与a[i]异或的最大值最小
思路:每个数拆成2进制数建立一个trie树,在trie树上dp即可
难点主要是实现方面
对trie树建边的思想没有理解很到位
#include<bits/stdc++.h>
#define warn printf("!*!!*\n")
#define debug(x,c) cout<<string(c)<<":"<<x<<endl
using namespace std;
typedef long long L;
const int maxn=1e7+10;
const int oo=1e9+7;
const int mod=998244353;
int a[maxn],trie[maxn][2],tot=0;
void init()
{
for(int i=0;i<maxn;i++) trie[i][0]=trie[i][1]=-1;
}
int addedge(int x)
{
int num[50];
for(int i=30;i>=1;i--){
num[i]=x%2;x/=2;
}
int p=0;
for(int i=1;i<=30;i++){
int c=num[i];
//if(p==0&&c==1) cout<<i<<endl;
if(trie[p][c]==-1){
trie[p][c]=++tot;
}
p=trie[p][c];
}
}
int dfs(int x,int w,int dep)
{
if(dep>30) return 0;
int c=trie[x][0],v=trie[x][1];
//debug(c,"c");
//debug(v,"v");
//debug(dep,"dep");
//debug(dep,"dep");
// if(dep==28) cout<<c<<","<<v<<endl;
if(c!=-1&&v!=-1) {
int p=dfs(c,w/2,dep+1)+w;
int q=dfs(v,w/2,dep+1)+w;
return min(p,q);
}
else {
if(c==-1) return dfs(v,w/2,dep+1);
return dfs(c,w/2,dep+1);
}
}
int main()
{
int w=1<<29;
int n;scanf("%d",&n);
init();
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
addedge(a[i]);
}
printf("%d\n",dfs(0,w,1));
}