[2019杭电多校第五场][hdu6625]three arrays（01字典树）

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

大意为给你两个数组a和b，对应位置异或得到c数组，现在可以将a,b数组从新排序求c数组，使得字典序最小。

大致的做法就是用两个数组中的数字二进制建两颗字典树，同时记录每个位置的个数。然后在两颗字典树上同时dfs，优先往0-0和1-1方向走，不能走再走0-1,1-0方向。

因为0-0和1-1两种情况不分先后，所以走出来的不一定是最小的，走完得到的c数组要排序。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 struct Trie {

     int tree[maxn * ][], num[maxn * ];

     int len, root;

     int newcode() {

         tree[len][] = tree[len][] = ;

         num[len] = ;

         return len++;

     }

     void init() {

         len = ;

         root = newcode();

     }

     void insert(int x) {

         int now = root;

         for (int i = ; i >= ; i--) {

             int k = (x >> i) & ;

             if (!tree[now][k])

                 tree[now][k] = newcode();

             now = tree[now][k];

             num[now]++;

         }

     }

 }A, B;

 int ans[maxn];

 void slove(int n) {

     for (int i = ; i <= n; i++) {

         ans[i] = ;

         int nowA = , nowB = ;

         for (int j = ; j >= ; j--) {

             if (A.num[A.tree[nowA][]] && B.num[B.tree[nowB][]]) {

                 nowA = A.tree[nowA][], nowB = B.tree[nowB][];

                 A.num[nowA]--, B.num[nowB]--;

             }

             else if (A.num[A.tree[nowA][]] && B.num[B.tree[nowB][]]) {

                 nowA = A.tree[nowA][], nowB = B.tree[nowB][];

                 A.num[nowA]--, B.num[nowB]--;

             }

             else if (A.num[A.tree[nowA][]] && B.num[B.tree[nowB][]]) {

                 nowA = A.tree[nowA][], nowB = B.tree[nowB][];

                 A.num[nowA]--, B.num[nowB]--;

                 ans[i] += ( << j);

             }

             else if (A.num[A.tree[nowA][]] && B.num[B.tree[nowB][]]) {

                 nowA = A.tree[nowA][], nowB = B.tree[nowB][];

                 A.num[nowA]--, B.num[nowB]--;

                 ans[i] += ( << j);

             }

         }

     }

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n, x;

         A.init(), B.init();

         scanf("%d", &n);

         for (int i = ; i <= n; i++)

             scanf("%d", &x), A.insert(x);

         for (int i = ; i <= n; i++)

             scanf("%d", &x), B.insert(x);

         slove(n);

         sort(ans + , ans +  + n);

         for (int i = ; i <= n; i++)

             printf("%d%c", ans[i], i == n ? '\n' : ' ');

     }

 }

巴特西

[2019杭电多校第五场][hdu6625]three arrays（01字典树）

最新文章

热门文章