2019牛客暑期多校2H题

https://ac.nowcoder.com/acm/contest/882/H

Given a N×M binary matrix. Please output the size of second large rectangle containing all "1".

Containing all "1" means that the entries of the rectangle are all "1".

A rectangle can be defined as four integers x1,y1,x2,y2 where 1≤x1≤x2≤N and 1≤y1≤y2≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2 and y1≤y≤y2. If all of the cell in the rectangle is "1", this is a valid rectangle.

Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.

输入描述:

The first line of input contains two space-separated integers N and M.
Following N lines each contains M characters cij. 1≤N,M≤1000 N×M≥2 cij∈"01"

输出描述:

Output one line containing an integer representing the answer. If there are less than 2 rectangles containning all "1""1", output "0""0".

题意大概就是让你找第二大的全‘1’子矩阵，递推处理，f[i][j]表示第i行，第j列时，从i能延伸的最大全1长度。记录l和r两个数组，分别表示能向左或右扩展的最大位置。

具体内容在代码里注释，原谅我给某个小仙女口头说不清（尬笑

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3fffffff
#define maxn 1005
#define mod 1000000000
int l[maxn],r[maxn];
int f[maxn][maxn],n,m;
int main(){
    scanf("%d%d%*c",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            char x=getchar();
            if(x=='1')
                f[i][j]=f[i-1][j]+1;
            else
                f[i][j]=0;//f[i][j]储存的是当前纵向连续'1'的个数
        }
        getchar();
    }
    int ans=0,ans2=0;//ans记录当前最大值，ans2记录第二大
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            l[j]=r[j]=j;
        f[i][0]=f[i][m+1]=-1;
        for(int j=1;j<=m;++j){
            while(f[i][j]<=f[i][l[j]-1])
                l[j]=l[l[j]-1];//如果当前纵向长度小于左边，则说明可以组成矩阵，一直向左寻找到最后一个大于等于当前纵向长度为止
        }
        for(int j=m;j>=1;--j){
            while(f[i][j]<=f[i][r[j]+1])
                r[j]=r[r[j]+1];//向右寻找同理
        }
        int k1,k2;
        for(int j=1;j<=m;++j){
            if(f[i][j]){
                int t=(r[j]-l[j]+1)*f[i][j];//左右长度乘高度就是面积
                if(t>ans){
                    ans2=ans;
                    ans=t;
                    k1=l[j];
                    k2=i;//如果更新了，记录当前最大矩阵的位置，防止搜索到相同矩阵重复记录
                }
                else if(t>ans2&&(l[j]!=k1||k2!=i))//防重
                    ans2=t;
                t=max((r[j]-l[j])*f[i][j],(r[j]-l[j]+1)*(f[i][j]-1));//(高度-1)*长度和(长度-1)*高度，找大的一方和第二大矩阵面积比较，更新答案
                if(t>ans2)
                    ans2=t;
            }
        }
    }
    printf("%d\n",ans2);
}