Gym 102091L Largest Allowed Area 【二分+二维前缀和】

<题目链接>

题目大意：
给你一个由01组成的矩形，现在问你，该矩形中，最多只含一个1的正方形的边长最长是多少。

解题分析：

用二维前缀和维护一下矩形的01值，便于后面直接$O(1)$查询任意子矩阵中1的个数，然后就是二分答案枚举边长。

#include <bits/stdc++.h>

using namespace std;

template<typename T>

inline void read(T&x){

    x=;int f=;char ch = getchar();

    while(ch<'' ||ch>''){ if(ch=='-')f=-;ch=getchar(); }

    while(ch>='' && ch<=''){ x=x*+ch-''; ch=getchar(); }

    x*=f;

}

#define rep(i,s,t) for(int i=s;i<=t;i++)

const int N = 1e3+;

int n,m,arr[N][N],sum[N][N];

bool check(int x){

    rep(i,,n) rep(j,,m) {

        if(i<x || j<x)continue;

        int num=sum[i][j]-sum[i][j-x]-sum[i-x][j]+sum[i-x][j-x];     //得到任意子矩阵的值

        if(num<=)return true;

    }

    return false;

}

int main(){

    int T;read(T);while(T--){

        memset(arr,,sizeof(arr));

        memset(sum,,sizeof(sum));

        read(n);read(m);

        rep(i,,n) rep(j,,m) {

            read(arr[i][j]);

            sum[i][j] = arr[i][j]+sum[i-][j]+sum[i][j-]-sum[i-][j-];    //维护二维前缀和

        }

        int l=,r=1e3+,ans=;

        while(l<=r){     //二分枚举正方形边长

            int mid=l+r>>;

            if(check(mid))ans=mid,l=mid+;

            else r=mid-;

        }

        printf("%d\n",ans);

    }

}

Gym 102091L Largest Allowed Area 【二分+二维前缀和】的相关教程结束。