被虐爆了 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.\n");return 0;}}printf("No two snowflakes are alike.\n");return 0; } poj3349

兔子與兔子 這個還是簡單一點的，加深了對于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\n");else printf("No\n");}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\n",mmax);}return 0; } poj3974

后綴數組 后綴數組原問題多個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++];elsett[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\n",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("\n");return 0; } 后綴數組

總結一下，hash的用途在判定相等而不支持大小比較，好像很適配于二分把問題轉成判定性問題以后？

補基礎的偽老年選手yzh好菜啊，一天才一章。。

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/9254372.html

總結

以上是生活随笔為你收集整理的0x14 hash的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。