转
2147 数星星
小明是一名天文爱好者，他喜欢晚上看星星。这天，他从淘宝上买下来了一个高级望远镜。他十分开心，于是他晚上去操场上看星星。
不同的星星发出不同的光，他的望远镜可以计算出观测到的星星发出的光的数值W。小明当然想尽可能地多看到星星，于是他每看到一颗星星，就要看看他之前有没有看过这颗星星。但是他看的星星太多了，他根本数不过来，于是他让你帮忙。
共有两行，第一行只有一个整数，为小明观测到的星星的数量n。第二行有n个整数，每两个整数由一个空格隔开，分别为小明观测到每颗星星的光的数值W[1]-W[n]。
只有一行，这一行共有n个数字0或1。0表示对应的星星之前没有观测到，1表示对应的星星之前已经看过了。注意：数字之间没有空格！
5
1 5 5 4 1
00101
样例是往往是骗人的，本题中
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#include #define f1 10007#define f2 500009using namespace std;int n,cnt;long long y;int head[10010];struct node{ int to,next;}e[500001];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=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x*f;}int main(){ n=init(); for(int i=1;i<=n;i++) { y=init(); y+=2000000000; long long h1=hash1(y); long long h2=hash2(y); bool k=find(h1,h2); if(k) printf("1"); else { printf("0"); 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]的下一个有数，就一直找下去，直至找到没有为止。这里不能找到就停下，因为本题对于没一个数不仅要查找，还要存储，存储就存到从x%a开始的没有数的地方。
注意hash数组要初始化为极小值
#include#include #include #include #include #define mod 500009using namespace std;int n,x;int hash[mod*2];int init(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}//若是字符直接读入下一个字符，若是负数使f=-1，则在改数前加了负号 while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}//若是数字，则让上一个输入的数乘10 return x*f;}//getchar函数getchar函数的功能是从键盘上输入一个字符。其一般形式为： getchar(); 通常把输入的字符赋予一个字符变量，构成赋值语句,只能读入一个字符int main(){ n=init();//读入优化 memset(hash,-128,sizeof(hash));//附初值成负无穷 for(int i=1;i<=n;i++) { int x=init(); int k=abs(x)%mod;// abs函数：求整数的 bool ok=false; while(hash[k]>=-2000000000) { if(hash[k]==x) ok=true; k++; } hash[k]=x; if(ok) cout<<1; else cout<<0; }}