HDU-4825-Xor Sum[사전 트 리]

HDU-4825-Xor Sum[사전 트 리]

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)

Problem Description Zeus 와 Prometheus 는 게임 을 했 습 니 다.Prometheus 는 Zeus 에 게 집합 을 주 었 습 니 다.집합 에는 N 개의 정수 가 포함 되 어 있 습 니 다.그 다음 에 Prometheus 는 Zeus 에 게 M 번 질문 을 할 것 입 니 다.매번 질문 에 정수 S 가 포함 되 어 있 습 니 다.그 다음 에 Zeus 는 집합 에서 정수 K 를 찾 아 K 와 S 의 차이 나 결 과 를 가장 크게 만들어 야 합 니 다.프로 메 테 우 스 는 제우스 에 게 인간 의 위대 함 을 보 여주 기 위해 제우스 가 인간 에 게 도움 을 청 할 수 있다 는 데 동의 했다.당신 은 인간 의 지혜 를 증명 할 수 있 습 니까?
Input 입력 은 여러 그룹의 테스트 데 이 터 를 포함 하고 각 그룹의 테스트 데 이 터 는 몇 줄 을 포함 합 니 다.입력 한 첫 줄 은 T 그룹 데이터 가 있 음 을 나타 내 는 정수 T(T<10)입 니 다.각 그룹의 데이터 의 첫 줄 에 두 개의 정수 N,M(<1=N,M<=100000)을 입력 하고 다음 줄 에는 N 개의 정수 가 포함 되 어 있 으 며 Zeus 가 얻 은 집합 을 대표 합 니 다.그 다음 에 M 줄 은 각 줄 의 정수 S 로 Prometheus 가 묻 는 정 수 를 대표 합 니 다.모든 정수 가 2^32 를 초과 하지 않 습 니 다.
출력 은 각 그룹의 데이터 에 대해 먼저 한 줄 의"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 3 Case #2: 4
제목 링크:HDU-4825
제목 대의:n 길이 의 서열 을 제시 하고 m 번 의 질문 을 하 며 매번 질문 할 때마다 숫자 S 를 제시 하고 n 서열 중의 한 값 K 와 S 가 다 르 거나 가장 큰 것 을 찾 습 니 다.
제목:누 드 사전 나무.

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
#define MAXN 4000005 
struct Trie  //   01Trie 
{
    int next[2];
    int flag,number;
    void ini()  //    
    {  
        next[0] = next[1] = 0;  
        flag = 0;  
    } 
}pnode[MAXN];
int root = 0;
int tot = 0;
void Insert(int num)
{
    int rt = root;
    for (int i = 30; i >= 0; i--)
    {
        int ret;
        if (num & (1 << i)) ret = 1; //   i  1  0 
        else ret = 0;
        if (!pnode[rt].next[ret]) //         
        {
            pnode[rt].next[ret] = ++tot;    //       ，           tot 
            pnode[tot].number = ret;    //tot        ret 
        }  
        rt = pnode[rt].next[ret];   //          
        pnode[rt].flag++;          
    }
} 

int Query(int num)
{
    int rt = root;
    for (int i = 30; i >= 0; i--)
    {
        int ret;
        if (num & (1 << i)) ret = 1;
        else ret = 0;
        if (ret == 1)   //   1，     0,0     1. 
        {
            int next_node = pnode[rt].next[0];
            if (pnode[next_node].flag > 0 && next_node) rt = pnode[rt].next[0];  //0  
            else
            {
                rt = pnode[rt].next[1];
                num ^= (1 << i);
            }   
        }
        else  //   0，     1,1     0. 
        {
            int next_node = pnode[rt].next[1];
            if (pnode[next_node].flag > 0 && next_node)  //1   
            {
                rt = pnode[rt].next[1];
                num ^= (1 << i);
            } 
            else rt = pnode[rt].next[0];
        }   
    }
    return num;
} 
int a[MAXN];
int cnt = 1;
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
    {
        for(int i = 0;i < tot;i++)   //    
        {  
            pnode[i].ini();  
        }
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
            Insert(a[i]);
        }
        printf("Case #%d:
",cnt++);
        while(m--)
        {
            int s;
            scanf("%d",&s);
            int ans = Query(s) ^ s;  //    ，    K   
            printf("%d
",ans); 
        }
    } 
    return 0;
}