題干：

鏈接：https://ac.nowcoder.com/acm/contest/882/H
來源：牛客網(wǎng)
?

題目描述

Given a N×MN \times MN×M binary matrix. Please output the size of second large rectangle containing all "1"\texttt{"1"}"1".

Containing all?"1"\texttt{"1"}"1"?means that the entries of the rectangle are all?"1"\texttt{"1"}"1".
?

A rectangle can be defined as four integers?x1,y1,x2,y2x_1, y_1, x_2, y_2x1?,y1?,x2?,y2? where 1≤x1≤x2≤N1 \leq x_1 \leq x_2 \leq N1≤x1?≤x2?≤N and 1≤y1≤y2≤M1 \leq y_1 \leq y_2 \leq M1≤y1?≤y2?≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2x_1 \leq x \leq x_2x1?≤x≤x2? and y1≤y≤y2y_1 \leq y \leq y2y1?≤y≤y2. If all of the cell in the rectangle is "1"\texttt{"1"}"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 cijc_{ij}cij?.

1≤N,M≤10001 \leq N, M \leq 10001≤N,M≤1000
N×M≥2N \times M \geq 2N×M≥2
cij∈"01"c_{ij} \in \texttt{"01"}cij?∈"01"

輸出描述:

?

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

示例1

輸入

復(fù)制

1 2 01

輸出

復(fù)制

0

示例2

輸入

復(fù)制

1 3 101

輸出

復(fù)制

1

題目大意：

給定一個N*M的01矩陣，求 不嚴(yán)格第二大 的全1子矩陣。（嚴(yán)格第二大就是，你求出的值必須和第一大的 值不同）

解題報告：

? 求第一大的是單調(diào)棧裸題。這題是第二大通過觀察不難發(fā)現(xiàn)，最終答案一定是某個候選的最大子矩陣的子矩陣。而在這些子矩陣中，肯定是去掉某一行或者去掉某一列是最優(yōu)的。所以做法就是先O(N*M)求出所有最大子矩陣，然后枚舉這些矩陣，維護(hù)最大值和次大值就好了。但是要注意去重，因為假設(shè)是一行三列"111"這種情況的話，那答案肯定是不對的，因為你以每一個1為底都是對應(yīng)同一個矩形，也就是這樣會算重復(fù)。

這里我采用的處理辦法是在記錄最大值次大值的同時記錄對應(yīng)的左端點(diǎn)，右端點(diǎn)和高。（雖然按理來說不能記錄高，而應(yīng)該記錄下底和上底，但是這個題我是按照下底進(jìn)行遍歷的，而遍歷每一行的時候都清空了我上一行維護(hù)的“左端點(diǎn)，右端點(diǎn)和高”，所以這樣就足夠去重的要求了，所以不需要記錄下底和上底）。雖然去重是沒有問題的，但是其實(shí)在考慮矩陣的時候我這樣做不是嚴(yán)格正確的，因為你去掉某一列的時候，默認(rèn)是去掉了最右列，按理來說也可以去掉最左列呀，，也就是說本身會生成兩個次小子矩陣的你只考慮了一個，所以程序其實(shí)是有點(diǎn)問題，但是因為這個題求的是第2大，所以肯定還是能AC的。因為你求的這些肯定比最大子矩陣要小，所以肯定符合要求，但是如果題目讓你求第三大的，這樣就不太行了。。。你得把：去掉左列，去掉右列，去掉上行，去掉下行，都加入考慮中，才是正確答案。。（或許這題還可以再出一遍？？emmm）

以上是我采用的處理辦法，但是不具有通用性，他如果讓你求第8大，那你維護(hù)八個變量不成？所以這里正解給出的是加入vector中，然后對vector排序，然后去重（這一點(diǎn)一定別忘了，但是你要是這么寫的話就得記錄對應(yīng)的左端點(diǎn)，右端點(diǎn)和下底上底了，不能只記錄高了），然后輸出第8大。（因為這題是第二大所以直接上pq維護(hù)兩個元素也行）

AC代碼：

#include<iostream> #include<cmath> #include<cstdio> #include<algorithm> #include<stack>using namespace std; const int MAX = 1000 + 5; int n,m; int maze[MAX][MAX]; int L[MAX],R[MAX];void getl(int i) {stack<int > sk;//要找他左側(cè)的第一個嚴(yán)格比他小的元素 所以需要從左向右維護(hù)一個嚴(yán)格單調(diào)遞增棧for(int j = 1; j<=n; j++) {while(!sk.empty() && maze[i][sk.top() ]>=maze[i][j] ) sk.pop();if(sk.empty() ) L[j] = 0;else L[j] = sk.top();sk.push(j);}} void getr(int i) {stack<int > sk;//要找他右側(cè)的第一個嚴(yán)格比他小的元素 所以需要從右向左維護(hù)一個嚴(yán)格單調(diào)遞增棧for(int j = n; j>=1; j--) {while(!sk.empty() && maze[i][sk.top() ]>=maze[i][j] ) sk.pop();if(sk.empty() ) R[j] = n+1;else R[j] = sk.top();sk.push(j);}} void init() {for(int i = 1; i<=m; i++)for(int j = 1; j<=n; j++)maze[i][j]=0; } int main() {while(~scanf("%d %d",&m,&n) ) {//m行n列init();for(int i = 1; i<=m; i++) {for(int j = 1; j<=n; j++) {int tmp;scanf("%1d",&tmp);if(tmp==1) {maze[i][j]=maze[i-1][j]+1;}}}//至此我們已經(jīng)有了截止第i行的(1~i)每一個j的連續(xù)高度，int maxx=0,ci = 0,tmp,tmp1,tmp2,mx1=-1,mx2=-1,mh=-1;for(int i = 1; i<=m; i++) {getl(i);getr(i);mx1=-1,mx2=-1,mh=-1;for(int j = 1; j<=n; j++) {tmp = maze[i][j] * (R[j] - L[j] -1);tmp1 = maze[i][j] * (R[j] - L[j] -2);tmp2 = (maze[i][j]-1) * (R[j] - L[j] -1);int curl=L[j]+1,curr = R[j]-1,curh = maze[i][j];if(tmp > maxx) {ci = maxx;mx1=curl,mx2=curr,mh=curh;maxx = tmp;}else if(tmp > ci && (mx1!=curl || mx2!=curr || mh!=curh)) {ci = tmp;}if(tmp1 >= tmp2) {tmp = tmp1;curr--;}else {tmp = tmp2;curh--;} // tmp = max(tmp1,tmp2);if(tmp > maxx) {ci = maxx;mx1=curl,mx2=curr,mh=curh;maxx = tmp;}else if(tmp > ci && (mx1!=curl || mx2!=curr || mh!=curh)) {ci = tmp;}} // printf("\n");}printf("%d\n",ci);}return 0 ;} /* 1 3 111 */

然后你會發(fā)現(xiàn)簡短好多：（忽然發(fā)現(xiàn)好像不用考慮減一行呀、、因為那肯定在上一行當(dāng)下底的時候算過了、、）

（其實(shí)還是因為單調(diào)棧的打開方式不太一樣，我是遍歷到第i個元素的時候處理第i個元素，然后push(i)進(jìn)去，他是pop(j)的時候才開始處理每一個j，我要是這么寫的話應(yīng)該也短不少，而且有的時候只能用第二種方式，比如后面那次牛客多校、、）

這樣寫的意思就是把所有寬度的縮減都考慮進(jìn)去了。但是這樣寫的話應(yīng)該可以卡T掉，，因為你構(gòu)造一個左下全1的下三角矩陣，就能卡成O(N*M*M)、、因為他那個cnt的動作太耗時了。（本來寫的是最下面那個代碼）

#include<bits/stdc++.h> using namespace std; const int M = 1e3+5; int dp[M][M]; int ddz[M],w[M]; vector<int> ans; int n,m;void solve(int *f){int top = 0;ddz[top] = -1;f[m+1] = -1;for(int i=1;i<=m+1;i++){if(ddz[top] <= f[i]) ddz[++top] = f[i];else {int cnt = 0;//接下來把所有寬度的都加進(jìn)去while(top && ddz[top] > f[i]) {cnt++;ans.push_back(ddz[top] * cnt);top--;}while(cnt--) ddz[++top] = f[i];ddz[++top] = f[i];}} }int main(){char c[M];while(~scanf("%d%d",&n,&m)) {ans.clear();for(int i=1;i<=n;i++){scanf("%s",c);for(int j=1;j<=m;j++) dp[i][j] = c[j-1] == '0'? 0 : dp[i-1][j]+1;}for(int i=1;i<=n;i++) solve(dp[i]);sort(ans.begin(),ans.end());/*考慮特例*/int sz = ans.size();if(sz<=1) printf("0\n");printf("%d\n", ans[sz-2]);}return 0; }

他本來的solve函數(shù)是這么寫的：

void solve(int *f){int top = 0;ddz[top] = -1;f[m+1] = -1;for(int i=1;i<=m+1;i++){/*等于時是否彈出這需要自己注意一下,就是嚴(yán)不嚴(yán)格單調(diào)的選擇*/if(ddz[top]<f[i]) ddz[++top]=f[i],w[top]=1;else{int width = 0;/*此處注意要先加寬度*/while(top&&f[i]<ddz[top]){ width+=w[top],ans.push_back(ddz[top]*width),ans.push_back(ddz[top]*(width-1));top--;}/*我的做法是 : 等于是加入,不嚴(yán)格單調(diào)*/ddz[++top]=f[i],w[top]=width+1;}} }

?

總結(jié)

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第二场） - H】Second Large Rectangle（单调栈，全1子矩阵变形）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。