本文主要是介绍SSL_1125 集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出两个集合，求出它们之间的关系：
1、A是B的一个真子集，输出“A is a proper subset of B”
2、B是A的一个真子集，输出“B is a proper subset of A”
3、A和B是同一个集合，输出“A equals B”
4、A和B的交集为空，输出“A and B are disjoint”
5、上述情况都不是，输出“I'm confused!”
2、B是A的一个真子集，输出“B is a proper subset of A”
3、A和B是同一个集合，输出“A equals B”
4、A和B的交集为空，输出“A and B are disjoint”
5、上述情况都不是，输出“I'm confused!”
思路：
这道题有两种做法：1、用快排加二分查找 2、用哈希表来查找
代码：
1：
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100001],n,s,sum,n1;
void ef(int x)
{int l=1,r=n,mid;while (l<=r){mid=(l+r)>>1;if (a[mid]==x) {sum++;return;}if (a[mid]>x) r=mid-1;else l=mid+1;}
}int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);scanf("%d",&n1);for (int i=1;i<=n1;i++){scanf("%d",&s);ef(s);}//二分查找两个集合中相同的个数if (sum==n&&n==n1) printf("A equals B");//输出else if (sum==n1) printf("B is a proper subset of A");else if (sum==n) printf("A is a proper subset of B");else if (!sum) printf("A and B are disjoint");else printf("I'm confused!");
}
#include<cstdio>
#define p 149993
using namespace std;
int n,n1,a[p],sum,s;
int hash(int x)
{return x%p;
}
int dw(int x)//定位
{int w=hash(x),i=0;while (i<p&&a[(i+w)%p]&&a[(i+w)%p]!=x)i++;return (i+w)%p;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&s);a[dw(s)]=s;//存到哈希表里}scanf("%d",&n1);for (int i=1;i<=n1;i++){scanf("%d",&s);sum+=a[dw(s)]==s;//这句意思是，如果哈希表中有s的话就让sum加一}if (sum==n&&n==n1) printf("A equals B");//输出else if (sum==n1) printf("B is a proper subset of A");else if (sum==n) printf("A is a proper subset of B");else if (!sum) printf("A and B are disjoint");else printf("I'm confused!");
}
这篇关于SSL_1125 集合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
