这是一类判断矩形的形状或者矩形的个数的问题,因为曾是NOIP2022真题,我们不得不重视这一类问题。同时,这个问题有非常多的解法,对其进行优化是一件很有意思的事情。

T1: P1191 矩形

题目描述

给出 n\times n 的矩阵,由 \texttt{W}\texttt{B} 组成,判断其中有多少个 \texttt{W} 构成的矩形。

数据范围:n \leq 150 ;

解析

考虑枚举矩阵的左上角,理论复杂度\mathcal{O}(n^3)

发现每个左上角可以与其下面的与右边的\mathcal{W}构成合法矩形,而每个左上角,我们仅考虑其作为左上角的情况。先向下找:找到temp个连续的\texttt{W},将其加入cnt,然后当我们往右找的时候,为了让该矩形合法,必须使temp每次取小,不然就会出现中途阻碍。

不过上述方法可以被卡到\mathcal{O}(n^4),因为每次都要找有多少个连续的,我们只要\mathcal{O}(n^2)处理出当前位置与下面能连续形成多长的\texttt{W}就可以优化一维时间复杂度。

#include<bits/stdc++.h>
//P1191
using namespace std;
typedef long long ll;
const int N = 160;
int a[N][N];
int stat[N][N];
char s[200];
int n;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> s + 1;
        for(int j = 1; j <= n; j++) {
            a[i][j] = s[j] == 'W' ? 0 : 1;
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = 1; j <= n; j++) {
            if(a[i][j] == 0) {
                stat[i][j] = stat[i + 1][j] + 1;
            }
        }
    } 
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i][j] == 0) {//当前的是白色,作为左上角
                int stats = stat[i][j];
                int tmpans = stats;
                for(int k = j + 1; k <= n; k++) {
                    if(stat[i][k]) {
                        stats = min(stats, stat[i][k]);
                        tmpans += stats;
                    }
                    else break;
                }
                ans += tmpans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

T2: P3400仓鼠窝

题目描述

给出 n\times m 的矩阵,求有几个 \mathcal{1} 构成的矩阵。

数据范围 n \leq 3000;

解析

这题数据范围远远大于上一题,所以需要一个单调队列进行优化(虽然我看到有人叫这个单调栈……?)