摘要：
范围这么小可以枚举子正方形的边长。那么可以对这个矩形进行二维hash，就可以在O的时候求出任意子矩形的hash值。然后判断这些正方形的hash值有没有相同的部分就行了。需要注意的是行和列乘的hash种子值需要不同的质数，否则可能出现冲突。
题意: 求两个矩形最大公共子正方形。(n<=50)
范围这么小可以枚举子正方形的边长。那么可以对这个矩形进行二维hash，就可以在O(1)的时候求出任意子矩形的hash值。然后判断这些正方形的hash值有没有相同的
部分就行了。可以用二分来判断。
需要注意的是行和列乘的hash种子值需要不同的质数，否则可能出现冲突。
时间复杂度O(n^3logn).
# include <cstdio># include <cstring># include <cstdlib># include <iostream># include <vector># include <queue># include <stack># include <map># include <set># include <cmath># include <algorithm> using namespacestd; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-9# define MOD 1024523# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int>PII; typedef vector<int>VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long longLL; intScan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void Out(inta) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=55; //Code begin... int hash1[N][N], hash2[N][N], P[N*N], Q[N*N], n; VI a; VI::iterator it; bool check(intans){ FOR(i,ans,n) FOR(j,ans,n) { int tmp=hash2[i][j]-hash2[i-ans][j]*Q[ans]-hash2[i][j-ans]*P[ans]+hash2[i-ans][j-ans]*P[ans]*Q[ans]; it=lower_bound(a.begin(),a.end(),tmp); if (it==a.end()||*it!=tmp) continue; return true; } return false; } intmain () { scanf("%d",&n); P[0]=1; FOR(i,1,250) P[i]=P[i-1]*131; Q[0]=1; FOR(i,1,250) Q[i]=Q[i-1]*1789; FOR(i,1,n) FOR(j,1,n) scanf("%d",&hash1[i][j]), hash1[i][j]+=hash1[i][j-1]*P[1]; FOR(i,1,n) FOR(j,1,n) hash1[i][j]+=hash1[i-1][j]*Q[1]; FOR(i,1,n) FOR(j,1,n) scanf("%d",&hash2[i][j]), hash2[i][j]+=hash2[i][j-1]*P[1]; FOR(i,1,n) FOR(j,1,n) hash2[i][j]+=hash2[i-1][j]*Q[1]; intans; for (ans=n; ans>=1; --ans) { a.clear(); FOR(i,ans,n) FOR(j,ans,n) a.pb(hash1[i][j]-hash1[i-ans][j]*Q[ans]-hash1[i][j-ans]*P[ans]+hash1[i-ans][j-ans]*P[ans]*Q[ans]); sort(a.begin(),a.end()); if (check(ans)) break; } printf("%d ",ans); return 0; }