夏令营机试复习Day08-1
题目描述
维护一个集合,支持如下几种操作:
I x,插入一个数 x;
Q x,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
原题连接
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
输入样例
5
I 1
I 2
I 3
Q 2
Q 5
输出样例
Yes
No
C++ 代码
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long,int> PII;
const int N=2e5 + 3;
int n;
int s[N];
const int null = 0x3f3f3f3f;
vector<long> alls;
int find(long x) {
int t = (x % N + N) % N;
while (s[t] != null && s[t] != x) {
t++;
if (t == N) {
t = 0;
}
}
return t;
}
int main(){
cin>>n;
char op;
long a;
memset(s, 0x3f, sizeof s);
for(int i=0;i<n;i++){
cin>>op>>a;
int f= find(a);
if (op=='I'){
s[f]=a;
}
else{
if (s[f]!=null)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}