首页 > 代码库 > codevs 2147 数星星
codevs 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
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。
哈希 点击传送
33分 WA+RE代码存档 （数组开小，没考虑负数）
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#define mo 13831using namespace std;int tot,head[100001],n,i,w;struct node{ int next,to;}e[100001];bool hash(int k){ int h=0; while(k) { h=h*13+k; k/=10; } h=h%mo; for(i=head[h];i;i=e[i].next) { if(e[i].to==w) return true; } tot++; e[tot].next=head[h]; e[tot].to=w; head[h]=tot; return false;}int main(){ cin>>n; while(n--) { cin>>w; if(hash(w)) cout<<"1"; else cout<<"0"; }}/*运行结果测试点#1.in 结果:AC 内存使用量: 492kB 时间使用量: 13ms 测试点#2.in 结果:AC 内存使用量: 364kB 时间使用量: 13ms 测试点#3.in 结果:AC 内存使用量: 360kB 时间使用量: 13ms 测试点#4.in 结果:RE 内存使用量: 876kB 时间使用量: 33ms 测试点#5.in 结果:RE 内存使用量: 872kB 时间使用量: 61ms 测试点#6.in 结果:WA 内存使用量: 1260kB 时间使用量: 142ms 测试点#large.in 结果:RE 内存使用量: 872kB 时间使用量: 58ms 测试点#large2.in 结果:RE 内存使用量: 360kB 时间使用量: 9ms 测试点#large3.in 结果:RE 内存使用量: 616kB 时间使用量: 16ms */
66分 RE代码 （数组开小）
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#define mo 13831using namespace std;int tot,head[100001],n,i,w;struct node{ int next,to;}e[100001];bool hash(int k){ int h=0; while(k) { h=h*13+k; k/=10; } h=h%mo; if(h<0) h=h*(-1); h+=233;//应该随便加一个质数就好 。 for(i=head[h];i;i=e[i].next) { if(e[i].to==w) return true; } tot++; e[tot].next=head[h]; e[tot].to=w; head[h]=tot; return false;}int main(){ cin>>n; while(n--) { cin>>w; if(hash(w)) cout<<"1"; else cout<<"0"; }}/*运行结果测试点#1.in 结果:AC 内存使用量: 364kB 时间使用量: 12ms 测试点#2.in 结果:AC 内存使用量: 360kB 时间使用量: 11ms 测试点#3.in 结果:AC 内存使用量: 364kB 时间使用量: 11ms 测试点#4.in 结果:AC 内存使用量: 1004kB 时间使用量: 134ms 测试点#5.in 结果:AC 内存使用量: 1132kB 时间使用量: 137ms 测试点#6.in 结果:AC 内存使用量: 1260kB 时间使用量: 138ms 测试点#large.in 结果:RE 内存使用量: 2412kB 时间使用量: 298ms 测试点#large2.in 结果:RE 内存使用量: 2412kB 时间使用量: 299ms 测试点#large3.in 结果:RE 内存使用量: 2284kB 时间使用量: 293ms */
100分 哈希代码 就是太慢了 = =| 长度575B 时间5404ms
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#define mo 13831using namespace std;int tot,head[1000001],n,i,w;struct node{ int next,to;}e[1000001];bool hash(int k){ int h=0; while(k) { h=h*13+k; k/=10; } h=h%mo; if(h<0) h=h*(-1); h+=233; for(i=head[h];i;i=e[i].next) { if(e[i].to==w) return true; } tot++; e[tot].next=head[h]; e[tot].to=w; head[h]=tot; return false;}int main(){ cin>>n; while(n--) { cin>>w; if(hash(w)) cout<<"1"; else cout<<"0"; }}
100分 STL代码 更慢但简单了不只一点。。代码长度179B 时间 6559ms
#include <iostream>#include <map>using namespace std;map<int,int>q;int main(){ int n; cin>>n; int a; while(n--) { cin>>a; cout<<q[a]; q[a]=1; }}
codevs 2147 数星星
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。