three arrays （HDU - 6625，字典树 + 贪心）

一.题目链接：

HDU-6625

二.题目大意：

给两个长度为 n 的数组 a，b.

定义 c = a ^ b.

先让你变换 a，b 中元素的顺序，使得 c 的字典序最小.

三.分析：

看到第一眼就想到字典树了，可是有些地方不会写......

赛后发现其实不难，本质与这道题一样，就是麻烦了点.

我好菜啊..............

ps：用 memset TLE，必须边建树边初始化.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e5;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

int x;
int cnt[2];
struct node
{
    int cnt;
    int nx[2];
}trie[2][M * 32 + 5];

int ans[M + 5];

void init()
{
    cnt[0] = cnt[1] = 1;
    trie[0][1].nx[0] = trie[0][1].nx[1] = trie[0][1].cnt = 0;
    trie[1][1].nx[0] = trie[1][1].nx[1] = trie[1][1].cnt = 0;
}

void Insert(int idx, int x)
{
    int p = 1, v;
    for(int i = 29; i >= 0; --i)
    {
        v = (x>>i) & 1;
        if(!trie[idx][p].nx[v])
        {
            trie[idx][p].nx[v] = ++cnt[idx];
            trie[idx][cnt[idx]].nx[0] = trie[idx][cnt[idx]].nx[1] = trie[idx][cnt[idx]].cnt = 0;
        }
        p = trie[idx][p].nx[v];
        trie[idx][p].cnt++;
    }
}

int Query()
{
    int p1 = 1;
    int p2 = 1;
    int res = 0;
    for(int i = 29; i >= 0; --i)
    {
        if(trie[0][trie[0][p1].nx[0]].cnt && trie[1][trie[1][p2].nx[0]].cnt)
        {
            p1 = trie[0][p1].nx[0];
            p2 = trie[1][p2].nx[0];
            trie[0][p1].cnt--;
            trie[1][p2].cnt--;
        }
        else if(trie[0][trie[0][p1].nx[1]].cnt && trie[1][trie[1][p2].nx[1]].cnt)
        {
            p1 = trie[0][p1].nx[1];
            p2 = trie[1][p2].nx[1];
            trie[0][p1].cnt--;
            trie[1][p2].cnt--;
        }
        else if(trie[0][trie[0][p1].nx[0]].cnt && trie[1][trie[1][p2].nx[1]].cnt)
        {
            p1 = trie[0][p1].nx[0];
            p2 = trie[1][p2].nx[1];
            trie[0][p1].cnt--;
            trie[1][p2].cnt--;
            res |= (1<<i);
        }
        else if(trie[0][trie[0][p1].nx[1]].cnt && trie[1][trie[1][p2].nx[0]].cnt)
        {
            p1 = trie[0][p1].nx[1];
            p2 = trie[1][p2].nx[0];
            trie[0][p1].cnt--;
            trie[1][p2].cnt--;
            res |= (1<<i);
        }
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        init();
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &x);
            Insert(0, x);
        }
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &x);
            Insert(1, x);
        }
        for(int i = 0; i < n; ++i)
            ans[i] = Query();
        sort(ans, ans + n);
        for(int i = 0; i < n; ++i)
            printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}