集合
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 27
2 55 27
样例2
3 9 24 1995
2 9 24
样例3
3 1 2 3
4 1 2 3 4
样例4
3 1 2 3
3 4 5 6
样例5
2 1 2
2 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!
题目分析
这题就是有两个集合，要判断集合的关系
关系1：两个集合一样
关系2：A集合属于B集合
关系3：B集合属于A集合
关系4：两个集合没有一个相同
关系5：除了以上关系的其他关系
解题思路
我们这题可以用hash的除余法，再加点判断，就ok了
这里我们了解一下hash的除余法
hash表
哈希表（Hash Table）作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表又叫做散列表，分为"开散列" 和"闭散列"。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的"哈希表"仅指"闭散列"，关于其他方面读者可参阅其他书籍。
基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
例1】用散列存储线性表：A=（18，75，60，43，54，90，46）。
分析：
假定选取的散列函数为：h(K)=K mod m，K为元素的关键字，m为散列表的长度，用余数作为存储该元素的散列地址。这里假定K和m均为正整数，并且m要大于等于线性表的长度n。此例n=7，故假定取m=13，则得到的每个元素的散列地址为：
h(18)=18 mod 13=5 h(75)=75 mod 13 =10
h(60)=60 mod 13=8 h(43)=43 mod 13=4
h(54)=54 mod 13=2 h(90)=90 mod 13=12
h(46)=46 mod 13=7
当然这是一个比较理想的情况。假如再往表中插入第8个元素30，h(30)=30 mod 13=4，我们会发现H[4]已经存了43，
此时就发生了冲突。我们可以从H[4]往后按顺序找一个空位置存放30，即可以把它插入到H[6]中。
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const int M=149994;
int s,A,B,a[M+6];
int h(int x)//除余
{
return x%M;
}
int cy(int x)//hash定位
{
int p=0,o=h(x);
while(a[(o+p)%M]!=0&&p<M&&a[(o+p)%M]!=x)//
p++;
return (o+p)%M;
}
int main()
{
scanf("%d",&A);
for(int i=1;i<=A;i++)
{
int x;
scanf("%d",&x);
a[cy(x)]=x;//将x赋值到定位中
}
scanf("%d",&B);
for(int i=1;i<=B;i++)
{
int x;
scanf("%d",&x);
if(a[cy(x)]==x)s++;//如果有就+1
}
if(s==A&&A==B)cout<<"A equals B";//判断
else if(s==B)cout<<"B is a proper subset of A";
else if(s==A)cout<<"A is a proper subset of B";
else if(s==0)cout<<"A and B are disjoint";
else cout<<"I'm confused!";
}
京公网安备 11010502036488号