本文共 1682 字，大约阅读时间需要 5 分钟。

集合(normal)

Time Limit:2000MS Memory Limit:65536K

Total Submit:741 Accepted:241

Description

给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 109，并且每个集合的元素个数不大于105。我们希望求出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!”

Input

输入有两行，分别表示两个集合，每行的第一个整数为这个集合的元素个数（至少一个），然后紧跟着这个集合的元素（均为不同的正整数）

Output

只有一行，就是A、B的关系。

Sample Input

样例1

2 55 272 55 27

样例2

3 9 24 19952 9 24

样例3

3 1 2 34 1 2 3 4

样例4

3 1 2 33 4 5 6

样例5

2 1 22 2 3

Sample Output

样例1

A equals B

样例2

B is a proper subset of A

样例3

A is a proper subset of B

样例4

A and B are disjoint

样例5

I'm confused!

分析：

就是判断存在关系的问题

可哈希表 也可二分查找

哈希表方式：

很明显的可以用哈希表来判断是否存在

CODE：

#include
   
    #include
    
     #include
     
      #define prime 149993 //取余质数using namespace std;int n,m,a[prime],s,sum;int hash(int x){
   	return x%prime; //哈希}int locate(int x){
   	int q=hash(x),i=0;	while(i
     
    
   

二分方式：

直接二分查找即可

CODE：

#include
   
    #include
    
     #include
     
      #pragma GCC optimize(2)using namespace std;int a[100001],n,m,sum,s;void brina(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+n+1);  //排序	scanf("%d",&m);	for(int i=1;i<=m;i++){
   		scanf("%d",&s);		brina(s);  //查找	} 	if(sum==n&&n==m) cout<<"A equals B";//逻辑判断	else if(sum==m) cout<<"B is a proper subset of A";	else if(sum==n) cout<<"A is a proper subset of B";	else if(!sum) cout<<"A and B are disjoint";	else cout<<"I'm confused!";		return 0;}