建出trie之后
考虑从根节点往下贪心考虑(高位到低位)
考虑节点要是分叉的情况我们序列中必然有数该位上为1
这样我们需要考虑往左往右走才是更优的
要是我们往左走了 就相当于可以不考虑右边的子树了 因为他们那边连高位的‘1’都没有显然不可能是最大值
要是不分叉我们就直接走就是了
然后考虑dp[u]:表示节点u子树包括的数异或后(ans)的最小值是什么
转移自然就只有三种 分叉一种 不分叉两种
分叉的话显然是左右两边的最小值+现在该位必为‘1’ dp[u]=min(dp[l],dp[r])+1<<(该位)
不分叉直接dp[u]=dp[]即可
C++ 代码
//郑老师和阿梓一样可爱^_^
#include <bits/stdc++.h>
using namespace std;
int n,idx,son[3000010][2],a[100010],dp[3000010];
void add(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
}
void dfs(int p,int now){
int l=son[p][0],r=son[p][1];
if(l)dfs(l,now-1);
if(r)dfs(r,now-1);
if(l&&!r)dp[p]+=dp[l];
else if(r&&!l)dp[p]+=dp[r];
else if(r&&l)dp[p]=min(dp[l],dp[r])+(1<<now);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
add(a[i]);
}
dfs(0,30);
cout<<dp[0]<<endl;
return 0;
}
男的见到lg写这么规范的代码,tql