codevs2147数星星（哈希）

2147 数星星

时间限制: 3 s

空间限制: 64000 KB

题目等级 : 钻石 Diamond

题目描述 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。

分类标签 Tags

哈希表线性结构

/*

对于哈希，我只是一个小小的初学者，所以这道题搞了好久才大体明白...

这是一个比较好的哈希题，但我至今没搞明白怎么让它mod素数后重复读的概率低

双哈希又不会写，好伤心2333

还有我写了一个哈希表，爆空间QwQ...

痛苦哇！！！！

*/

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

#define mod 500009//大于50万的最小素数

long long hash[mod*];

int n,w[mod];

int main()

{

    memset(hash,-,sizeof(hash));//赋最小值

    scanf("%d",&n);

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

    {

        scanf("%d",&w[i]);

        int k=abs(w[i])%mod;//字符下标非负

        bool flag=;

        while(hash[k]>=-)

        {

            if(hash[k]==w[i])

               flag=;//是否已经看过

            k++;

        }

        hash[k]=w[i];//往后放到空位置

        if(flag)

          printf("");

        else

          printf("");

    }

    return ;

}

心若向阳，无言悲伤

巴特西

codevs2147数星星（哈希）

2147 数星星

分类标签 Tags

最新文章

热门文章