All-one Matrices

Posted on | In , , ,

题目链接

题意

找到所有的不被其他全1矩阵包含的全1矩阵个数。

思路

做了这么多全1子矩阵的题目，该知道要用单调栈了吧。
我们枚举这些矩阵的底边，一个满足要求的全1子矩阵，它的底边必然满足一个特点，就是底边下面必然有至少一个0.
对于所有满足要求的边，我们直接把它的最大全1子矩阵扔到一个set里面去。
具体实现上，枚举行作为底，枚举列$j$，那么从到，只要有下面一行是0的位置就合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const int N = 3e3 + 5;
char s[N][N];
int st[N], h[N][N];
int L[N], R[N];
int sum[N];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%s", s[i] + 1);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			h[i][j] = (s[i][j] == '1')? h[i - 1][j] + 1 : 0;
	}
	for (int i = n; i >= 1; i--)
	{
		int top = 0;
		for (int j = 1; j <= m; j++)
		{
			while (top && h[i][st[top]] >= h[i][j])
				top--;
			if (top == 0)
				L[j] = 1;
			else
				L[j] = st[top] + 1;
			st[++top] = j;
		}
		top = 0;
		for (int j = m; j >= 1; j--)
		{
			while (top && h[i][st[top]] >= h[i][j])
				top--;
			if (top == 0)
				R[j] = m;
			else
				R[j] = st[top] - 1;
			st[++top] = j;
		}
		set<pair<int, int> > ss;
		sum[0] = 0;
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '1' && (i == n || s[i + 1][j] == '0'))
				sum[j] = 1 + sum[j - 1];
			else
				sum[j] = sum[j - 1];
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '1')
				ss.insert(make_pair(L[j], R[j]));
		for (auto &p : ss)
		{
			//dbg(i, p.first, p.second, sum[p.second], sum[p.first - 1]);
			if (sum[p.second] - sum[p.first - 1])
				ans++;
		}
		//dbg(i, ans);
	}
	printf("%lld\n", ans);
	return 0;
}

0%