2014 百度之星 1003 題解 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

Case #2:

看起來非常easy的題目，由于使用暴力法的代碼非常easy，可是這道題使用暴力法逾時，是以就成為難題了。

題目應該使用Trie資料結構去解。并且是Trie的基本建構和搜尋了。

和一般的Trie不同，就是不用26個分支了，這裡僅僅有兩個分支，那麼就更加簡單了。

我一直都不太喜歡杭電的OJ。就是由于他們的輸入輸出感覺不夠智能。尾部多個換行符或者少個換行符都不成，一般OJ都無論這個推斷答案的了。

并且本題使用自家寫的IO也不行，浪費我不少時間。

我這道題是從高位到低位建構Trie的。也是從高位到低位搜尋。并且樹高是固定33. 搜尋效率接近常數.

以下是收拾過的代碼。帶上釋放記憶體，形成良好的程式設計習慣。