题目描述:
一开始你有一个空集,集合可以出现重复元素,然后有 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;
}