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+;

int n,m,pos;

ll val[N*],nxt[N*][];

void init(){

    pos=;

    memset(nxt,,sizeof(nxt));

    memset(val,,sizeof(val));

}

void Insert(ll x){    //用x的二进制建树

    int now=;

    for(int i=;i>=;i--){

        int to=(x>>i)&;     //从最高位开始建

        if(!nxt[now][to])nxt[now][to]=++pos;

        now=nxt[now][to];

    }

    val[now]=x;      //标记前缀二进制串为完整的数字

}

ll query(ll x){   //寻找01Trie树上异或的最大数

    int now=;

    for(int i=;i>=;i--){

        int to=(x>>i)&;

        if(nxt[now][to^])now=nxt[now][to^];   //优先找与当前位不同的路线

        else now=nxt[now][to];    //如果没有的话，只能找相同的

    }

    return val[now];

}

int main(){

    int ncase=;

    int T;scanf("%d",&T);while(T--){

        init();

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++){

            ll cur;scanf("%lld",&cur);

            Insert(cur);

        }

        printf("Case #%d:\n",++ncase);

        for(int i=;i<=m;i++){

            ll cur;scanf("%lld",&cur);

            printf("%lld\n",query(cur));

        }

    }

}

2019-03-02