2019牛客暑期多校训练营（第八场）A All-one Matrices【单调栈】【前缀和】

题意:

输入 n*m 的01矩阵
有多少个全1矩阵，不会被其他的全1矩阵覆盖

题目链接：

https://ac.nowcoder.com/acm/contest/888/A

题解：

单调栈+前缀和
对于每-一个格子(ij) , 记up[il[j]为其向上的连续的1的个数。
然后枚举每一行作为矩阵的底边所在行,从前往后枚举每一列 ,枚举时候，记录更新一个pos值，判断下一行该列为不为0， 方便为下面能否向下扩展做判断， 维护一个关于up[i][j]的单调上升的栈，对于栈中每一个up值,那么每当有元素退栈的时候,判断与后一个元素是否相等，相等则可以向右扩展，不进行任何操作， 栈内前一个元素为左边所能到达最远位置, 判断一个下一行该列的连续1所能到达最左边位置pos是否大于该位置, 是则说明不能向下扩展，我们可以得到一一个全1矩阵(i+up-1,sta[top-1] + 1)-(ij) ，且不能向上下左右扩展了。
时间复杂度: O(nm)

AC_code:

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e3+5;
int up[maxn][maxn], sta[maxn];//每个点的其向上的连续的1的个数 栈
char c[maxn][maxn];
int n, m;
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%s", c[i]+1);
	}
	for(int i = 1; i <= n; i++){//预处理 
		for(int j = 1; j <= m; j++){
			if(c[i][j] == '0'){
				up[i][j] = 0;
			}else {
				up[i][j] = up[i-1][j] + 1;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int pos = 0, top = 0;
		sta[++top] = 0;
		if(c[i][1] == '0'){//放入第一个元素 
			sta[top] = 1;
		}else {
			sta[++top] = 1;
		}
		for(int j = 1; j <= m; j++){
			if(j != 1){// 第一个已经如果栈了 不必入了 
				sta[++top] = j;
			}
			if(c[i+1][j] == '0' || i == n) {//判断下一行为不为0和是不是最后一行 为0和最后一行说明这是矩形下一行所能向左扩展最远位置 
				pos = j; 
			}
			while(top > 0 && up[i][sta[top]] >= up[i][j+1]){//栈顶元素 大于等于 下一个数 则退栈 
				if(top > 1 && sta[top-1] < pos && c[i][j] != '0' && up[i][sta[top]] > up[i][j+1]) {//判断退栈元素是否无法向右扩展 
					ans++;
				}
				top--;
			}
		}
		cout<<ans<<endl; 
	}
	cout<<ans<<endl; 
	return 0;
}