abc--281--F

F - Xor Minimization

思路

感觉算是字典树的板子题了

先对每一个数进行按位分解，然后看这一位可以选择什么
如果这一位既有0，又有1，那么这一定是1
否则就可以为0，走为0的这条路就好了

代码

#include <bits/stdc++.h>
using namespace std;
const int M=1e5*5;

int ch[M*30][2],tot;
int dfs(int now,int dep) {
    if(dep==-1)return 0;
    if(ch[now][0]==0)return dfs(ch[now][1],dep-1);//这一位全部是1
    if(ch[now][1]==0)return dfs(ch[now][0],dep-1);//这一位全部是0
    return min(dfs(ch[now][0],dep-1),dfs(ch[now][1],dep-1))+(1<<dep);//这一位逃不掉，两个选一个小的就好了
}

int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int p=0;
        int x;cin>>x;
        for(int j=29;j>=0;j--) {
            int v=x>>j&1;
            if(ch[p][v]==0)ch[p][v]=++tot;
            p=ch[p][v];
        }
    }
    cout<<dfs(0,29)<<endl;
    return 0;
}