Perfect Security【01字典树、Trie树】

  我只想说这道题难就难在翻译，读上去真的什么都读不懂，后来广寻名师，终于，在我的不懈努力下知道了真相。

  题意：题目给你N个数，第一排一串数组a[1]~a[N]，第二排也是一串数b[1]~b[N]，所要我们求的是这样的c[1]~c[N]为从a[1]开始一直找到a[N]的与{b[1] ~ b[N]}中异或的最小值，然后删除对应异或的b[i]，以此类推类推，求出{c}的全体。然后，用一个01字典树（Trie树）即可，具体实现看下面代码。

 

完整代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
using namespace std;
typedef long long ll;
const int maxN=300005;
struct node
{
    int cnt;
    node *child[2];
};
node *root;
int N;
int a[maxN];
void buildTree(int x)
{
    node *now=root;
    for(int i=31; i>=0; i--)
    {
        int exp=(x>>i)&1;
        if(now->child[exp]==NULL)
        {
            now->child[exp]=new node();
            //now->child[exp]->cnt=0;
        }
        now=now->child[exp];
        now->cnt++;
    }
}
int getsumoftree(int x)
{
    int cc=0;
    node *now=root;
    for(int i=31; i>=0; i--)
    {
        int exp=(x>>i)&1;
        if(now->child[exp]!=NULL && now->child[exp]->cnt)
        {
            now=now->child[exp];
            now->cnt--;
            cc+=exp<<i;
        }
        else
        {
            now=now->child[!exp];
            now->cnt--;
            cc+=(1-exp)<<i;
        }
    }
    return cc^x;
}
int main()
{
    while(scanf("%d",&N)!=EOF)
    {
        root=new node();
        //root->child[0]=NULL;
        //root->child[1]=NULL;
        memset(a, 0, sizeof(a));
        for(int i=1; i<=N; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1; i<=N; i++)
        {
            int e1;
            scanf("%d",&e1);
            buildTree(e1);
        }
        for(int i=1; i<=N; i++) printf("%d ",getsumoftree(a[i]));
        printf("\n");
        delete root;
    }
    return 0;
}