时间限制: 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
分类标签 Tags 点此展开
哈希60分RE代码 head数组开小了
#include <iostream>
#include <cstring>
#include <cstdio>
#define mo1 12421
#define mo2 34343
using namespace std; struct node
{
int next;
int to;
}e[];
int n,m,i,j,tot,head[];
void add(int u,int v)
{
tot++;
e[tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
int get_hash(int k)
{
int h=;
while(k)
{
h=h*+k%;
k/=;
}
return h%mo2;
}
bool query(int u,int v)
{
for(int i=head[u];i;i=e[i].next)
{
if(e[i].to==v)
return true;
}
return false;
}
int main()
{
int a;
cin>>n>>m;
while(n--)
{
cin>>a;
int y=get_hash(a);
add(a,y);
}
while(m--)
{
cin>>a;
int y=get_hash(a);
if(query(a,y))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
哈希满分做法
#include <iostream>
#include <cstring>
#include <cstdio>
#define mo1 12421
#define mo2 34343
using namespace std; struct node
{
int next;
int to;
}e[];
int n,m,i,j,tot,head[];
void add(int u,int v)
{
tot++;
e[tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
int get_hash(int k)
{
int h=;
while(k)
{
h=h*+k%;
k/=;
}
return h%mo2;
}
bool query(int u,int v)
{
for(int i=head[u];i;i=e[i].next)
{
if(e[i].to==v)
return true;
}
return false;
}
int main()
{
int a;
cin>>n>>m;
while(n--)
{
cin>>a;
int y=get_hash(a);
add(a,y);
}
while(m--)
{
cin>>a;
int y=get_hash(a);
if(query(a,y))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
STL满分做法
#include<map>
#include<iostream>
using namespace std;
int s[];
map<int,bool>g;
int main()
{
int n,m,ss;
cin>>n>>m;
for(int i=;i<=n;++i)
{
cin>>s[i];
g[s[i]]=;
}
for(int i=;i<=m;++i)
{
cin>>ss;
if(g[ss]==)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}