HDU 4825 Xor Sum 【01字典树】

题目大意：

从一个N个数集合中找出一个数K，使得这个数与给出的S异或结果最大。

解题思路：

涉及到异或问题，将给的数都用二进制形式表示出来。为了使异或结果最大，即从高位开始选，K的这一位为1时选S的这一位为0的，为0时刚好相反。
然后用字典树进行存储分解后的二进制表示就OK了。

Mycode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX =100010;

int t, n, m;
long long x;
struct Trie
{
    int nex[MAX * 32][2], tot;
    long long pre[MAX * 32];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, 0, sizeof(pre));
    }
    void add()
    {
        int now = 1;
        for(int i = 32; i >= 0; --i)
        {
            if(nex[now][(x >> i) & 1] == 0)
                nex[now][(x >> i) & 1] = ++tot;
            now = nex[now][(x >> i) & 1];
        }
        pre[now] = x;
    }
    long long query()
    {
        int now = 1;
        for(int i = 32; i >= 0; --i)
        {
            if(nex[now][((x >> i) & 1) ^ 1])
                now = nex[now][((x >> i) & 1) ^ 1];
            else
                now = nex[now][(x >> i) & 1];
        }
        return pre[now];
    }
} trie;
int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        trie.init();
        printf("Case #%d:\n", cas);
        scanf("%d%d",&n,&m);
        while(n--)
        {
            scanf("%lld", &x);
            trie.add();
        }
        while(m--)
        {
            scanf("%lld", &x);
            printf("%lld\n", trie.query());
        }
    }
    return 0;
}