P1387 题解

ikunTLE · 2025-12-15 22:45:05 · 题解

思路

大的正方形会包含小的正方形，故答案具有单调性是显然的。

考虑二分，二分正方形的边长。

枚举每行每列的起始位置，这样可以得到 N^2 的数量级个正方形，依次判断是否全部是 1。

判断方法可以预处理前缀和，后面就可以 \mathcal{O}(1) 判断。

时间复杂度 \mathcal{O}(N^2\log N)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,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;}
const int N=1e2+10,R=1e2;
int n,m,p[N][N];
int calc(int x_1,int y_1,int x_2,int y_2){
    return p[x_2][y_2]-p[x_1-1][y_2]-p[x_2][y_1-1]+p[x_1-1][y_1-1];
}
bool check(int len){
    for(int i=1;i<=n-len+1;++i)
        for(int j=1;j<=m-len+1;++j)
            if(calc(i,j,i+len-1,j+len-1)==len*len)
                return true;
    return false;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            bool x=read();
            p[i][j]=p[i][j-1]+p[i-1][j]-p[i-1][j-1]+x;
        }
    int l=0,r=R;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}