题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6625

题目：

给出两个数组a和b，可以任意调整a和b中元素的位置，使得最后的c数组的字典序最小，c[i] = a[i] ^ b[i] 

 

解题思路：

先对a和b数组分别建立两棵01字典树，如图（省去了前面的很多位没有太大意义的0，此时max_base取3，因为最大的数才是3位的）：

<figcaption> a数组的01字典树 </figcaption>
<figcaption> b数组的01字典树 </figcaption>

 

01字典树从上到下（即从高位到低位）的每一行的值表示，在这一堆数中，存在该位上为0/1的数。

同时遍历这两个01字典树，每次都贪心的找该位上同为0，或者同为1的节点，依次为基准再分别向下遍历，让每一位上都尽量同为0或者同为1，这样该位异或的时候才能得到0。若不存在该位上同为0或者1的情况，那么这一位就没法在a和b数组中找到两个数使得这一位的异或结果为0，那么就要更新答案。

一共要遍历n次，每次找到两个数使得他们的异或值是最小的，然后在01字典树上“删除”这了两个数（可在遍历的时候完成）

讲的有点啰嗦，参照代码和图模拟一遍就很清楚啦。

 

ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int max_base = 30;
int  ans[maxn];
struct node{
    int ch[32*maxn][2];
    int num[32*maxn];
}tree[2]; //两棵01字典树,不要忘记*32！！
int tol = 0;
void init(int type)
{
    tol = 1;
    tree[type].ch[0][0] = tree[type].ch[1][0] = 0;
}
void insert(int x, int type)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = (x >> i & 1);
        if(!tree[type].ch[u][v]) // 新建节点
        {
            tree[type].ch[tol][1] = tree[type].ch[tol][0] = 0;
            tree[type].num[tol] = 0;
            tree[type].ch[u][v] = tol++;
        }
        u = tree[type].ch[u][v];
        tree[type].num[u]++;
    }
}
int query()
{
    int u0 = 0, u1 = 0, x = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int nxt0_0 = tree[0].ch[u0][0], nxt0_1 = tree[0].ch[u0][1], nxt1_0 = tree[1].ch[u1][0], nxt1_1 = tree[1].ch[u1][1];//下一行0，1对应的编号，若没有的话编号是0
        if(tree[0].num[nxt0_0] && tree[1].num[nxt1_0])//两棵字典树中都有数满足其第i位上是0
        {
            u0 = tree[0].ch[u0][0];
            u1 = tree[1].ch[u1][0];
            tree[0].num[nxt0_0]--;
            tree[1].num[nxt1_0]--;
        }
        else if(tree[0].num[nxt0_1] && tree[1].num[nxt1_1])
        {
            u0 = tree[0].ch[u0][1];
            u1 = tree[1].ch[u1][1];
            tree[0].num[nxt0_1]--;
            tree[1].num[nxt1_1]--;
        }
        else if(tree[0].num[nxt0_0] && tree[1].num[nxt1_1])
        {
            u0 = tree[0].ch[u0][0];
            u1 = tree[1].ch[u1][1];
            tree[0].num[nxt0_0]--;
            tree[1].num[nxt1_1]--;
            x += (1 << i);
        }
        else
        {
            u0 = tree[0].ch[u0][1];
            u1 = tree[1].ch[u1][0];
            tree[0].num[nxt0_1]--;
            tree[1].num[nxt1_0]--;
            x += (1 << i);
        }
    }
    return  x;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t, n, x;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        init(0);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            insert(x, 0);
        }
        init(1);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            insert(x, 1);
        }
        for(int i = 0; i < n; i++)
            ans[i] = query();
        sort(ans, ans + n);
        for(int i = 0; i < n; i++)
        {
            if(i) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}