【codevs1230】元素查找

2016年6月11日1,6401

题目描述 Description

给出n个正整数,然后有m个询问,每个询问一个整数,询问该整数是否在n个正整数中出现过。

输入描述 Input Description

第一行两个整数 n 和m。

第二行n个正整数(1<=n<= 100000)

第三行m个整数(1<=m<=100000)

输出描述 Output Description

一共m行,若出现则输出YES,否则输出NO

样例输入 Sample Input

4 2

2 1 3 4

1 9

样例输出 Sample Output

YES

NO

数据范围及提示 Data Size & Hint

所有数据都不超过10^8

<:SECTION id=statistics>

题解

这是一道哈希表的入门题,要求实现插入和查询,可以直接将大数取模一个质数作为key

为什么模数为质数可以减少冲突的可能?(建议思考 or 使用搜索引擎)

当然我们可以多重哈希(用多个哈希值一起判断),或者直接使用stl中的map

hash(这是一个没有解决冲突的哈希版本,若要保证正确的话可以把相同哈希值的元素用链表串起来)

多重哈希

map