hdu6625 three arrays 01字典树

题意：有两个数组a和b，可以随意调换数组中的元素的顺序，令 c[ i ] = a[ i ] ^ b[ i ]，使c的字典序最小。

思路：每个数按二进制从高位到低位看作一个字符串，对a和b数组分别建一棵01字典树，并记录每个结点出现的次数。然后同时遍历这两棵字典树，优先走当前位相同的（0和0，1和1），这样一定是最优的，因为每个数是由二进制从高位到低位排的，异或可以抵消高位。

求出来后还要再排个序。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e5+10;
 5 
 6 int n;
 7 int ans[N];
 8 
 9 struct Tire{
10     int t[N*30][2],num[N*30];
11     int tot,root;
12     int New(){
13         t[tot][0]=t[tot][1]=0;
14         num[tot]=0;
15         return tot++;
16     }
17     void init(){
18         tot=0;
19         root=New();
20     }
21     void insert(int x){
22         int p=root;
23         for(int i=29;i>=0;i--){
24             int k=(x>>i)&1;
25             if(!t[p][k])
26                 t[p][k]=New();
27             p=t[p][k];
28             num[p]++;
29         }
30     }
31 }; 
32 Tire A,B;
33 
34 void solve(){
35     for(int i=1;i<=n;i++){
36         int p1=0,p2=0;
37         ans[i]=0;
38         for(int j=29;j>=0;j--){
39             if(A.num[A.t[p1][0]]&&B.num[B.t[p2][0]]){
40                 p1=A.t[p1][0];
41                 p2=B.t[p2][0];
42                 A.num[p1]--,B.num[p2]--;
43             }
44             else if(A.num[A.t[p1][1]]&&B.num[B.t[p2][1]]){
45                 p1=A.t[p1][1];
46                 p2=B.t[p2][1];
47                 A.num[p1]--,B.num[p2]--;
48             }
49             else if(A.num[A.t[p1][0]]&&B.num[B.t[p2][1]]){
50                 p1=A.t[p1][0];
51                 p2=B.t[p2][1];
52                 A.num[p1]--,B.num[p2]--;
53                 ans[i]+=(1<<j);
54             }
55             else if(A.num[A.t[p1][1]]&&B.num[B.t[p2][0]]){
56                 p1=A.t[p1][1];
57                 p2=B.t[p2][0];
58                 A.num[p1]--,B.num[p2]--;
59                 ans[i]+=(1<<j);
60             }
61         }
62     }
63 }
64 
65 int main()
66 {
67     int T;
68     scanf("%d",&T);
69     while(T--){
70         A.init(),B.init();
71         scanf("%d",&n);
72         for(int i=1;i<=n;i++){
73             int x;
74             scanf("%d",&x);
75             A.insert(x);
76         }
77         for(int i=1;i<=n;i++){
78             int x;
79             scanf("%d",&x);
80             B.insert(x);
81         }
82         solve();
83         sort(ans+1,ans+n+1);
84         for(int i=1;i<=n;i++){
85             printf("%d%c",ans[i],i==n? '
':' ');
86         }
87     }
88     return 0;
89 }