本文共 1312 字，大约阅读时间需要 4 分钟。

题目大意

给2个正方形，求最大公共子正方形的边长。

思路

显然可以通过二维hash+二分答案+暴力枚举达到目的

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int a[1001][1001],b[1001][1001],ans;int n,m;unsigned long long ha[1001][1001],hb[1001][1001],p[1001],p2[1001];//数组开大又不会死bool check(int x,int y,int l){   	if (x>n||y>m||x
       
        
         n||yy>m) continue; bb=hb[xx][yy]-hb[xx][yy-l]*p[l]-hb[xx-l][yy]*p2[l]+hb[xx-l][yy-l]*p[l]*p2[l]; if (bb==aa) return 1; } } return 0;}int main(){ cin>>n; m=n; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin>>a[i][j]; } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin>>b[i][j]; } } p2[0]=p[0]=1; for (int i=1;i<=1000;i++) p[i]=97*p[i-1],p2[i]=13331*p2[i-1]; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { ha[i][j]=ha[i][j-1]*97+a[i][j]; hb[i][j]=hb[i][j-1]*97+b[i][j]; } } for (int i=2;i<=n;i++) { for (int j=1;j<=m;j++) { ha[i][j]=ha[i-1][j]*13331+ha[i][j]; hb[i][j]=hb[i-1][j]*13331+hb[i][j]; } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { int l=1,r=n+m,mn=0; while (l<=r) { int mid=(l+r)>>1; if (check(i+mid,j+mid,mid*2+1)) l=mid+1,mn=max(mn,mid*2+1); else r=mid-1; } ans=max(ans,mn); l=1,r=n+m,mn=0; while (l<=r) { int mid=(l+r)>>1; if (check(i+mid,j+mid,mid*2)) l=mid+1,mn=max(mn,mid*2); else r=mid-1; } ans=max(ans,mn); } } cout<