「CODEVS1230」元素查找
题目描述 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（这是一个没有解决冲突的哈希版本，若要保证正确的话可以把相同哈希值的元素用链表串起来）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define inf 1000000000 #define ll long long #define mod 9875321 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int mp[10000005]; int gethash(int x) { return x%mod; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { int x=read(); mp[gethash(x)]=1; } for(int i=1;i<=m;i++) { int x=read(); if(mp[gethash(x)])puts("YES"); else puts("NO"); } return 0; } |
多重哈希
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int mod[3]={10007,1000007,9875321}; int n,m; int mp[3][10000005]; int gethash(int x,int t) { return x%mod[t]; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { int x=read(); mp[0][gethash(x,0)]=mp[1][gethash(x,1)]=mp[2][gethash(x,2)]=1; } for(int i=1;i<=m;i++) { int x=read(); if(mp[0][gethash(x,0)]&&mp[1][gethash(x,1)]&&mp[2][gethash(x,2)])puts("YES"); else puts("NO"); } return 0; } |
map
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; map<int,int>mp; int main() { n=read();m=read(); for(int i=1;i<=n;i++) { int x=read(); mp[x]=1; } for(int i=1;i<=m;i++) { int x=read(); if(mp[x])puts("YES"); else puts("NO"); } return 0; } |
Subscribe
计数器 9786089
OI 课件=>
OI 课件=>