题目：
在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号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亿,并且可重复）非常的大！但是最多只有100个球，所以用一个大数组，下标（球号可重复）表示球号，内容标记是否存在，显然是不合理的。
所以考虑用hash，hash就是将关键字和位置建立映射关系。但是不同的关键字可能对应到同一位置，这就是冲突，怎么处理冲突？方法很多。好的处理冲突的方法可以大大加速查找速度。我暂时只会用链地址法处理冲突。就是把关键字（可以存）当成链表头结点，如果后面算出的key和关键字相同，则插入到以关键字为头结点的那个链表中。所以一个链表的元素都是会对应同一个位置的（如果用数组），这样弄成链表（如果是数组，一个位置只能放一个数）就好查找了。
hash就是插入和查找，插入的时候先查找，没找到才插，否则不用插。
代码：
#include<iostream>
#include<cstdio>
#define SIZE 1000001
#define MOD 1000000
//减小冲突的次数
using namespace std;
/* 感觉用链地址法处理hash冲突的话好像那个图的邻接表啊 */
typedef struct node
{
int key;
struct node *next;
}HashNode;
HashNode hash[SIZE];//结构体数组存放链表头结点
HashNode * search(HashNode head[SIZE],int k);//查找key的位置
void insert(HashNode head[SIZE],int k);//插入关键字k
int main()
{
int n,num,a,i;
char ch[6];
scanf("%d",&n);
for(i = 0 ; i != SIZE ; ++i)//将所有头结点初始化
{
hash[i].key = -1;
hash[i].next == NULL;
}
do
{
scanf("%s",ch);
if(ch[0] == 'A')
{
scanf("%d",&num);
for( i = 0 ; i != num ; ++i )
{
scanf("%d",&a);
insert(hash,a);
}
}
else
{
scanf("%d",&num);
for( i = 0 ; i != num ; ++i )
{
scanf("%d",&a);
if(search(hash,a))
puts("YES");
else
puts("NO");
}
}
}while(--n);
//system("pause");
return 0;
}
HashNode * search(HashNode head[SIZE],int k)
{
HashNode *s ;
int pos = k % MOD;//算出关键字的位置
s = & head[pos] ; //让指针s指向这一链的头结点
while(s && s->key != k)//当当前结点不空，并且key未找到，就继续找，知道找到或者不存在为止
s = s->next;
return s;//如果s 为空，则没找到，否则 查找成功
}
void insert(HashNode head[SIZE],int k)
{
HashNode * q, *one;
int pos;
one = new HashNode;//开辟一个新结点
q = search(head,k);
if(q)//如果找到，便不需要插入了
delete one;
else//没找到，说明是新结点，可以插入 ，插在头结点的后面
{
pos = k % MOD ;//算出关键字的位置
one->key =k;
one->next = head[pos].next;
head[pos].next = one;
}
}