福州网站开发招聘,电商沙盘seo裤子关键词,国内做的比较好的旅游网站,网络推广的方法包括维护一个集合#xff0c;支持如下几种操作#xff1a;
I x#xff0c;插入一个整数 x #xff1b; Q x#xff0c;询问整数 x 是否在集合中出现过#xff1b; 现在要进行 N 次操作#xff0c;对于每个询问操作输出对应的结果。
输入格式 第一行包含整数 N #xff0c…维护一个集合支持如下几种操作
I x插入一个整数 x Q x询问整数 x 是否在集合中出现过 现在要进行 N 次操作对于每个询问操作输出对应的结果。
输入格式 第一行包含整数 N 表示操作数量。
接下来 N 行每行包含一个操作指令操作指令为 I xQ x 中的一种。
输出格式 对于每个询问指令 Q x输出一个询问结果如果 x 在集合中出现过则输出 Yes否则输出 No。
每个结果占一行。
数据范围 1≤N≤105
−109≤x≤109 输入样例 5 I 1 I 2 I 3 Q 2 Q 5
#include iostream
#include cstringusing namespace std;const int N 100003;int n;
int h[N], e[N], ne[N], idx;
//h是哈希表头结点数组、e是元素数组、ne是链表中下一个元素的索引
/*h 数组是哈希表的数组每个元素表示一个桶。
h[k] 存储的是第 k 个桶的头结点即链表中第一个元素的索引。存的拉链的头结点的下标
e 数组存储具体的元素值每个元素值对应一个索引。
ne 数组存储链表中每个元素的下一个元素的索引。
idx 是当前要插入的元素的索引。*/void insert(int x)
{// 计算哈希值使用取模运算防止越界int k (x % N N) % N; // x % N x是负数的话保证这个哈希函数映射一定是正数// 插入到哈希表中使用链地址法处理哈希冲突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()
{scanf(%d, n);memset(h, -1, sizeof h);// 初始化哈希表的头结点为 -1表示空链表while(n -- ){char op[2];int x;scanf(%s%d, op, x);if(op[0] I){insert(x);}else{if(find(x)) printf(Yes\n);else printf(No\n);}}return 0;
}
