[2019牛客暑期多校训练营(第八场)-A题]All-one Matrices

题目链接(暂未开放)

题目大意为:

给你一个 $n*m$ 的01矩阵,让你找出数量最多的全1矩阵,使得他们不被包含在其他任何全1矩阵中。

样例输入:
3 4
0111
1110
0101
样例输出:
5
说明:

The 5 matrices are $ (1,2)−(1,4)$,  $(1,2)−(2,3)$,  $(1,2)−(3,2)$,  $(2,1)−(2,3)$, $ (3,4)−(3,4)$.

这个题下去写了好久才写出来,坑比较多,处理起来比较复杂。

​ 题目意思就是求所有的不能再扩充的01子矩阵,首先我们需要知道,对于一个全1子矩阵,如果它不能扩充,那么它的上下左右相邻的点必定不是全1,即有0,这个我们可以用前缀和来处理,接下来就是如何求这样一个全1矩阵。
​ 根据之前学过的知识,求一个全1矩阵,先求每个点向下的连续的1的长度,样例的连续的1的矩阵为:

0 1 1 1
1 2 2 0
0 3 0 1

​ 构造好以后,我们就对每一行利用单调栈进行计算,假如有元素出栈,那么就说明这个元素所对应的全1矩阵已经找到,不能再扩充了,那么我们一定知道它向下,向左,向右一定不能扩充,因此我们只需要它能不能向上扩充即可,此时就用到了前缀和。
​ 当遍历完一行之后,单调栈内可能还有一些元素没有被处理,那么这些元素所对应的矩阵右边界一定为左右边这一列,因此也按照之前的方法进行判断即可。

​ 需要注意的是,每当出栈一个元素,这个元素的左边界就会改变,因此我们还需要一个数组来记录当前元素的左边界的位置。

代码如下:

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
char mp[maxn][maxn];
int up[maxn][maxn];//连续1的长度
int pre[maxn][maxn];//前缀和
int pos[maxn];//当前行每个元素的左边界
int n,m;
int main()
{
while(~scanf("%d %d",&n,&m)){
memset(up,0,sizeof(up));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
}
for(int j=1;j<=m;j++){
for(int i=n;i>0;i--){
up[i][j]=up[i+1][j];
if(mp[i][j]=='1') up[i][j]++;
else up[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
pre[i][j]=pre[i][j-1];
if(mp[i][j]=='1') pre[i][j]++;
}
}
int ans=0;
for(int i=1;i<=n;i++){
stack<int>st;
for(int j=1;j<=m;j++){
pos[j]=j;
while(!st.empty() && up[i][st.top()]>=up[i][j]){
if(up[i][st.top()]!=up[i][j]){//相同的长度可以不做考虑,直接跳过,因为它必定包含在当前这个更大的矩阵中
if(pre[i-1][j-1]-pre[i-1][pos[st.top()]-1]!=j-pos[st.top()]) ans++;
}
pos[j]=pos[st.top()];
st.pop();
}
st.push(j);
}
while(!st.empty()){//剩下元素右边界均为m
if(up[i][st.top()]!=0 && pre[i-1][m]-pre[i-1][pos[st.top()]-1]!=m-pos[st.top()]+1) ans++;
st.pop();
}
}
printf("%d\n",ans);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------