SSL_1125_集合_HASH

发布于 2019-04-23  930 次阅读


题目大意

求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!”

思路

用hash存,然后判断b中有多少个数在a中就可以了

#include 
#define empty 0x7fffffff
#define p 10000007
int a[p+1],h[p+1],ans=0;
int insert(int x)
{
    int i=x%p;
    while (h[i]!=0) i=(i+1)%p;
    h[i]=x;
}
int find(int x)
{
    int i=x%p;
    while (h[i]!=0&&h[i]!=x) i=(i+1)%p;
    if (h[i]==x) ans++;
}
int main()
{
    int n,m;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        insert(a[i]);
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        find(a[i]);
    }
    if (n
]]>