首页 > 代码库 > 南阳OJ-138 找球号(二)(hash表应用)

南阳OJ-138 找球号(二)(hash表应用)

找球号(二)

时间限制: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 #include<stdio.h>
 2 #include<string.h>
 3 #define base 1000000    //由于0 <= data <= 10^8 且最大往箱子放100个球,最坏的假设是100个球都不一样 需要10^6的空间 
 4 struct node {
 5     int data, next;
 6 }hash[base+10];
 7 int head[base+10], ip;
 8 void add(int x) {    //添加元素进hash表 
 9     int y = x%base;
10     hash[ip].data =http://www.mamicode.com/ x;
11     hash[ip].next = head[y];
12     head[y] = ip;
13     ip++;
14 }
15 bool query(int x) {//查找数值是否在hash表中 
16     int y = x%base;
17     for (int i = head[y]; i != -1; i = hash[i].next)
18         if (hash[i].data =http://www.mamicode.com/= x)
19             return true;
20     return false;
21 }
22 int main() {
23     int t;
24     memset(head, -1, sizeof(head));
25     scanf("%d", &t);
26     while (t--) {
27         char str[10];
28         int n, m;
29         scanf("%s %d", str, &n);
30         if (str[0] == A)
31             while (n--) {
32                 scanf("%d",&m);
33                 add(m);
34             }
35         else
36             while (n--) {
37                 scanf("%d", &m);
38                 if (query(m))
39                     printf("YES\n");
40                 else
41                     printf("NO\n");
42             }
43     }
44 }

 也可以用stl中的vector ac

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 using namespace std;
 5 int main() {
 6     vector<bool> v(100000005);
 7     int t;
 8     scanf("%d", &t);
 9     while (t--) {
10         char str[10];
11         int n, m;
12         scanf("%s %d", str, &n);
13         if (str[0] == A)
14             for (int i = 0; i < n; i++) {
15                 scanf("%d", &m);
16                 v[m] =  true;
17             }
18         else {
19             for (int i = 0; i < n; i++) {
20                 scanf("%d", &m);
21                 if (v[m])
22                     printf("YES\n");
23                 else
24                     printf("NO\n");
25             }
26                 
27         }
28     }
29 }

 

南阳OJ-138 找球号(二)(hash表应用)