首页 > 学院 > 开发设计 > 正文

集合B(哈希表模板题)

2019-11-08 03:00:13
字体:
来源:转载
供稿:网友

题目: 给定两个集合 A、B,集合内的任一元素 x 满足 1≤x≤109,并且每个集合的元素个数不大于107。我们希望求出 A、B 之间的关系,只需确定在 B 中但是不在 A 中的元素的个数即可。

输入: 输入文件有两行,分别表示两个集合,每行的第一个整数为这个集合的元素个数(至少一个),然后紧跟着这个集合的元素(均为不同的正整数)。

输出: 输出文件只有一个整数,即在 B 中但是不在 A 中的元素的个数即可。

EG.1: in: 2 55 27 2 55 27 out: 0

EG.2: in: 3 9 24 1995 2 9 24 out: 0

EG.3 in: 3 1 2 3 4 1 2 3 4 out: 1

EG.4: in: 3 1 2 3 3 4 5 6 out: 3

EG.5: in: 2 1 2 2 2 3 out: 1


#include<iostream>#include<algorithm>#include<cctype>#include<cstdio>#include<cstring>#include<ctime>#include<cmath>#include<queue>using namespace std;int n,m;int a,b;int hx[10000010];inline int haxi(int x){ int num=x%1588991; while(hx[num]!=x&&hx[num]!=0) ++num; return num;}inline bool check(int x){ if(hx[haxi(x)]==x) return true; else return false;}int main(){ cin>>n; for(int i=1;i<=n;++i) { cin>>a; hx[haxi(a)]=a; } cin>>m; int ans=m; for(int i=1;i<=m;++i) { cin>>b; if(check(b)) ans--; } cout<<ans; return 0;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表