Educational Codeforces Round 23 817E. Choosing The Commander 字典树位运算

86 阅读 0 评论 57 点赞

我是靠谱客的博主体贴棒球，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 23 817E. Choosing The Commander 字典树位运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接: Choosing The Commander

题目大意

士兵有一个个性值p
将领有一个个性值p, 领导力l
( $1 leq p, l leq 10^8$ )
如果将领和士兵个性值按位异或的得到的值小于将领的领导力, 这个士兵会尊重这个将领
三种操作:
1 p:添加一名个性值为p的士兵
2 p:减少一名个性值为p的士兵
3 p l:个性值为p, 领导力为l的将领, 输出有多少士兵尊重他

思路

建立字典树
将个性值以二进制形式从高位到低位(31位-0位)插入字典树, 沿途经过的节点cnt值+1(每个节点cnt值代表的是经过这个节点的所有士兵数量)
减少士兵则将沿途节点cnt-1

对于每一个将领
也是将他的p和l从最高位到最低位一位位的处理
如果将领的p在这位的值为0
那么对于这位为1的士兵, 异或得1, 为0的士兵异或为0, 当将领领导力l在这位为0时, 为1的士兵一定不会尊重它, 接下来处理为0的士兵, 当将领领导力l在这位为1是, 为0的士兵一定会尊重它(高位有一位大于了, 整个数字一定大于), 接下去处理为1的士兵
如果将领在这位的值为1
对于为1的士兵, 异或得0, 为0的士兵异或得1, 接下来和过程就类似了

代码

#include <bits/stdc++.h>
using namespace std;

struct node
{
    node * nxt[2];
    int cnt;
    node()
    {
        cnt = 0;
        nxt[0] = nxt[1] = nullptr;
    }
};

void insert(node * root, int x)
{
    node * p = root;
    for(int i=31; i>=0; --i)
    {
        int t = bool(x & (1<<i));
        if(p->nxt[t] == nullptr) p->nxt[t] = new node;
        p = p->nxt[t];
        p->cnt++;
    }
}
void del(node * root, int x)
{
    node * p = root;
    for(int i=31; i>=0; --i)
    {
        int t = bool(x & (1<<i));
        p = p->nxt[t];
        p->cnt--;
    }
}

int query(node * root, int x, int l)
{
    node * p = root;
    int ret = 0;
    for(int i=31; i>=0; --i)
    {
        int tx = bool(x & (1<<i));
        int tl = bool(l & (1<<i));
        if(tx)
        {
            if(tl)
            {
                if(p->nxt[1]) ret += p->nxt[1]->cnt;
                p = p->nxt[0];
            }
            else 
            {
                p = p->nxt[1];
            }
        }
        else 
        {
            if(tl)
            {
                if(p->nxt[0]) ret += p->nxt[0]->cnt;
                p = p->nxt[1];
            }
            else 
            {
                p = p->nxt[0];
            }
        }
        if(p==nullptr) break;
    }
    return ret;
}


int main()
{
    int q, a, b, c;
    node * root = new node;
    for(scanf("%d", &q); q; --q)
    {
        scanf("%d%d", &a, &b);
        if(a==1) insert(root, b);
        else if(a==2) del(root, b);
        else 
        {
            scanf("%d", &c);
            printf("%dn", query(root, b, c));
        }
    }

    return 0;
}