题目描述
blablabla
样例
//拉链法
/*#include <iostream>
#include <cstring>
using namespace std;
const int N=100003;
int n;
int h[N];//存储下一个结点的下标
int e[N],ne[N],idx;//拉链法
void insert(int x){
int k=(x%N+N)%N;//x在哈希表中的下标
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool query(int x){
int k=(x%N+N)%N;//x在哈希表中的下标
for(int i=h[k];i!=-1;i=ne[i]){//在单链表中查找
if(e[i]==x) return true;
}
return false;//这个要写在循环外面
}
int main(){
cin>>n;
memset(h,-1,sizeof h);//初始化,把头结点下标都初始化为-1;因为在单链表中只有一个头结点所以不需要用menset函数来初始化
while(n--){
char op;
int x;
cin>>op;
if(op=='I'){//注意这里是单引号
cin>>x;
insert(x);
}else{
cin>>x;
if(query(x)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}*/
//开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N=100003;
const int null=0x3f3f3f3f;
int n;
int h[N];
int find(int x){//x存在返回x的下标,不存在返回它应该存储的位置
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x){
k++;
if(k==N) k=0;//k到最后一个位置后从起点开始查找
}
return k;
}
int main(){
cin>>n;
memset(h,0x3f,sizeof h);
while(n--){
char op;
int x;
cin>>op>>x;
int k=find(x);
if(op=='I'){//注意这里是单引号
h[k]=x;
}else{
if(h[k]!=null) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}