bzoj 1567: [JSOI2008]Blue Mary的战役地图 （二分+hash）

Description

Input

Output

Sample Input

Sample Output

HINT

样例解释：子矩阵：5 68 9为两个地图的最大公共矩阵约定：n<=50

Source

题解：二分+hash

二分答案，然后利用hash值判定，做法十分的暴力，但是时间复杂度不是严格的，所以过掉了。

其实可以预处理出第一个大矩阵的所以小矩阵，然后二分查找。

#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdio>#define ull unsigned long long#define p 2000001001#define N 53using namespace std;ull a[N][N][N],b[N][N][N],mi[N];int mpa[N][N],mpb[N][N],n;bool check(int x){	for (int i=1;i<=n-x+1;i++)	 for (int j=1;j<=n-x+1;j++)	  for (int k=1;k<=n-x+1;k++)	   for (int l=1;l<=n-x+1;l++) {	   	 bool pd=true;	   	 for (int t=1;t<=x;t++) 	   	 	if (a[i+t-1][j][j+x-1]!=b[k+t-1][l][l+x-1]) {	   	 	 //cout<<a[i][j][j-x+1]<<" "<<b[k][l][l+x-1]<<endl;	   	 	 pd=false;			 break;	 		    }		// if (pd) cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;		 if (pd) return 1;	   }	return 0;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d",&n);	for (int i=1;i<=n;i++) 	 for (int j=1;j<=n;j++) scanf("%d",&mpa[i][j]);	for (int i=1;i<=n;i++)	 for (int j=1;j<=n;j++) scanf("%d",&mpb[i][j]);	for (int i=1;i<=n;i++)	 for (int j=1;j<=n;j++) {	 	a[i][j][j]=mpa[i][j]*p;	 	for (int k=j+1;k<=n;k++)	 	 a[i][j][k]=a[i][j][k-1]*p+mpa[i][k];	 }	for (int i=1;i<=n;i++) 	 for (int j=1;j<=n;j++) {	 	b[i][j][j]=mpb[i][j]*p;	 	for (int k=j+1;k<=n;k++) 	 	 b[i][j][k]=b[i][j][k-1]*p+mpb[i][k];	 }	int l=1; int r=n; int ans=0;	while (l<=r) {		int mid=(l+r)/2;		if (check(mid)) ans=max(ans,mid),l=mid+1;		else r=mid-1;	}	PRintf("%d/n",ans);}