不知道为啥,我死活想不到二分(楼下正解)
所以,就有了这篇题解
可以看到,这道题离暴力的距离只有一步!
就是数组开不下!!
小问答:数组开不下时,你会?
A:map
B:优化代码
C:gp_hash_table由于正在学hash,所以容易想到...
tong[本来的下标%9999999]
然后就玄学的过了。。。
ACcode
#include<bits/stdc++.h>
#define int long long
using namespace std;
char a[600][1100],b[600][1100];
int n,m,cnt;
signed tong[10000000];
unsigned long long ha[600][1100],hb[600][1100],mi[1100];
signed main(){
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]+1;
}
for(int i=1;i<=n;i++){
cin>>b[i]+1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ha[i][j]=ha[i][j-1]*13331+a[i][j]-'A'+1;
hb[i][j]=hb[i][j-1]*13331+b[i][j]-'A'+1;
}
}
mi[0]=1;
for(int i=1;i<=m+10;i++){
mi[i]=mi[i-1]*13331;
}
for(int j=1;j<=m;j++){
for(int i=1;i+j<=m;i++){
int flag=1;++cnt;
for(int l=1;l<=n;l++){
tong[(1uLL*ha[l][i+j]-ha[l][i]*mi[j]-'A'+1)%9999999]=cnt;
}
for(int l=1;l<=n;l++){
if(tong[(1uLL*hb[l][i+j]-hb[l][i]*mi[j]-'A'+1)%9999999]==cnt){
flag=0;
break;
}
}
if(flag){
cout<<j;
return 0;
}
}
}
return 0;
}
标签:Usaco2017,Genomics,600,int,题解,long,1100
From: https://www.cnblogs.com/lewisak/p/18209074