Xor SumTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 5864    Accepted Submission(s): 2557Problem DescriptionZeus 和 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 Input23 23 4 5154 14 6 5 63 Sample OutputCase #1:43Case #2:4 Source2014年百度之星程序设计大赛 - 资格赛  Recommendliuyiding

这道题是道字典树的题，是为什么呢？

首先看数据范围，字符集肯定是2，因为是异或

然后我们可以把每个数变成一个32位的二进制数（因为数据范围是2^32），然后插入到字典树里，然后查询时候尽量走和询问数那一位不一样的路径

最后累加就是答案；

怎么 把这个数二进制化呢，只要枚举第几位然后把这个数和1<<i位&一下就好了

这道题有一个东西

1<<0=1

1<<31=-2147483648

1<<32=0

这就很尴尬，因为这道题数据范围里可能会有三十二位

所以

1ll<<31=2147483648

1ll<<32=4294967296

这里加了一个ll，意味着告诉计算机这个1是个ll的类型

代码在此

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N 100011 5 using namespace std; 6 int t,n,m; 7 long long s; 8 long long num[N]; 9 int cnt=1;10 struct trie{11     int to[2],val;12 }tree[35*N];13 inline void cl(){cnt=1,memset(&tree,0,sizeof(tree));}14 inline int regist(){
   return cnt++;}15 void insert(long long now)16 {17     int rt=0;long long c;18     for(int i=32;i>=0;i--)19     {20         c=(1ll<
        
         =0;i--)31     {32         c=(1ll<