题意：给出A数组，B数组，你可以对A和B分别进行重排列，使得C[i]=A[i]^B[i]的字典序最小。
思路：对于这类题，显然需要建立字典树，然后某种形式取分治，或者贪心。 假设现在有了两颗字典树A，B，显然尽量让同方向的先匹配。
而且同一棵树的左右两边相互不影响，所以可以直接贪：如果A树上出发左走有x个数字，B左走有y个数字，那么一定会左匹配min(x,y)；右匹配同理； 剩下的交叉匹配；
看代码应该就会看懂了：add建立字典树。
dfs进行匹配； (i,j)从前往后分别是，(0,0) (1,1),(0,1) (1,0)保证了相同的先匹配。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=100010; int ch0[maxn*30][2],ch1[maxn*30][2],tot0,tot1; int ans[maxn],num,sum0[maxn*30],sum1[maxn*30]; void init() { rep(i,0,tot0) rep(j,0,1) ch0[i][j]=0; rep(i,0,tot1) rep(j,0,1) ch1[i][j]=0; tot0=tot1=num=0; } void add(int ch[][2],int sum[],int x,int &tot) { for(int i=29,now=0;i>=0;i--){ int t=(x>>i)&1; if(!ch[now][t]) ch[now][t]=++tot; now=ch[now][t]; sum[now]++; } } void dfs(int now0,int now1,int cost,int dep) { int e=min(sum0[now0],sum1[now1]); sum0[now0]-=e; sum1[now1]-=e; if(dep==-1) { rep(i,1,e) ans[++num]=cost; return ; } rep(k,1,4){ int i=k&1,j=i^1; if(k<=2) j=i; if(sum0[ch0[now0][i]]&&sum1[ch1[now1][j]]) dfs(ch0[now0][i],ch1[now1][j],cost+(i==j?0:(1<<dep)),dep-1); } } int main() { int T,N,x; scanf("%d",&T); while(T--){ init(); scanf("%d",&N); rep(i,1,N){ scanf("%d",&x); add(ch0,sum0,x,tot0); } rep(i,1,N){ scanf("%d",&x); add(ch1,sum1,x,tot1); } dfs(0,0,0,29); sort(ans+1,ans+N+1); rep(i,1,N-1) printf("%d ",ans[i]); printf("%d ",ans[N]); } return 0; }