NOIP模拟题 2015.8.2 T1
NOIP模拟题 2015.8.10 T2

NOIP模拟题 2015.8.6 T3

HJWJBSR posted @ 2015年8月16日 22:40 in 题解 , 410 阅读

输入格式:第一行一个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;
 }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter