Problem H: 位运算的游戏

Time Limit: 2 Sec   Memory Limit: 128 MB
Submit: 4   Solved: 2
[ Submit][ Status][ BBS]

Description

大家都知道位运算对于学计算机的人来说是很重要的，因为他运算效率最高。自从知道了这一点之后，毛毛雨就研究了一个游戏让自己练习位运算。游戏是这样的给你一个有N个整数的数组A，然后有Q中操作，每次操作给你一个整数X，让你求X和数组A中每个元素异或的最大值。现在毛毛雨正在出线段树的题，所以需要你们帮忙了，聪明的你们能帮他解决吗？

Input

每组数据第一行输入两个整数N和Q(0<=N,Q<=100000),第二行输入A(0<=A[i]<=1000000000)数组的N个整数。

当N和Q都等于0的时候结束输入。

Output

每组数据的每个询问输出一个整数(异或的最大值)，占一行。

Sample Input

10  5
1  2  3  4  5  6  7  8  9  10
1
2
3
4
5
0  0

Sample Output

11
11
11
14
15


题目大意：给你n个数，m个操作 给你一个数分别于这n个数异或找出最大的值并输出 


题目思路：这题最开始是在cf上看到的，，当时听了别人说用字典树，，然后仔细分析下，，确实可以用字典树，，字典树存每个数的二进制数，最多31位，因为要异或最大所以从最高位开始如果是0就要找1，是1就要找0，，如果找到就 ans|=(1<<i)  最后ans就是答案


AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
 
using namespace std;
 
struct trie{
    struct trie *Next[2];
    trie(){
       for(int i=0;i<2;i++)
         Next[i]=NULL;
    }
};
 
trie *head;
 
void BuildTrie(int str[]){
    trie *p = head;
    int id;
    for(int i=31;i>=0;i--){
        id = str[i];
        if(p->Next[id]==NULL){
            p->Next[id]= new trie;
        }
        p=p->Next[id];
    }
}
 
int QuarryTrie(int str[]){
    int id,ans=0;
    trie *p = head;
    for(int i=31;i>=0;i--){
        id = str[i];
        if(p->Next[id^1]){
            ans|=(1<<i);
            p=p->Next[id^1];
        }
        else {
            p=p->Next[id];
        }
    }
    return ans;
}
 
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)&&(n+m)){
        head = new trie;
        for(int i=0;i<n;i++){
            int x;scanf("%d",&x);
            int num[32],cnt=0;
            memset(num,0,sizeof(num));
            while(x){num[cnt++]=x%2;x>>=1;}
            BuildTrie(num);
        }
        while(m--){
            int x;scanf("%d",&x);
            int num[32],cnt=0;
            memset(num,0,sizeof(num));
            while(x){num[cnt++]=x%2;x>>=1;}
            printf("%d\n",QuarryTrie(num));
        }
 
    }
    return 0;
}