首页 > 代码库 > hash 表 | | jzoj 1335 | | 脑残+手残 | | 集合的关系
hash 表 | | jzoj 1335 | | 脑残+手残 | | 集合的关系
给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 10^9，并且每个集合的元素个数不大于10^5。我们希望求出A、B之间的关系。
给定两个集合的描述，判断它们满足下列关系的哪一种：
A是B的一个真子集，输出“A is a proper subset of B”
B是A的一个真子集，输出“B is a proper subset of A”
A和B是同一个集合，输出“A equals B”
A和B的交集为空，输出“A and B are disjoint”
上述情况都不是，输出“I‘m confused!”
***************************************************************
哈希表的线性探测法，比较ab数组项数多少，然后对a（b）数组进行插入，b（a）数组进行查找，flag用于查询即可
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<ctime>using namespace std;const int maxprime=1000003;const int step=7;const int N=1000000;struct nums{ int val,sum;}hash[N];int m,n;int find(int x){ int temp=x%maxprime; while(hash[temp].val!=0&&hash[temp].val!=x) { temp+=step; if(temp>=maxprime) temp-=maxprime; } return temp;}bool flag1=0,flag2=0;void insert(int x){ int now=find(x); hash[now].val=x; return ;}void judge(int x){ int now=find(x); if(hash[now].val==x) flag1=1; else flag2=1;}int a[N],b[N];int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int i=1; ios::sync_with_stdio(false); cin>>m; for(int i=1;i<=m;i++) cin>>a[i]; cin>>n; for(int j=1;j<=n;j++) cin>>b[j]; if(m<n) { for(int i=1;i<=n;i++) insert(b[i]); for(int i=1;i<=m;i++) judge(a[i]); if(flag1==1&&flag2==0) {cout<<"A is a proper subset of B"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/return 0;} if(flag1==0&&flag2==1) {cout<<"A and B are disjoint"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/return 0;} } if(m>n) { for(int j=1;j<=m;j++) insert(a[j]); for(int i=1;i<=n;i++) judge(b[i]); if(flag1==1&&flag2==0) {cout<<"B is a proper subset of A"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/return 0;} if(flag1==0&&flag2==1) {cout<<"A and B are disjoint"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/return 0;} } if(m==n) { for(int i=1;i<=m;i++) insert(a[i]); for(int j=1;j<=n;j++) judge(b[j]); if(flag1==1&&flag2==1) {cout<<"A equals B"<<endl;return 0;} if(flag1==0&&flag2==1) {cout<<"A and B are disjoint"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/return 0;} } cout<<"I‘m confused!"<<endl; /*cout<<"THE TIME HAS PASSED: "<<clock()<<" ms"<<endl;*/ return 0; }
hash 表 | | jzoj 1335 | | 脑残+手残 | | 集合的关系
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。