codeforces 842 D. Vitya and Strange Lesson（01字典树+思维+贪心）

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

题解：像这种求一段异或什么的都可以考虑用字典树而且mex显然可以利用贪心+01字典树，和线段树差不多就是比较节点总数和有的数字数比较有限向左边转移。

然后这个异或其实可以利用一个数num与一个一个的x异或然后求异或的mex也是容易的只要判断当前二进制位是1那么左右节点拥有的数字数互换（不用真的互换

只要用转移体现出来就行了）。这里的01字典树写法是类似线段树且利用递归的方法。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 2e5 + ;

int ch[ * M][] , nodes[ * M];

int node_size , num;

void build(int pos , int node) {

    if(pos < ) return;

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

        ch[node][i] = ++node_size;

        nodes[node_size] = ;

        build(pos -  , ch[node][i]);

    }

}

void init() {

    node_size = ;

    nodes[] = ;

    build( , );

}

void Insert(int node , int x , int pos) {

    if(pos < ) {

        nodes[node] = ;

        return ;

    }

    int id = (x >> pos) & ;

    Insert(ch[node][id] , x , pos - );

    nodes[node] = nodes[ch[node][id]] + nodes[ch[node][id ^ ]];

}

int query(int node , int x , int pos) {

    if(pos < ) return x;

    int gg = (num >> pos) & ;

    if(nodes[ch[node][gg]] < ( << pos)) return query(ch[node][gg] , x , pos - );

    return query(ch[node][gg ^ ] , x | ( << pos) , pos - );

}

int main() {

    int n , m , x;

    num = ;

    init();

    scanf("%d%d" , &n , &m);

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

        scanf("%d" , &x);

        Insert( , x , );

    }

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

        scanf("%d" , &x);

        num ^= x;

        printf("%d\n" , query( ,  , ));

    }

    return ;

}

巴特西

codeforces 842 D. Vitya and Strange Lesson（01字典树+思维+贪心）

最新文章

热门文章