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

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

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

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

    1111
    0101
    1100
    1111

   其矩阵a为:

    1111
    0202
    1300
    2411

   之后对于每一行的所有列用单调栈维护每个数左/右边第一个比它小的值的下标,则以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[1005][1005],stk1[1005],stk2[1005];
int l[1005],r[1005];
char s[1005];
int mx,my,xx,yy;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        a[i][0]=-1,a[i][m+1]=-1;
        scanf("%s",s);
        for(int j=1;j<=m;++j){
            int tmp=s[j-1]-'0';
            if(tmp) a[i][j]=a[i-1][j]+1;
        }
    }
    stk1[0]=0,stk2[0]=m+1;
    for(int i=1;i<=n;++i){
        p1=p2=1;
        for(int j=1;j<=m;++j){
            while(a[i][stk1[p1-1]]>=a[i][j]) --p1;
            l[j]=stk1[p1-1];
            stk1[p1++]=j;
        }
        for(int j=m;j>=1;--j){
            while(a[i][stk2[p2-1]]>=a[i][j]) --p2;
            r[j]=stk2[p2-1];
            stk2[p2++]=j;
        }
        for(int j=1;j<=m;++j){
            int x=r[j]-l[j]-1,y=a[i][j];
            if(!y) continue; 
            int aa=i,bb=r[j]-1;
            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-1)*y,x*(y-1)));
        }
    }
    printf("%d\n",max2);
    return 0;
}

 

上一篇:hdoj 1715 大菲波数


下一篇:[BZOJ3997][TJOI2015]组合数学