HDU 4825 Xor Sum (模板题)【01字典树】

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+5;
int n,m,pos;
ll val[N*32],nxt[N*32][2];

void init(){
    pos=1;
    memset(nxt,0,sizeof(nxt));
    memset(val,0,sizeof(val));
}
void Insert(ll x){    //用x的二进制建树
    int now=1;
    for(int i=32;i>=0;i--){     
        int to=(x>>i)&1;     //从最高位开始建
        if(!nxt[now][to])nxt[now][to]=++pos;
        now=nxt[now][to];
    }
    val[now]=x;      //标记前缀二进制串为完整的数字
}
ll query(ll x){   //寻找01Trie树上异或的最大数
    int now=1;
    for(int i=32;i>=0;i--){
        int to=(x>>i)&1;
        if(nxt[now][to^1])now=nxt[now][to^1];   //优先找与当前位不同的路线
        else now=nxt[now][to];    //如果没有的话，只能找相同的
    }
    return val[now];
}
int main(){
    int ncase=0;
    int T;scanf("%d",&T);while(T--){
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            ll cur;scanf("%lld",&cur);
            Insert(cur);
        }
        printf("Case #%d:\n",++ncase);
        for(int i=1;i<=m;i++){
            ll cur;scanf("%lld",&cur);
            printf("%lld\n",query(cur));
        }
    }
}