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