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

<题目链接>

题目大意：

给定n个数，进行m次查找，每次查找输出n个数中与给定数异或结果最大的数。

解题分析：

01字典树模板题，01字典树在求解异或问题上十分高效。利用给定数据的二进制数进行建树，然后在查找的时候，利用贪心的策略，优先寻找与当前位数的0、1值不同的路线，从而达到异或值最大的目的。

#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:
",++ncase);
        for(int i=1;i<=m;i++){
            ll cur;scanf("%lld",&cur);
            printf("%lld
",query(cur));
        }
    }
}

2019-03-02