这是一类判断矩形的形状或者矩形的个数的问题，因为曾是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;
解析
这题数据范围远远大于上一题，所以需要一个单调队列进行优化（虽然我看到有人叫这个单调栈……？）
正文完
