描述

---

...

 

1230 元素查找

 

 

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

 

 

 

 

 

 

 

题目描述

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

 

 

分析

---

就是见识了一下简单的Hash是啥...set也可以做(其实我也不会用set).

给出一组数,查找其中是否存在某一个数x.很容易想到搞个桶,但是数字如果很大,比如整型上限,桶就开不下了,可以离散处理(以前一直用的自己脑补的离散方法).用Hash的话就是:假设共n个数,则记mod为任意一个大于等于n的数,这样x%mod在[0,mod-1],至少有n种不同的值,然后以模作为数组下标,如果已经被占了就往后走.查找的时候也是,如果被其他数占了就往后走,如果走到空的还没有找到,说明没有这个数(如果有就会占到空位).

set:

1 #include 
      
        2 #include 
       
         3 using namespace std; 4  5 int n,m,x; 6 int main(){ 7     scanf("%d%d",&n,&m); 8     set 
        
          s; 9     for(int i=1;i<=n;i++) scanf("%d",&x),s.insert(x);10     for(int i=1;i<=m;i++) scanf("%d",&x),s.count(x)?puts("YES"):puts("NO");11     return 0;12 }
        
       
      

Hash:

1 #include 
      
        2  3 const int mod=1e5+7; 4 int a[mod]; 5 inline void insert(const int &x){ for(int k=x%mod;a[k]!=x;k=(k+1)%mod) if(!a[k]) { a[k]=x; return; } } 6 inline bool search(const int &x){ for(int k=x%mod;a[k]!=x;k=(k+1)%mod) if(!a[k]) return false; return true;} 7  8 int n,m,x; 9 int main(){10     scanf("%d%d",&n,&m);11     for(int i=1;i<=n;i++) scanf("%d",&x),insert(x);12     for(int i=1;i<=m;i++) scanf("%d",&x),search(x)?puts("YES"):puts("NO");13     return 0;14 }15 16 Hash