Choosing The Commander CodeForces - 817E (01字典树)

60 阅读 0 评论 40 点赞

我是靠谱客的博主想人陪鱼，最近开发中收集的这篇文章主要介绍Choosing The Commander CodeForces - 817E (01字典树)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

题意：给出三个操作，第一种操作是1 pi表示加入一个士兵的个性值为pi，第二种操作是2 pi表示撤离一个士兵的个性值为pi，第三种操作是3 pj lj，问加入的士兵中个性值与这个pj异或下来的值是否小于lj，在加入的士兵中总共有多少个这种士兵？

题解：首先存在大量的按位异或的运算，那么可以把加入的士兵的个性值设为二进制存入字典树中，然后用val维护个数，这样撤离也直接维护val即可，这样查找是如果此时这个位上的lj是0的话，把指针转到相应pj的此时的位上，否则直接加上pj这个位上的数量，把指针转到另一边即可。

附上代码：

#include<bits/stdc++.h>

using namespace std;

const int maxnode=1e5*50;
const int sigma_size=5;

struct Trie{
    int ch[maxnode][sigma_size];
    int val[maxnode];
    int sz;
    void clear(){
        sz=1;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }
    void insert(int x){
        int u=0;
        for(int i=31;i>=0;i--){
            int a=bool(x&(1<<i));
            if(!ch[u][a]){
                memset(ch[sz],0,sizeof(ch[sz]));
                ch[u][a]=sz++;
            }
            u=ch[u][a];
            val[u]++;
        }
    }
    void deletee(int x){
        int u=0;
        for(int i=31;i>=0;i--){
            int a=bool(x&(1<<i));
            u=ch[u][a];
            val[u]--;
        }
    }
    int find_prefixes(int x,int l){
        int u=0,ans=0;
        for(int i=31;i>=0;i--){
            int tx=bool(x&(1<<i));
            int tl=bool(l&(1<<i));
            if(tl==0){
                u=ch[u][tx];
            }else{
                ans+=val[ch[u][tx]];
                u=ch[u][1-tx];
            }
            if(u==0){
                break;
            }
        }
        return ans;
    }
};
Trie trie;

int main()
{
    int q;
    scanf("%d",&q);
    int com,p,l;
    trie.clear();
    for(int i=1;i<=q;i++){
        scanf("%d",&com);
        if(com==1){
            scanf("%d",&p);
            trie.insert(p);
        }else if(com==2){
            scanf("%d",&p);
            trie.deletee(p);
        }else{
            scanf("%d%d",&p,&l);
            int ans=trie.find_prefixes(p,l);
            printf("%dn",ans);
        }
    }
    return 0;
}