NOIP模拟题 2015.8.6 T3
HJWJBSR
posted @ 2015年8月16日 22:40
in 题解
, 430 阅读
输入格式:第一行一个n为操作数,后面n行每行一个字符串和一个数x,前面为add时就是加进来x,del则为减去x,否则是查询x
输出格式:对于每个cnt输出一行答案
Sample Input:
7
add 11
cnt 15
add 4
add 0
cnt 6
del 4
cnt 15
Sample Output:
1
2
2
题解:这场好像水了前两题然后这题想着想着就睡着了= =
可以分块操作,设a[pre][suf]代表集合中前八个二进制位是pre而后八个与suf与运算不变的数个数。然后枚举子集什么的就可以做到插入删除查找都是sqrt(n)的了。然而这题被大爷暴力怒A了
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 256 int s[N][N],t;char b[20]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } int main() { freopen("subset.in","r",stdin); freopen("subset.out","w",stdout); t=Read(); while (t--) { scanf("%s",b);int w=Read(); if (b[0]!='c') { int e=b[0]=='d'?-1:1,l=w >> 8,k=N-(w&(N-1))-1; for (int i=k;i;i=(i-1)&k) s[l][N-i-1]+=e; s[l][N-1]+=e; }else { int l=w >> 8,k=w%N,e=s[0][k]; for (int i=l;i;i=(i-1)&l) e+=s[i][k]; printf("%d\n",e); } } return 0; }