模擬散列表

維護一個集合，支持如下幾種操作：
1.“I x”，插入一個數x
2.“Q x”，詢問數x是否在集合中出現過
現在要進行N次操作，對于每個詢問操作輸出對應的結果

輸入格式

第一行包含整數N，表示操作數量
接下來N行，每行包含一個操作指令，操作指令為"I x"，"Q x"中的一種

輸出格式

對于每個詢問指令"Q x"，輸出一個詢問結果，如果x在集合中出現過，則輸出"Yes"，否則輸出"No"
每個結果占一行

數據范圍

$1\le N\le 10^5$
$?10^9\le x\le 10^9$

輸入樣例

5
I 1
I 2
Q 2
Q 5

輸出樣例

Yes
No

問題分析

$$哈希表?\begin{array}{r}存儲結構\{\begin{array}{r}開放尋址法\\ 拉鏈法\end{array}\\ \\ 字符串哈希方式\end{array}$$

AC代碼

#include<iostream>
#include<cstring>
using namespace std;const int N = 1e5 + 3;int h[N], e[N], ne[N], idx;void insert(int x) {// keep the remainder positive int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(int x) {int k = (x % N + N) % N;for(int i = h[k]; i != -1; i = ne[i])if(e[i] == x) return true;return false;
}int main() {int n;scanf("%d", &n);memset(h, -1, sizeof(h));while(n--) {char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I') insert(x);else {if(find(x)) puts("Yes");else puts("No");}}return 0;
}