字典树

电玩女神 2022-07-15 10:16 147阅读 0赞

## 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

0  0

## Sample Output ##

题目大意：给你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;
    }

[Submit]: http://acm.ccniit.com/JudgeOnline/submitpage.php?cid=1255&pid=7&langmask=1012
[Status]: http://acm.ccniit.com/JudgeOnline/problemstatus.php?id=2509
[BBS]: http://acm.ccniit.com/JudgeOnline/phpbb.php?pid=2509&cid=1255