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

雨点打透心脏的1/2处 2021-10-18 08:18 192阅读 0赞

## 题意：问有多少个全1的子矩形，且该矩形不会被另外一个全1子矩形覆盖。   分析：预处理每个1的高度以及每一行的前缀和，枚举每一行 i，单调栈求出每个点 j 以h\[i\]\[j\]（1的高度）为高度的矩形左边界L\[j\]和右边界R\[j\]，然后枚举每个点，如果sum\[i + 1\]\[R\[j\]\] - sum\[i + 1\]\[L\[j\] - 1\] != R\[j\] - L\[j\] + 1，说明这个矩形下面一排不全是1，不会被覆盖，答案++，然后我们要去重，可能有多个点 j，他们形成的矩形是一模一样的，我们再用一个单调栈（维护单调递增的高度）去一下重，如果栈顶元素高度等于当前点高度，说明是重复的，不用计算，去重这里很巧妙。此题关键在于利用单调栈确定四个方向的边界。参考[https://blog.csdn.net/ccsu\_cat/article/details/99087362][https_blog.csdn.net_ccsu_cat_article_details_99087362]。 ##

## 总结：矩形01题做少了，很久以前做过，也记得一般使用单调栈（队列）维护，时间太久了，忘得差不多了，得刷几个题捡回来了，顺带巩固一下单调栈。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 3e3+5;
    int n,m,h[N][N],sum[N][N],q[N],R[N],L[N];
    char s[N][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++) {
                if (s[i][j] == '1')
                    h[i][j] = h[i - 1][j] + 1;
                sum[i][j] = sum[i][j - 1] + s[i][j] - '0';
            }
        }
        int ans = 0;
        for (int i = n; i; i--) {
            stack<int> sta;
            sta.push(m + 1);
            ///从后往前找出每个点j以h[i][j]（1的高度）为高度的矩形右边界R[j]
            for (int j = m; j; j--) {
                while (!sta.empty() && h[i][j] <= h[i][sta.top()])
                    sta.pop();
                if (sta.empty()) R[j] = -1;
                else R[j] = sta.top() - 1;
                sta.push(j);
            }
            while (!sta.empty()) sta.pop();
            sta.push(0);
            ///从前往后找出每个点j以h[i][j]（1的高度）为高度的矩形左边界L[j]
            for (int j = 1; j <= m; j++) {
                while (!sta.empty() && h[i][j] <= h[i][sta.top()]) sta.pop();
                if (sta.empty()) L[j] = -1;
                else L[j] = sta.top() + 1;
                sta.push(j);
            }
            while (!sta.empty()) sta.pop();
            for (int j = 1; j <= m; j++) {
                if (h[i][j] == 0) {
                    while (!sta.empty())
                        sta.pop();
                    continue;
                }
                while (!sta.empty() && h[i][j] < h[i][sta.top()]) sta.pop();
                if (sta.empty() || h[i][j] != h[i][sta.top()]) {///去重
                    int l = L[j];
                    int r = R[j];
                    if (sum[i + 1][r] - sum[i + 1][l - 1] != r - l + 1)///确定下边界(下面一排不全是1，不会被覆盖)
                        ans++;
                    sta.push(j);
                }
            }
        }
        printf("%d\n", ans);
        return 0;
    }

[https_blog.csdn.net_ccsu_cat_article_details_99087362]: https://blog.csdn.net/ccsu_cat/article/details/99087362