NYOJ 138 找球号(二） (Hash) OJ

题目138
题目信息
运行结果
本题排行
讨论区

找球号(二）时间限制： 1000 ms|内存限制： 65535 KB 难度： 5

描述: 在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，还有一个空箱子，现在有两种动作：一种是"ADD"，表示向空箱子里放m(0
输入: 第一行有一个整数n(0 随后有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

【NYOJ 138 找球号(二） (Hash)】 此题的正确解法应该是Hash，但是可以用其他的方法水过
1.标准hash表

#include #include using namespace std; const int maxn = 1000010; const int fib = 111123; int key[maxn]; int head[maxn]; //相当于每一个散列表的头节点 int next[maxn]; //当前节点的下一个节点 int top; void add(int n) { int temp; temp = n % fib; key[top] = n; //在Hash表中记录下这个数值 next[top] = head[temp]; head[temp] = top; top++; }int main() { int n, m, number; char str[8]; bool flag; memset(key, 0, sizeof(key)); memset(next, 0, sizeof(next)); memset(head, -1, sizeof(head)); //相当于把每一个映射的头结点的next都赋为NULL top = 0; scanf("%d", &n); while (n--){ scanf("%s", str); if (str[0] == 'A'){ scanf("%d", &m); for (int i = 0; i < m; i++){ scanf("%d", &number); add(number); } } else{ scanf("%d", &m); for (int i = 0; i < m; i++){ flag = 0; scanf("%d", &number); int temp = number % fib; for (int j = head[temp]; j != -1; j = next[j]){ if (key[j] == number){ flag = 1; break; } } if (flag) printf("YES\n"); else printf("NO\n"); } } } return 0; }

2.最优的解法
3125005怎么来的？因为最大值是10^7+10。用32来除法散列，（10^7+10）/32 ~~3125000.3125，所以取3125005。为什么是用32来散列呢？数据说了数值不会超过32位。

#include using namespace std; unsigned int hash[3125005] = {0}; int main() { int n, m, number; char str[8]; scanf("%d", &n); while (n--){ scanf("%s", str); if (str[0] == 'A'){ scanf("%d", &m); for (int i = 0; i < m; i++){ scanf("%d", &number); hash[number / 32] |= 1 << (number % 32); } } else{ scanf("%d", &m); for (int i = 0; i < m; i++){ scanf("%d", &number); if (hash[number / 32] & (1 << (number % 32))) printf("YES\n"); else printf("NO\n"); } } } return 0; }

3.使用vector水过
但是最好不要使用vectot

#include #include #include using namespace std; vector flag(100000010); int main() { int n, m, a, b; char s[6]; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%s", s); if (s[0] == 'A'){ scanf("%d", &m); for (int i = 0; i < m; i++){ scanf("%d", &a); flag[a] = 1; } } else{ scanf("%d", &m); for (int i = 0; i < m; i++){ scanf("%d", &b); if (flag[b]) printf("YES\n"); else printf("NO\n"); } } } return 0; }