#哈希#SSL 1125 集合

2024-02-11 06:48

文章标签 哈希 ssl 集合 1125

本文主要是介绍#哈希#SSL 1125 集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求两个集合的关系

分析：

c++ map大法快排+二分哈希比较时间
首先如果答案和两个数组的数据个数相等为同一个集合
如果和第一个相等 B包含与A 和第二个相等 A包含于B
有答案说明交集不为空否则有交集confused

map（622ms）代码

#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
int n1,n2,ans; map<int,bool>uk;
inline int ip(){char c=getchar(); int ans=0;while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){n1=ip(); for (int i=1;i<=n1;i++) uk[ip()]=1; //标记布尔数组n2=ip(); for (int i=1;i<=n2;i++) ans+=uk[ip()];//判断if (ans==n2&&ans==n1) puts("A equals B");else if (ans==n2&&ans<n1) puts("B is a proper subset of A");else if (ans==n1) puts("A is a proper subset of B");else if (!ans) puts("A and B are disjoint"); else puts("I'm confused!");return 0;
}

快排+二分（215ms）代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int a[100001],b[100001],n1,n2,ans;
inline int ip(){char c=getchar(); int ans=0;while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void pu(int &n,int *c){n=ip(); for (int i=1;i<=n;i++) c[i]=ip();}
int main(){pu(n1,a); pu(n2,b);stable_sort(a+1,a+1+n1);//对前一个数组快排for (int i=1;i<=n2;i++){int l=1,r=n1,mid;while (l<=r){//二分mid=(l+r)>>1;if (a[mid]==b[i]) break;else if (a[mid]>b[i]) r=mid-1; else l=mid+1;}if (a[mid]==b[i]) ans++;//查找到答案增加}if (ans==n2&&ans==n1) puts("A equals B");else if (ans==n2&&ans<n1) puts("B is a proper subset of A");else if (ans==n1) puts("A is a proper subset of B");else if (!ans) puts("A and B are disjoint"); else puts("I'm confused!");return 0;
}

哈希（154ms）代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define p 149993
using namespace std;
int a[p+1],n1,n2,ans;
inline int ip(){char c=getchar(); int ans=0;while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int locate(int x){int orig=x%p,i=0;while (i<p&&a[(orig+i)%p]!=x&&a[(orig+i)%p]) i++;//往后寻找return (orig+i)%p;
}
void insert(int x){a[locate(x)]=x;}
bool find(int x){return a[locate(x)]==x;}
int main(){n1=ip(); for (int i=1;i<=n1;i++) insert(ip());//插入n2=ip(); for (int i=1;i<=n2;i++) if (find(ip())) ans++;//寻找if (ans==n2&&ans==n1) puts("A equals B");else if (ans==n2&&ans<n1) puts("B is a proper subset of A");else if (ans==n1) puts("A is a proper subset of B");else if (!ans) puts("A and B are disjoint"); else puts("I'm confused!");return 0;
}