codevs 2147 数星星

2147 数星星

http://codevs.cn/problem/2147/

题目描述 Description

小明是一名天文爱好者，他喜欢晚上看星星。这天，他从淘宝上买下来了一个高级望远镜。他十分开心，于是他晚上去操场上看星星。

不同的星星发出不同的光，他的望远镜可以计算出观测到的星星发出的光的数值W。小明当然想尽可能地多看到星星，于是他每看到一颗星星，就要看看他之前有没有看过这颗星星。但是他看的星星太多了，他根本数不过来，于是他让你帮忙。

输入描述 Input Description

共有两行，第一行只有一个整数，为小明观测到的星星的数量n。第二行有n个整数，每两个整数由一个空格隔开，分别为小明观测到每颗星星的光的数值W[1]-W[n]。

输出描述 Output Description

只有一行，这一行共有n个数字0或1。0表示对应的星星之前没有观测到，1表示对应的星星之前已经看过了。注意：数字之间没有空格！

样例输入 Sample Input

1 5 5 4 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

样例是往往是骗人的，本题中

30%的数据，0<n≤5000。

20%的数据，-20000≤W≤20000。

60%的数据，0<n≤50000。

100%的数据，0<n≤500000；-2000000000≤W≤2000000000。

方法一：双模哈希

取2个模数a，b，必须是质数。

设x%a=s1，x%b=s2，那么就在s1和s2之间建一条边，用链表的方式建。

所以s1可以小一点，它控制着链表中head[]或front[]的大小，但s2要大于n，不然会出现重复。

#include<iostream>

#include<cstdio>

#define f1 10007

#define f2 500009

using namespace std;

int n,cnt;

long long y;

int head[];

struct node

{

    int to,next;

}e[];

int hash1(long long a)

{

    return a%f1;

}

int hash2(long long a)

{

    return a%f2;

}

void add(int u,int v)

{

    cnt++;

    e[cnt].to=v;

    e[cnt].next=head[u];

    head[u]=cnt;

}

bool find(int u,int v)

{

    for(int i=head[u];i;i=e[i].next)

     if(e[i].to==v) return true;

    return false;

}

long long init()

{

    long long x=,f=; char c=getchar();

    while(c<''||c>'') {if(c=='-') f=-;c=getchar();}

    while(c>=''&&c<='') {x=x*+c-'';c=getchar();}

    return x*f;

}

int main()

{

    n=init();

    for(int i=;i<=n;i++)

    {

        y=init();

        y+=;

        long long h1=hash1(y);

        long long h2=hash2(y);

        bool k=find(h1,h2);

        if(k) printf("");

        else

        {

            printf("");

            add(h1,h2);

        }

    }

}

刚开始时第二个模数取了1009，521，都取小了。。。。。。

方法二：单模哈希

取一个大于n的质数a，对其取模。

设一个hash[]，存的是原数，如果hash[x%a]还没有被用过，就把x存在hash[x%a]里，如果hash[x%a]已经被用了，那就x%a加加，直至加到hash[]没有用为止，把x存进去。所以这就需要开2*n大小的hash[]。查找的时候，从h[x%a]开始找，只要h[x%a]的下一个有数，就一直找下去，直至找到没有为止。

注意hash数组要初始化为极小值

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#define mod 500009

using namespace std;

int n,x;

int hash[mod*];

int init()

{

    int x=,f=;char c=getchar();

    while(c<''||c>'') {if(c=='-') f=-;c=getchar();}

    while(c>=''&&c<='') {x=x*+c-'';c=getchar();}

    return x*f;

}

int main()

{

    n=init();

    memset(hash,-,sizeof(hash));

    for(int i=;i<=n;i++)

    {

        int x=init();

        int k=abs(x)%mod;

        bool ok=false;

        while(hash[k]>=-)

        {

            if(hash[k]==x)

           {

           　　 ok=true;

            　　break;

           }

            k++;

        }

        hash[k]=x;

        if(ok) cout<<;

        else cout<<;

    }

}

开始hash没有初始化，初始值为0，测试数据中只要0，就WA了

巴特西

codevs 2147 数星星

2147 数星星

最新文章

热门文章