2019牛客暑期多校训练营（第二场）H Second Large Rectangle

秒速五厘米 2023-10-11 09:33 20阅读 0赞

题意：

就是给你个n行字符串，字符串由0和1构成，让你找出来一个里面全部字符都是1的第二大的矩形，如果一个大矩形包含一个小矩形，那么他们算两个

题解：

这道题和[51nod 1158][]很相似，只不过我们要找第二大，那么我们可以维护一个记录第一大和第二大的变量，每次都对他们进行判断

但是注意我们不能通过[51nod 1158][]的做题方法，先找出来所有矩形大小，因为有可能答案就在第一大矩形内部

所以我们可以找到最大矩形的长y和宽x后利用x\*(y-1)或(x-1)\*y来找到第二大矩形

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<queue>
     5 #include<algorithm>
     6 #include<vector>
     7 #include<stack>
     8 using namespace std;
     9 const int maxn=1080;
    10 stack<int>r;
    11 int n,m,h[maxn],a[maxn],mx1,mx2;
    12 char str[maxn][maxn];
    13 void solve(int x)
    14 {
    15     if(x>mx1)
    16         mx2=mx1,mx1=x;
    17     else if(x>mx2) mx2=x;
    18 }
    19 int main()
    20 {
    21     scanf("%d%d",&n,&m);
    22     for(int i=0;i<n;++i)
    23     {
    24         //cin>>str[i];
    25 
    26             cin>>str[i];
    27 
    28         for(int j=1;j<=m;++j)
    29         {
    30             if(str[i][j-1]-'0') a[j]+=1;
    31             else a[j]=0;
    32             h[j]=a[j];
    33         }
    34         r.push(0);
    35         for(int j=1;j<=m+1;++j)
    36         {
    37             while(h[j]<h[r.top()])
    38             {
    39                 int index = r.top();
    40                 r.pop();
    41                 int x=j-1-r.top();
    42                 int y=h[index];
    43                 solve(x*y);
    44                 solve((x-1)*y);
    45                 solve(x*(y-1));
    46             }
    47             r.push(j);
    48 
    49         }
    50     }
    51     printf("%d\n",mx2);
    52 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11278042.html

[51nod 1158]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1158
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif