找球号(二）
时间限制：
1000 ms | 内存限制：
65535 KB
难度：
5
- 描述
-
在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，还有一个空箱子，现在有两种动作：一种是"ADD"，表示向空箱子里放m(0<m<=100)个球，另一种是"QUERY”，表示说出M(0<M<=100)个随机整数ki(0<=ki<=100000100),分别判断编号为ki 的球是否在这个空箱子中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。
- 输入
-
第一行有一个整数n(0<n<=10000);
随后有n行;
每行可能出现如下的任意一种形式：
第一种：
一个字符串"ADD"，接着是一个整数m，随后有m个i；
第二种：
一个字符串"QUERY”，接着是一个整数M，随后有M个ki；
- 输出
- 输出每次询问的结果"YES"或"NO".
- 样例输入
-
2 ADD 5 34 343 54 6 2 QUERY 4 34 54 33 66
- 样例输出
-
YES YES NO NO
1 2 #include<cstdio> 3 #include<bitset> 4 #include<cstring> 5 using namespace std; 6 7 bitset <100000001> Q; 8 int main() 9 { 10 char ch[11]; 11 int T,m,a,i,j; 12 scanf("%d",&T); 13 while(T--) 14 { 15 //Q.reset();//全部置为0，加上这一句就TLE，不加就AC 16 scanf("%s%d",ch,&m); 17 if(ch[0]=='A') 18 for(j=0;j<m;j++) 19 { 20 scanf("%d",&a); 21 Q[a]=1; 22 } 23 else for(j=0;j<m;j++) 24 { 25 scanf("%d",&a); 26 if(Q[a]==1) printf("YES\n"); 27 else printf("NO\n"); 28 } 29 } 30 }
//用hash一定要开大空间，否则可能TLE //用bitset亦可 //set，使用test方法判断是否存在 /* set.find(value) == set.end() 就是查找value是否在set里面 如果没找到，就会返回一个指向end()的iterator */ #include <iostream> #include <stdio.h> #include <string> #include <string.h> using namespace std; const int N = 9533333; const int ope = N; int ch[N]; //先对素数求余， 不求余，就把数组开大，不然value超过N怎么办 int hashfun(int val) { return val%(ope); } void insert(int num) { int pos=hashfun(num); while(ch[pos]>0) pos=(pos+1)%N; ch[pos]=num; } bool find(int num) { int pos=hashfun(num); int i=0; while(ch[pos]&&ch[pos]!=num&&i<N) pos=(pos+1)%N; if(ch[pos]&&i<N)return 1; return 0; } int main() { memset(ch,0,sizeof(ch)); int i,j,k,T; scanf("%d",&T); int cnt,num; string s; while(T--) { s.clear(); cin>>s; scanf("%d",&cnt); if(s=="ADD") { while(cnt--) { scanf("%d",&num); insert(num); } } if(s=="QUERY") { while(cnt--) { scanf("%d",&num); if(find(num)) puts("YES"); else puts("NO"); } } } return 0; }
