SSL 2482_上海红茶馆_hash

发布于 2019-05-18  7 次阅读


题目描述

你现在正在经营一家红茶馆, 而且这里有各种各样的红茶, 你现在把这些红茶分成了N个等级, 每个等级的茶有一个品质Q。
现在每一个来的客人都会要求一个品质为S的茶, 你需要迅速的回答他是否有。


思路

看数据范围就知道肯定不是开个桶就可以的题
所以就开个hash就可以了
随便搞搞


#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) return 1;
    return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        insert(x);
    }
    for (int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        if (find(x)) printf("Y");
        else printf("N");
    }
}
]]>