找球號(二）

時間限制：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

一開始用STL里面的set，超時了。后來才聽說要用哈希表。

哈希參考資料：http://blog.csdn.net/v_JULY_v/article/details/6256463

#include<cstdio> #include<cstring> const int N = 1e6 + 10; #define mod 200003 int Head[N], Next[N], Hash[N]; int top;void add(int num) {int key = num % mod; Hash[top] = num; Next[top] = Head[key]; Head[key] = top; top++; }int main() {int n, m, a;char op[10];while(~scanf("%d",&n)) {memset(Head, -1, sizeof(Head));top = 0;while(n--) {scanf("%s%d", op, &m);if(op[0] == 'A') {for(int i = 0; i < m; i++) {scanf("%d",&a);add(a);}}else {while(m--) {int flag = 0;scanf("%d",&a);for(int i = Head[a%mod]; i != -1; i = Next[i]) {if(Hash[i] == a) {flag = 1;break;}}if(flag) printf("YES\n");else printf("NO\n");}}}}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 138 找球号（二）哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。