923
字典樹-百度之星-Xor Sum
Xor Sum
Problem Description
Zeus 和 Prometheus 做了一個遊戲，Prometheus 給 Zeus 一個集合，集合中包含了N個正整數，隨後 Prometheus 將向 Zeus 發起M次詢問，每次詢問中包含一個正整數 S ，之後 Zeus 需要在集合當中找出一個正整數 K ，使得 K 與 S 的異或結果最大。Prometheus 為了讓 Zeus 看到人類的偉大，隨即同意 Zeus 可以向人類求助。你能證明人類的智慧麼？
Input
輸入包含若幹組測試數據，每組測試數據包含若幹行。輸入的第一行是一個整數T（T < 10），表示共有T組數據。每組數據的第一行輸入兩個正整數N，M（<1=N,M<=100000），接下來一行，包含N個正整數，代表 Zeus 的獲得的集合，之後M行，每行一個正整數S，代表 Prometheus 詢問的正整數。所有正整數均不超過2^32。
Output
對於每組數據，首先需要輸出單獨一行”Case #?:”，其中問號處應填入當前的數據組數，組數從1開始計算。對於每個詢問，輸出一個正整數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
吐槽：這個題目真爛，跟sum一點關係都沒有。
分析：暴力要超時，所以把每個數字轉換為長度為32的0-1字符串，用字典樹。因為其公共前綴的特性，空間上可以承受。因為是二叉樹，用node[SIZE][2]存放。不知道new速度是否會慢很多，所以沒用指針。
最後更新：2017-04-03 08:26:11