@

题意：

\(T(100)\)组，每组两个长度为\(n(100000)\)的排列，你可以将\(a[]\)和\(b[]\)随机排列，可以得到\(c[i]=a[i]\)^\(b[i]\)，求字典序最小的\(c[]\)。

解析

一个显然对的贪心做法：

针对本题

  • 每次两颗字典树同时往下走，如果都有\(0\)或者\(1\)这条路径，就随便同时走\(0\;or\;1\)这条路径，否则只能一个走\(0\)，一个走\(1\)。这样复杂度是严格\(O(log)\)的，最后将得到的\(n\)个数字排序即为最后答案。
  • 这样为什么正确呢？
  • 如果当前两字典树都有\(0\)和\(1\)的路径，同时走\(0\)这条路得到数字肯定不能保证是当前能异或出来的最小值，但是可以肯定的是他一定是字典序最小的序列所包含的某个值。
  • 如果想单纯的求两个01字典树异或最小值，个人感觉还没有较好的复杂度的做法。

一个可以推广的正解：

  • 出题人\(dreamoon\)提供的正解：
  • 现在\(a[]\)中随便找一个数字\(x\)，然后在\(b[]\)中相应找一个和\(x\)匹配异或最小的数字\(y\)，再在\(a[]\)里面找一个和\(y\)匹配最小的数字\(z\)，递归下去一定会找到一个大小为2的环。
  • 把这个环这两个数字取出来，再回到上一个失配位置继续递归下去。
  • 这样得到的\(n\)个数字排序后即为最终答案。
  • 复杂度同样很科学并且这个思路适用性很广。

Code1

const int MXN = 1e5 + 7;

const int MXE = 2e6 + 7;

int n, m;

int ar[MXN], br[MXN];

struct Trie {

    int tot;

    int nex[MXE][2], num[MXE], val[MXE];

    Trie(){nex[0][0] = nex[0][1] = -1;}

    void newnode() {

        ++ tot;

        nex[tot][0] = nex[tot][1] = -1;

    }

    void inisert(int x) {

        int rt = 0;

        for(int i = 31, tmp; i >= 0; --i) {

            tmp = ((x>>i)&1);

            if(nex[rt][tmp] == -1) newnode(), nex[rt][tmp] = tot;

            rt = nex[rt][tmp];

            num[rt] ++;

        }

        val[rt] = x;

    }

    void del(int x) {

        int rt = 0;

        for(int i = 31, tmp; i >= 0; --i) {

            tmp = ((x>>i)&1);

            int lst = rt;

            rt = nex[rt][tmp];

            nex[lst][tmp] = -1;

            num[rt] = 0;

        }

    }

}cw[2];

bool check(int id, int rt, int tmp) {

    return cw[id].nex[rt][tmp] != -1 && cw[id].num[cw[id].nex[rt][tmp]] > 0;

}

int getans() {

    int rt1 = 0, rt2 = 0;

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

        if(check(0, rt1, 0) && check(1, rt2, 0)) {

            rt1 = cw[0].nex[rt1][0];

            rt2 = cw[1].nex[rt2][0];

            -- cw[0].num[rt1];

            -- cw[1].num[rt2];

        }else if(check(0, rt1, 1) && check(1, rt2, 1)) {

            rt1 = cw[0].nex[rt1][1];

            rt2 = cw[1].nex[rt2][1];

            -- cw[0].num[rt1];

            -- cw[1].num[rt2];

        }else if(check(0, rt1, 1) && check(1, rt2, 0)) {

            rt1 = cw[0].nex[rt1][1];

            rt2 = cw[1].nex[rt2][0];

            -- cw[0].num[rt1];

            -- cw[1].num[rt2];

        }else if(check(0, rt1, 0) && check(1, rt2, 1)) {

            rt1 = cw[0].nex[rt1][0];

            rt2 = cw[1].nex[rt2][1];

            -- cw[0].num[rt1];

            -- cw[1].num[rt2];

        }

    }

    return cw[0].val[rt1] ^ cw[1].val[rt2];

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);

//    freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);

#endif

    int tim = read();

    while(tim --) {

        n = read();

        cw[0].tot = cw[1].tot = 0;

        for(int i = 1; i <= n; ++i) ar[i] = read(), cw[0].inisert(ar[i]);

        for(int i = 1; i <= n; ++i) br[i] = read(), cw[1].inisert(br[i]);

        vector<int> vs;

        for(int i = 1; i <= n; ++i) vs.eb(getans());

        sort(all(vs));

        for(int i = 0; i < SZ(vs); ++i) printf("%d%c", vs[i], " \n"[i == SZ(vs) - 1]);

        for(int i = 1; i <= n; ++i) cw[0].del(ar[i]), cw[1].del(br[i]);

    }

    return 0;

}

Code2

const int MXN = 1e5 + 7;

const int MXE = 2e6 + 7;

int n, m;

int ar[MXN], br[MXN];

struct Trie {

    int tot;

    int nex[MXE][2], num[MXE], val[MXE];

    Trie(){nex[0][0] = nex[0][1] = -1;}

    void newnode() {

        ++ tot;

        nex[tot][0] = nex[tot][1] = -1;

    }

    void inisert(int x) {

        int rt = 0;

        for(int i = 30, tmp; i >= 0; --i) {

            tmp = ((x>>i)&1);

            if(nex[rt][tmp] == -1) newnode(), nex[rt][tmp] = tot;

            rt = nex[rt][tmp];

            num[rt] ++;

        }

        val[rt] = x;

    }

    int query(int x) {

        int rt = 0;

        for(int i = 30, tmp; i >= 0; --i) {

            tmp = ((x>>i)&1);

            if(nex[rt][tmp] != -1 && num[nex[rt][tmp]]) rt = nex[rt][tmp];

            else rt = nex[rt][!tmp];

        }

        return val[rt];

    }

    int find() {

        int rt = 0;

        for(int i = 30, tmp; i >= 0; --i) {

            if(nex[rt][0] != -1 && num[nex[rt][0]]) rt = nex[rt][0];

            else if(nex[rt][1] != -1 && num[nex[rt][1]]) rt = nex[rt][1];

        }

        if(rt == 0) return -1;

        return val[rt];

    }

    void del() {

        for(int i = 0; i <= tot + 1; ++i) num[i] = 0, clr(nex[i], -1);

        tot = 0;

    }

    void sub(int x) {

        int rt = 0;

        for(int i = 30, tmp; i >= 0; --i) {

            tmp = ((x>>i)&1);

            rt = nex[rt][tmp];

            num[rt] --;

        }

    }

}cw[2];

/*

 * 这种做法不能保证每次求出来的异或最小值都是单调递增的，但是将n次得到的值排序后一定是正确答案

 * 如果想单纯的求两个01字典树异或最小值，个人感觉还没有较好的复杂度的做法。

 * 关于本题，还有一个出题人提供适用性更加广泛的正解：

 * 现在a中随便找一个数字，然后在b中找一个和他匹配最小的数字，再在a里面找一个和上个数匹配最小的数字，递归下去一定会找到一个大小为2的环

 * 把这个环取出来，在回到上一个位置继续递归下去。得到的n个数字排序即为最终答案。

 * */

vector<int> vs;

int dfs(int id, int x, int lst) {

    int tmp = cw[!id].query(x);

    if(tmp == lst) {

        vs.eb(tmp ^ x);

        cw[id].sub(x);

        cw[!id].sub(tmp);

        return id;

    }

    int ret = dfs(!id, tmp, x);

    if(ret != id) return ret;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);

//    freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);

#endif

    int tim = read();

    while(tim --) {

        n = read();

        for(int i = 1; i <= n; ++i) ar[i] = read(), cw[0].inisert(ar[i]);

        for(int i = 1; i <= n; ++i) br[i] = read(), cw[1].inisert(br[i]);

        vs.clear();

        while(1) {

            int tmp = cw[0].find();

            if(tmp == -1) break;

            dfs(1, tmp, -1);

        }

        sort(all(vs));

        for(int i = 0; i < SZ(vs); ++i) printf("%d%c", vs[i], " \n"[i == SZ(vs) - 1]);

        cw[0].del(), cw[1].del();

    }

    return 0;

}

原题描述

字典树动态求Mex

CF842D

把所有数字从高位开始插入字典树，对每个节点维护下面叶子节点的个数。判断与当前询问为异或为0的子树是否满叶子，若不是满叶子则Mex在此路径下，反之在异或为1那条路径下。

const int TRIE_MAX = 25;

int n, m;

int ar[MXN];

int node, nex[MXN][2], is[MXN];

void new_node() {

    clr(nex[++node], -1);

}

void insert(int x) {

    int rt = 0;

    for(int i = TRIE_MAX, t; i >= 0; --i) {

        t = (x>>i)&1;

        if(nex[rt][t] == -1) {

            new_node();

            nex[rt][t] = node;

        }

        rt = nex[rt][t];

    }

    if(is[rt] == 0) {

        rt = 0;

        for(int i = TRIE_MAX, t; i >= 0; --i) {

            t = (x>>i)&1;

            rt = nex[rt][t];

            ++ is[rt];

        }

    }

}

int query(int x) {

    int ans = 0, rt = 0;

    for(int i = TRIE_MAX, t; i >= 0; --i) {

        t = (x>>i)&1;

        if(rt == -1 || nex[rt][t] == -1) break;

//        if(i <= 1) debug(rt, t, nex[rt][t], is[nex[rt][t]], i)

        if(is[nex[rt][t]] == (1<<i)) t ^= 1, ans |= (1<<i);

        rt = nex[rt][t];

//        debug(rt)

    }

    return ans;

}

最新文章

  1. js的Array的map和sort实现方法
  2. poj1155
  3. 文件输入流 FileInputStream类 文件输出流FileOutputStream ---转载
  4. jsp放在web-inf下的注意事项
  5. Liunx 下使用cmake
  6. angularJS自定义指令间的“沟通”
  7. Learing WCF Chapter1 Fundamental WCF Concepts
  8. C# Sending data using GET or POST ZZ
  9. STL源码剖析之list的sort函数实现
  10. java 根据时间生成唯一id
  11. 终于说再见了！Google Reader
  12. Marble 添加自定义Layer
  13. 结对作业NO.2
  14. (转)SQLServer_十步优化SQL Server中的数据访问 三
  15. LabVIEW将字符串转化为十进制
  16. django —— MVT模型
  17. 学习MongoDB(三) Add an Arbiter to Replica Set 集群中加入仲裁节点
  18. Nginx的配置文件nginx.conf配置详解
  19. 未在本地计算机上注册“microsoft.ACE.oledb.12.0”提供程序的解决方法
  20. Redis实战（四）CentOS 7上Redis哨兵

热门文章

  1. （转）Docker network命令
  2. Java JsonPath grab InvalidPathException in code, you must be catching Java 7&#39;s java.nio.file.InvalidPathException instead of JsonPath&#39;s com.jayway.jsonpath.InvalidPathExceptio
  3. laravel框架手动删除迁移文件后再次创建报错
  4. java并发编程笔记（十）——HashMap与ConcurrentHashMap
  5. delphi xe2 opencv 学习
  6. 怎样理解Functor与Monad
  7. 蛋糕仙人的javascript笔记
  8. python基础--快速排序
  9. Linux上用sublime编辑Python时候出现&quot;SyntaxError: Non-ASCII character ‘\xe5′ in file&quot;的问题
  10. shell中#*,##*,#*,##*,% *,%% *的含义及用法