ABC281F字典树01Trie

#include <stdio.h>
const int N=150005;
int n, m=2e9, p, c=1, i, j, k, d[N*32][2];
void trie(int p, int x){
    int i, j, k;
    for(i=29; i>=0; i--){
        k = (x & 1<<i) > 0;
        if(!d[p][k]) d[p][k] = ++c;
        p = d[p][k];
    }
}
void dfs(int p, int k, int s){
    int lc=d[p][0], rc=d[p][1];
    if(k < 0 && s < m) m = s;//到达叶子取最小值
    if(lc && rc){
        dfs(lc, k-1, s|1<<k);//左右均可选
        dfs(rc, k-1, s|1<<k);//两边选小的
    }//左右子树都有，无论x怎么选都会异或出1<<k
    else if(lc) dfs(lc, k-1, s);
    else if(rc) dfs(rc, k-1, s);
}//时间复杂度就是遍历这棵字典树
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        trie(1, k);//存入字典树
    }
    dfs(1, 29, 0);//从29次幂开始
    printf("%d\n", m);
    return 0;
}