2147 数星星

2018-06-17 22:16:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 

题目描述 Description

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

5

1 5 5 4 1

样例输出 Sample Output

00101

数据范围及提示 Data Size & Hint

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

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

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

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

100%的数据,0<n≤500000;-2000000000≤W≤2000000000。

 

 题解:

看本题数据就知道,暴力是是无法过的(数组开不到那么大)。本题用哈希表就能过,不过本题要处理负数的情况。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int hashsize=100000+7;
int read()
{
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n;
vector<int> hs[hashsize]; 
int h(int x)
{
    int tmp=x%hashsize;
    if(tmp<0) tmp=-tmp;
    return tmp;
}
bool ok(int x)
{
    int s=h(x);
    int len=hs[s].size();
    for(int i=0;i<len;i++)
    {
        if(hs[s][i]==x) return 0;
    }
    hs[s].push_back(x);
    return 1;
}
int main()
{
    n=read();
    int x;
    for(int i=1;i<=n;i++)
    {
        x=read();
        if(ok(x)) printf("%d",0);
        else printf("%d",1);
    }
    return 0;
}
    

稍加改动,就可以变成邻接表版的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500000+5;
const int hashsize=100000+7;
int read()
{
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n,head[hashsize],num;
struct hash
{
    int next,to;
}hs[maxn];//注意边的的多少与是与n的值有关
int h(int x)
{
    int tmp=x%hashsize;
    if(tmp<0) tmp=-tmp;
    return tmp;
}
bool ok(int x)
{
    int s=h(x);
    for(int i=head[s];i;i=hs[i].next)
    if(hs[i].to==x) return 0;
    hs[++num].next=head[s];
    hs[num].to=x;
    head[s]=num;
    return 1;
}
int main()
{
    n=read();
    int x;
    for(int i=1;i<=n;i++)
    {
        x=read();
        if(ok(x)) printf("%d",0);
        else printf("%d",1);
    }
    return 0;
}

 

以上两种在codevs上提交均在600ms左右。

还有一种是用STL中的pb_ds库做的,代码很简单,速度接近手打哈希。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<int,bool>h;
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        printf("%d",h[x]);
        h[x]=1; 
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1112 波浪数

下一篇:P1280 尼克的任务