[NOIP模拟][分块]subset

时间:2022-12-16 14:04:25

题目描述:
一开始你有一个空集,集合可以出现重复元素,然后有 Q 个操作:
1、add s
在集合中加入数字 s 。
2、del s
在集合中删除数字 s 。保证 s 存在。如果有多个 s,只删除一个即可。
3、 cnt s
查询满足 a&s=a 条件的 a 的个数。
输入格式:
第一行一个整数 Q 接下来 Q 行,每一行都是 3 个操作中的一个。
输出格式:
对于每个 cnt 操作输出答案。
样例输入:
7
add 11
cnt 15
add 4
add 0
cnt 6
del 4
cnt 15
样例输出:
1
2
2
数据规模:
对于 30% 的数据满足:1≤n≤1000;
对于 100% 的数据满足:1≤n≤200000;0<s<2^16
题目分析:
分块算法。
1、因为s<2^16,以2^8分块,a[pre] [suf],其中下标pre表示前8位(指的二进制的8位,但是以十进制存,后皆同),suf表示后8位,存的是个数。对于任意数分成前8位(用位运算左移8位),后8位(&255得到,因为255的二进制码是11111111(8个1),与运算就直接得到后八位了)。
2、整体思想是分成2^8块,依据是前8位,对应第一维pre,每次把加入(删掉)的数依次看是否丢入(取出)块中。在询问中直接进入询问数a的前八位对应的块,在块里枚举,对应第二维suf。
注:(感觉讲的有点不清楚,限于语文水平~~~,将就啦······)
附代码:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,x,a[256][256];
char s[5];

int main()
{
    //freopen("subset.in","r",stdin);
    //freopen("subset.out","w",stdout);

    scanf("%d",&n);
    while(n--)
    {
        int f=1;
        scanf("%s%d",s,&x);
        int pre=x>>8,suf=x&255;//处理得到前8位和后8位 
        if(s[0]=='d') f=-1; 
        if(s[0]!='c') 
        {
            for(int i=0;i<=255;i++)
                if((pre&i)==pre)//只有与前8位与运算是其本身才存下来,相当于处理了前8位 
                    a[i][suf]+=f;
        }
        else
        {
            int cnt=0;
            for(int i=0;i<=255;i++)
                if((i&suf)==i)//因为在添加和删除操作已经处理pre,存的就是与pre与运算相等的,此时的pre相当于就是上个中的i 
                    cnt+=a[pre][i];//所以此时,只需枚举suf,判断与运算相等的,累加,就得到答案 
            printf("%d\n",cnt);
        }
    }

    return 0;
}