题目描述

维护一个集合，支持如下几种操作：

I x，插入一个数 x；
Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109

样例

5
I 1
I 2
I 3
Q 2
Q 5

结果

Yes
No

算法1 开放寻址法 找坑法

注意 开数组要大2到3倍 N为质数

#include <cstring>
#include <iostream>

using namespace std;
const int null=0x3f3f3f3f;
const int N=2*1e5+3; //大于数据范围的 第一个质数
int n;
int h[N];

int find(int x)  //找x的坑位
{
   int t=(x%N+N)%N;
   while(h[t]!=null&&h[t]!=x)
   {
           t++;
           if(t==N)  //收尾相连构成一个环 如果找到最后没有就从头开始
           t=0;

   }
   return t;      //返回坑的位置
} 

int main() {
     cin.tie(0);
   memset(h,0x3f,sizeof(h));
    cin >> n;
    while(n--)
    {
            char op;
            int x;
            cin>>op;
            if(op=='I')
           {
                   cin>>x;
                   h[find(x)]=x;  //find（x）是x的坑位 再赋值

           }
           else
           {         cin>>x;
                   if(h[find(x)]==null)  //如果找到的坑位没被赋值 则输出No
                   puts("No");
                   else
                   puts("Yes");
           }
    }

    return 0;
}