被虐爆了 cry 我的hash是真的菜啊。。。
poj3349 肝了一个上午心态崩了。。。一上午fail了42次我的天，一开始搞了个排序复杂度多了个log，而且是那种可能不同值相等的hash，把12种情况枚举，TLE了，然后就用了那种栈循环的hash，又T又W，期间大力搞大质数想要各个不同的雪花hash值不同，然后改成链表，最后一怒之下把最小表示法删了换暴力就A了。。想了想是因为我以为它的角度不会重复然后就偷了一波懒。。。这道题告诉我，假如重复还是得管的。。。hash应该作为一个筛选的工具。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; int next[210000],last[110000]; int len,hash[110000][7],key[110000]; int c[10]; bool check(int k) { for(int i=1;i<=6;i++) { bool bk=true; for(int j=1;j<=6;j++) if(hash[k][j]!=c[(i+j-2)%6+1]){bk=false;break;} if(bk==true)return true; } for(int i=1;i<=6;i++) { bool bk=true; for(int j=1;j<=6;j++) if(hash[k][j]!=c[(i+(6-j+1)-2)%6+1]){bk=false;break;} if(bk==true)return true; } return false; } bool calc() { int d=0; for(int i=1;i<=6;i++)d+=c[i]; int x=d%99991; for(int k=last[x];k;k=next[k]) if(key[k]==d&&check(k)==true)return true; key[++len]=d; for(int i=1;i<=6;i++)hash[len][i]=c[i]; next[len]=last[x]; last[x]=len; return false; } int main() { int n; scanf("%d",&n);len=0;memset(last,0,sizeof(last)); memset(key,0,sizeof(key)); for(int i=1;i<=n;i++) { for(int j=1;j<=6;j++)scanf("%d",&c[j]); if(calc()==true){printf("Twin snowflakes found. ");return 0;} } printf("No two snowflakes are alike. "); return 0; }
兔子与兔子 这个还是简单一点的，加深了对于mod之后的运算的满足的理解吧。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int s[1100000],Bin[1100000]; char ss[1100000]; int main() { scanf("%s",ss+1);int len=strlen(ss+1); s[0]=0;Bin[0]=1; for(int i=1;i<=len;i++) Bin[i]=Bin[i-1]*27, s[i]=s[i-1]+Bin[i]*(ss[i]-'a'); int Q,l,r; scanf("%d",&Q); while(Q--) { scanf("%d%d",&l,&r); int d1=(s[r]-s[l-1])*Bin[len-r]; scanf("%d%d",&l,&r); int d2=(s[r]-s[l-1])*Bin[len-r]; if(d1==d2)printf("Yes "); else printf("No "); } return 0; }
poj3974 马拉车原问题多个log的hash做法。。就是对于每个点二分回文的长度，然后判断是否匹配
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int len; int Bin[1100000],zh[1100000],fh[1100000]; bool check(int i,int mid) { int l1=i-mid+1,r1=i; int l2=i,r2=i+mid-1; int d1=(zh[r1]-zh[l1-1])*Bin[len-r1]; int d2=(fh[l2]-fh[r2+1])*Bin[l2-1]; return d1==d2; } bool check2(int i,int mid) { int l1=i-mid+1,r1=i; int l2=i+1,r2=(i+1)+mid-1; int d1=(zh[r1]-zh[l1-1])*Bin[len-r1]; int d2=(fh[l2]-fh[r2+1])*Bin[l2-1]; return d1==d2; } char ss[1100000]; int main() { int T_T=0; while(scanf("%s",ss+1)!=EOF) { len=strlen(ss+1); if(ss[1]=='E'&&ss[2]=='N'&&ss[3]=='D'&&len==3)break; printf("Case %d: ",++T_T); Bin[0]=1;zh[0]=0;fh[len+1]=0; for(int i=1;i<=len;i++) Bin[i]=Bin[i-1]*27, zh[i]=zh[i-1]+Bin[i]*(ss[i]-'a'+1); for(int i=len;i>=1;i--) fh[i]=fh[i+1]+Bin[len-i+1]*(ss[i]-'a'+1); int mmax=0; for(int i=1;i<=len;i++) { int l=1,r=min(i,len-i+1),ans=1; while(l<=r) { int mid=(l+r)/2; if(check(i,mid)==true) { ans=mid; l=mid+1; } else r=mid-1; } mmax=max(mmax,ans*2-1); if(i!=len) { l=1,r=min(i,len-(i+1)+1),ans=0; while(l<=r) { int mid=(l+r)/2; if(check2(i,mid)==true) { ans=mid; l=mid+1; } else r=mid-1; } mmax=max(mmax,ans*2); } } printf("%d ",mmax); } return 0; }
后缀数组 后缀数组原问题多个log的hash做法，做到这题感觉hash写得很顺啊，调都没调就过了，具体做法是这样的，对于sa，我归并排序下标（其实就是对应后缀），然后用二分+hash搞出要比较大小的后缀的前缀，比较它们前缀的后一位就知道那个后缀较小了。height同理二分+hash可得
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int len;char ss[310000]; int ha[310000],Bin[310000]; bool check(int l1,int l2,int L) { int r1=l1+L-1,r2=l2+L-1; int d1=(ha[r1]-ha[l1-1])*Bin[len-r1]; int d2=(ha[r2]-ha[l2-1])*Bin[len-r2]; return d1==d2; } bool bijiao(int x,int y) { int l=0,r=len-max(x,y)+1,ans=0; while(l<=r) { int mid=(l+r)/2; if(check(x,y,mid)==true) { ans=mid; l=mid+1; } else r=mid-1; } return ss[x+ans]<ss[y+ans]; } int id[310000],tt[310000]; void mergesort(int l,int r) { if(l==r)return ; int mid=(l+r)/2; mergesort(l,mid);mergesort(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid&&j<=r) { if(bijiao(id[i],id[j])==true) tt[p++]=id[i++]; else tt[p++]=id[j++]; } while(i<=mid)tt[p++]=id[i++]; while(j<=r) tt[p++]=id[j++]; for(int i=l;i<=r;i++)id[i]=tt[i]; } int main() { scanf("%s",ss+1),len=strlen(ss+1); Bin[0]=1; for(int i=1;i<=len;i++) Bin[i]=Bin[i-1]*27, ha[i]=ha[i-1]+Bin[i]*(ss[i]-'a'+1); for(int i=1;i<=len;i++)id[i]=i; mergesort(1,len); for(int i=1;i<len;i++)printf("%d ",id[i]-1); printf("%d ",id[len]-1); printf("0"); for(int i=2;i<=len;i++) { int l=0,r=len-max(id[i-1],id[i])+1,ans=0; while(l<=r) { int mid=(l+r)/2; if(check(id[i-1],id[i],mid)==true) { ans=mid; l=mid+1; } else r=mid-1; } printf(" %d",ans); } printf(" "); return 0; }
总结一下，hash的用途在判定相等而不支持大小比较，好像很适配于二分把问题转成判定性问题以后？
补基础的伪老年选手yzh好菜啊，一天才一章。。