2014百度之星资格赛――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

Sample Output

Case #1:
4
3
Case #2:
4

Source 2014年百度之星程序设计大赛 - 资格赛
AC代码：暴力求解直接超时；所以选择字典树，依次对每一个比特位的XOR值进行选择，直至最后得出最优解；

#include
  
   
#include
   
     #include
    
      #define LL long long using namespace std; LL power[32]; typedef struct TrieNode { struct TrieNode *next[2]; }TrieNode; void Init(TrieNode **root) { *root=NULL; } TrieNode *CreateNode() { TrieNode *p; p=(TrieNode *)malloc(sizeof(TrieNode)); if(!p) { printf("No enough memory!\n"); exit(-1); } p->next[0]=NULL; p->next[1]=NULL; return p; } void InsertNode(TrieNode **root,LL data) { int i,k; TrieNode *p=*root; if(p==NULL) { p=*root=CreateNode(); } for(i=31;i>=0;i--) { if(data&power[i]) k=1; else k=0; if(p->next[k]==NULL) p->next[k]=CreateNode(); p=p->next[k]; } } LL Search(TrieNode *root,LL data) { LL ans=0; TrieNode *p=root; for(int i=31;i>=0;i--) { if(data&power[i])//the No.i bit is 1 { if(p->next[0])//to get the max xor value the same bit should p=p->next[0]; // be 0 if it exists else// if not exist ,then have to choose 1 { ans|=power[i]; p=p->next[1]; } } else//the No.i bit is 0,so we should choose 1 if it exits { if(p->next[1]) { ans|=power[i]; p=p->next[1]; } else p=p->next[0]; } } return ans; } int main(int argc,char *argv[]) { LL t,n,m; scanf("%I64d",&t); for(LL i=1;i<=t;i++) { TrieNode *root; power[0]=1; for(int j=1;j<=31;j++) power[j]=power[j-1]<<1; Init(&root); printf("Case #%I64d:\n",i); scanf("%I64d%I64d",&n,&m); while(n--) { LL data; scanf("%I64d",&data); InsertNode(&root,data); } while(m--) { LL s; scanf("%I64d",&s); printf("%I64d\n",Search(root,s)); } } return 0; }