找球号(二)
时间限制: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 //代码一:用邻接表存储--hash 2 #include<stdio.h> 3 #include<string.h> 4 #include<malloc.h> 5 #define Mod 10000 6 struct Node 7 { 8 int num; 9 struct Node *next; 10 }node[10001]; 11 12 int main() 13 { 14 int n,t,temp,i; 15 char s[10]; 16 struct Node *t1; 17 scanf("%d",&n); 18 for(i=0;i<10001;++i) 19 { 20 node[i].num=i; 21 node[i].next=NULL; 22 } 23 while(n--) 24 { 25 scanf("%s",s); 26 if(s[0]=='A') 27 { 28 scanf("%d",&t); 29 for(i=0;i<t;++i) 30 { 31 scanf("%d",&temp); 32 t1=(struct Node *)malloc(sizeof(struct Node)); 33 t1->num=temp; 34 t1->next=node[temp%Mod].next; 35 node[temp%Mod].next=t1; 36 } 37 } 38 else 39 { 40 scanf("%d",&t); 41 for(i=0;i<t;++i) 42 { 43 scanf("%d",&temp); 44 t1=node[temp%Mod].next; 45 if(t1==NULL) 46 { 47 printf("NO\n"); 48 continue; 49 } 50 while(t1) 51 { 52 if(t1->num==temp) 53 { 54 printf("YES\n"); 55 break; 56 } 57 t1=t1->next; 58 } 59 if(t1==NULL) 60 printf("NO\n"); 61 } 62 } 63 } 64 return 0; 65 }
//代码二:利用二进制位 hash
#include <iostream> #include <cstdio> using namespace std; int flag[3125001]; int main() { int n, t; scanf("%d", &n); char cmd[6]; while(n--) { scanf("%s", cmd); scanf("%d", &t); int temp; if(cmd[0] == 'A') { while(t--) { scanf("%d", &temp); flag[temp / 32] |= 1 << (temp % 32); } } else { while(t--) { scanf("%d", &temp); if(flag[temp / 32] & 1 << (temp % 32)) printf("YES\n"); else printf("NO\n"); } } } return 0; }