2019牛客暑期多校训练营（第二场）-H Second Large Rectangle（次大子矩阵，降维，直方图+单调栈）

题目链接：https://ac.nowcoder.com/acm/contest/882/H

题目：给n×m的由01组成的矩阵，求次大全1子矩阵的大小。

思路：第一步还是降维操作，用a[i][j]记录以第i行为底的全1直方图的高，如对于矩阵：

　　　其矩阵a为：

　　　之后对于每一行的所有列用单调栈维护每个数左/右边第一个比它小的值的下标，则以a[i][j]为高的矩阵最大为(r[j]-l[j]+1)×a[i][j]，然后维护更新max1,max2即可。

　　　需要注意的是，max1维护最大矩阵的大小，max2维护次大矩阵的大小，mx、my维护最大矩阵的右下角下标，xx、yy维护最大矩阵的长和宽，若当前面积值>=max1,需要比较是否是同一个矩阵（by mx、my、xx、yy是否相等来比较），若是，则不能更新max2=max1,否则，即不是一个矩阵，则可以max2=max1.

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,p1,p2,max1,max2;

int a[][],stk1[],stk2[];

int l[],r[];

char s[];

int mx,my,xx,yy;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;++i){

        a[i][]=-,a[i][m+]=-;

        scanf("%s",s);

        for(int j=;j<=m;++j){

            int tmp=s[j-]-'';

            if(tmp) a[i][j]=a[i-][j]+;

        }

    }

    stk1[]=,stk2[]=m+;

    for(int i=;i<=n;++i){

        p1=p2=;

        for(int j=;j<=m;++j){

            while(a[i][stk1[p1-]]>=a[i][j]) --p1;

            l[j]=stk1[p1-];

            stk1[p1++]=j;

        }

        for(int j=m;j>=;--j){

            while(a[i][stk2[p2-]]>=a[i][j]) --p2;

            r[j]=stk2[p2-];

            stk2[p2++]=j;

        }

        for(int j=;j<=m;++j){

            int x=r[j]-l[j]-,y=a[i][j];

            if(!y) continue;

            int aa=i,bb=r[j]-;

            if(x*y>=max1){

                if(!(aa==mx&&bb==my&&x==xx&&y==yy))

                    max2=max1;

                max1=x*y,mx=aa,my=bb,xx=x,yy=y;

            }

            else if(x*y>max2)

                max2=x*y;

            max2=max(max2,max((x-)*y,x*(y-)));

        }

    }

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

    return ;

}

巴特西

2019牛客暑期多校训练营（第二场）-H Second Large Rectangle（次大子矩阵，降维，直方图+单调栈）

最新文章

热门文章