題目：

Problem Description
Zeus 和 Prometheus 做了一個游戲，Prometheus 給 Zeus 一個集合，集合中包含了N個正整數(shù)，隨后 Prometheus 將向 Zeus 發(fā)起M次詢問，每次詢問中包含一個正整數(shù) S ，之后 Zeus 需要在集合當(dāng)中找出一個正整數(shù) K ，使得 K 與 S 的異或結(jié)果最大。Prometheus 為了讓 Zeus 看到人類的偉大，隨即同意 Zeus 可以向人類求助。你能證明人類的智慧么？
Input
輸入包含若干組測試數(shù)據(jù)，每組測試數(shù)據(jù)包含若干行。
輸入的第一行是一個整數(shù)T（T < 10），表示共有T組數(shù)據(jù)。
每組數(shù)據(jù)的第一行輸入兩個正整數(shù)N，M（<1=N,M<=100000），接下來一行，包含N個正整數(shù)，代表 Zeus 的獲得的集合，之后M行，每行一個正整數(shù)S，代表 Prometheus 詢問的正整數(shù)。所有正整數(shù)均不超過2^32。
Output
對于每組數(shù)據(jù)，首先需要輸出單獨一行”Case #?:”，其中問號處應(yīng)填入當(dāng)前的數(shù)據(jù)組數(shù)，組數(shù)從1開始計算。
對于每個詢問，輸出一個正整數(shù)K，使得K與S異或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4

很明顯，直接暴力求該值與數(shù)組中的值的異或然后比較大小肯定過不了。
由于異或運算是位運算，因此這道題可以將這些數(shù)字轉(zhuǎn)換為二進制數(shù)，二進制數(shù)只有0或1，而異或出來的值如果為1，則它越靠近高位，最終異或的結(jié)果越大。因此，我們可以用字典樹維護。

異或是相同為0，不同為1，因此在對要查詢的數(shù)進行處理時，該位為1則變?yōu)?，該位為0則變?yōu)?.

高位不足則補0.
這道題雖然是字典樹，但是要處理的細(xì)節(jié)很多，這道題也不算簡單。

參考代碼：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
const int N = 100000+10;
typedef long long LL;

struct Trie {
    LL f;
    Trie *next[2];//0 and 1;
};

Trie *root;

int a[35];//保存數(shù)字轉(zhuǎn)換為二進制之后的每一位數(shù);

void change(LL num) {
    int i = 0;
    while (num) {
        a[i++] = num % 2;
        num = num / 2;
    }
} 

void createTrie(int a[]) {
    Trie *p = root, *q;
    int len = 34;//高位靠近樹根;
    while (len >= 0) {
        int id = a[len];
        if (p->next[id] == NULL) {
            q = new Trie();
            for (int i = 0;i < 2;++i) {
                q->next[i] = NULL;  
            }
            p->next[id] = q;
            p = p->next[id];
        }
        else {
            p = p->next[id];
        }
        if (id) p->f = (LL) (1) << len;//如果下標(biāo)為1, 表明該權(quán)重有值;
        --len;  
    }
}

LL findTrie(int a[]) {
    Trie *p = root;
    int len = 34;
    LL ans = 0;
    while (len >= 0) {
        int id = a[len];

        if (p->next[id] == NULL) {//所有的數(shù)字的二進制數(shù)都沒有以id值為最高位;
            id = id ^ 1;
        }

        p = p->next[id];
        if (id) {
            //cout << s.size() << " " << id << endl;
            ans += p->f;    
        }
        --len;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int cnt = 1;cnt <= t;++cnt) {
        root = new Trie();
        root->next[0] = NULL;
        root->next[1] = NULL;
        
        int n, m;
        cin >> n >> m;
        LL number;
        for (int i = 1;i <= n;++i) {
            cin >> number;
            memset(a, 0, sizeof(a));//初始化;
            change(number);
            createTrie(a);
        }
        
        int query;
        cout << "Case #" << cnt << ":" << endl;
        for (int i = 1;i <= m;++i) {
            cin >> query;
            memset(a, 0, sizeof(a));
            change(query);
            for (int i = 0;i < 35;++i) {
                a[i] = a[i] ^ 1;//轉(zhuǎn)換;//兩數(shù)異或, 不相同為1, 這里轉(zhuǎn)換后就變?yōu)橄嗤瑸?;
            }
            LL ans = findTrie(a);
            cout << ans << endl;
        }
        
        delete root;
    }
    return 0;
}