Codeforces Round #430 (Div. 2)

题目链接：http://codeforces.com/contest/842/problem/D

题意：定义Mex为一个序列中最小的未出现的正整数，给定一个长度为n的序列，然后有m个询问，每个询问给定一个数x，先对序列每个数与x进行异或运算(^)，之后输出当前序列修改完之后的Mex。

思路：因为对于原序列和x异或后，得到的新序列再与y异或相当于原序列与z(z=x^y)进行异或，所以问题就可以转化为对于一个数val,原序列和val进行异或后得到新序列的Mex是多少？考虑01字典树，先把序列的n个数插入字典树(相同的数只插一次)，考虑现在的val=0，那么如果左子树(边权为0的边)没有满，说明Mex在左子树，否则在右子树，直到最后到叶子结点为止，那么答案就是该叶子所代表的权值。现在考虑val为任意数，对于val的二进制为0的位，按照上面的分析即可，但是对于二进制为1的位，优先走右子树(边权为1的边，因为1^1=0, 1^0=1，所以对于右子树相当于异或后的左子树，左子树相当于异或后的右子树), 一直到叶子结点为止。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<stdio.h>

#include<queue>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<time.h>

#include<cmath>

#include<sstream>

#include<assert.h>

using namespace std;

typedef long long int LL;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

const int MAXN = 3e5 + ;

struct Trie{

    int val[MAXN << ];

    int next[MAXN << ][];

    int root, L;

    int newnode(){

        next[L][] = next[L][] = -;  val[L] = ;

        return L++;

    }

    void init(){

        L = ; root = newnode(); build(,);

    }

    void build(int u,int deep){

        if (deep == ){

            return;

        }

        next[u][] = newnode();

        next[u][] = newnode();

        build(next[u][], deep + );

        build(next[u][], deep + );

    }

    void insert(int x){

        int now = root;

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

            int num = ( << i)&x ?  : ;

            now = next[now][num];

            val[now]++;

        }

    }

    int Query(int x){

        int now = root, res = ;

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

            int num = ( << i)&x ?  : ;

            if (val[next[now][num]] < ( << i)){ //异或后0的边

                now = next[now][num];

            }

            else{ //异或后1的边， 顺便把权值累计

                now = next[now][!num];

                res |= ( << i);

            }

        }

        return res;

    }

}trie;

set<int>se;

int main(){

#ifdef kirito

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int start = clock();

    int n, m,val;

    while (~scanf("%d%d", &n, &m)){

        int prexor = ;

        trie.init(); se.clear();

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

            scanf("%d", &val);

            if (!se.count(val)){

                trie.insert(val);

            }

            se.insert(val);

        }

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

            scanf("%d", &val);

            prexor ^= val;

            printf("%d\n", trie.Query(prexor));

        }

    }

#ifdef LOCAL_TIME

    cout << "[Finished in " << clock() - start << " ms]" << endl;

#endif

    return ;

}

巴特西

Codeforces Round #430 (Div. 2) - D

最新文章

热门文章