2019牛客暑期多校训练营第八场 A All-one Matrices（单调队列）

题目链接：https://ac.nowcoder.com/acm/contest/888/A

题意：给一个大小为N*M的'01'矩阵，求矩阵中全由1构成的矩阵有多少个，其中任意一个矩阵不能被其他矩阵完全包含（即不能取一个矩阵的一部分作为一个新的矩阵）       1=<N,M<=3000

思路：我们可以处理一个数组H[i][j]表示位于a[i][j]的字符向上有几个连续的1,用一个L数组记录枚举a[i][j]时第i+1行的第j位向前的最长连续1的个数，矩阵无法向下或向右扩充的条件是H[i][j]小于H[i][j-1]同时第i+1行的L[j-1]小于第i行的L[j-1]，此时我们就找到了一个有效矩阵，ans++；

下面是AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
using namespace std;
typedef long long LL;
const int N=3e3+5;
int n,m,t;
struct node
{
    int h,l,r;      ///l,r表示影响的范围
} f[N];
char s[N][N];
int a[N][N],H[N][N],L[N];  
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%s",s[i]+1);
        for(int j=1; j<=m; j++)
            a[i][j]=s[i][j]-'0';     ///字符串转化为a数组
    }
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        int l=1,r=0;          
        for(int j=0; j<=m+1; j++)    
        {
            if(a[i][j])
                H[i][j]=H[i-1][j]+1;
            else
                H[i][j]=0;
            if(a[i+1][j])
                L[j]=L[j-1]+1;
            else
                L[j]=0;
            node now= {H[i][j],j,j};       ///最开始影响范围设为自己
            while(l<=r&&now.h<=f[r].h)     
            {
                if(now.h<f[r].h&&L[j-1]<j-f[r].l)
                 ans++;
                now.l=f[r].l;                ///左端点向前延伸
                r--;                         ///f[r]出队
            }
            f[++r]=now;                       ///now.h>f[r].h或队列为空时加入now
        }
    }
    printf("%d\n",ans);
    return 0;
}

^ ^ 感谢大佬的思路【鞠躬