信息学奥赛算法练功房◌检测中
题单　·　习题解析

洛谷 P4147 玉蟾宫

★★ 关键的一步跨得比看起来小：每格算「往上连续几个 F」⇒ **每一行就是一张柱状图**，[SP1805](/sol/sp1805/) 原样搬过来，O(NM)；★ 第二条路是悬线法（一行不共享 ⇒ 顶格对拍的参照物，而 O(N²M²) 暴力顶格 20 秒跑不完）；⚠ 输出的是 **3S** —— 抓获数 **≡ 「答案 > 0」的轮数**（四档全中，因为 0 = 3×0）；★★★ 输入的字符**之间有空格** —— 而第 13/14/30 章那几道网格题都不带 ⇒ **习惯是跟着题号走的**，★ 而这个读入 bug 在 **M = 1 时必然正确**（124 ≡ 124，剩下 35 轮才是碰巧）；★★★ 「每行没清空栈」是本轮唯一**写不成 ≡** 的一个（第一层 117 / 抓获 103，单行单列差 1.7 倍）⇒ **「≡」是量出来的运气，不是规律**；★★★ 顶格 ≠ 最坏第四次：顶格随机 60% F 的答案只有 **30 格**，全 F 是 10⁶ 格 —— 差 **33 333 倍**

原题：洛谷 P4147出自 第 35 章 单调栈与单调队列 的题单题面本地存档：2026-08-31
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P4147，日期见页头。两边不一致时信原站。

题目背景

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫， 玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

题目描述

这片土地被分成 N × M 个格子，每个格子里写着 R 或者 F， R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。

现在 freda 要在这里卖萌。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。

但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌 （她显然是不会编程的……），所以它们决定，如果你找到的最大的土地面积为 S， 它们每人给你 S 两银子。

输入格式

第一行两个整数 N，M，表示矩形土地有 N 行 M 列。

接下来 N 行，每行 M 个用空格隔开的字符 F 或 R，描述了矩形土地。

输出格式

输出一个整数，表示你能得到多少银子，即 3 × S 的值。

数据规模与约定

对于 50% 的数据，1 ≤ N, M ≤ 200。

对于 100% 的数据，1 ≤ N, M ≤ 1000。

时限 1 秒，内存 512 MB。

输入输出样例

输入

5 6 
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

输出

45

最大的全 F 矩形是右边那块 5 × 3（第 15 行、第 46 列）⇒ S = 15，输出 3 × 15 = 45。 ⚠ 输出的不是 15 —— 「rainbow 和 freda 每人给你 S 两」再加上蓝兔，一共 3 份 （第 ③ 步专门讲这个坑）。

1★★ 关键的一步：把柱状图那道题在每一行上各做一遍

p4147.cpp★ 这一版就能 AC（顶格 1000 × 1000，本机 10 毫秒 / 5 MB）
// P4147 玉蟾宫 —— ★ 这一版就能 AC
//
// ★★ 关键的一步只有一句话：**把柱状图那道题在每一行上各做一遍**。
//   对每个格子先算出「从这一格往上连续有多少个 F」——
//   那就是以这一行为底的柱状图的高度；
//   然后对每一行跑一次本章第 5 步的单调栈，取全局最大。
//   复杂度 O(NM)：顶格 1000 × 1000 = 10⁶。
//
// ⚠ 两处和算法无关、但会当场 WA 的：
//   ① 输出的是 **3 × S**，不是 S（本页第 ③ 步）；
//   ② 输入的字符**之间有空格**（本页第 ④ 步）。
#include <bits/stdc++.h>
using namespace std;


static const int N = 1005;
static int h[N], stk[N];
static char g[N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];      // ★ cin >> char 自己跳过空白


    long long best = 0;
    for (int j = 1; j <= m; j++) h[j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) h[j] = (g[i][j] == 'F') ? h[j] + 1 : 0;   // ★ 撞到 R 就清零
        h[m + 1] = -1;                                    // 哨兵
        int top = 0;                                      // ★ 每一行都从空栈开始
        for (int j = 1; j <= m + 1; j++) {
            while (top && h[stk[top]] >= h[j]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                best = max(best, H * (j - left - 1));
            }
            stk[++top] = j;
        }
    }
    cout << best * 3 << '\n';                             // ★ 三个人各给 S 两银子 ⇒ 3S
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★ 这一步跨得比看起来小

对每个格子先算出「从这一格往上连续有多少个 F」——

h[j] = (g[i][j] == 'F') ? h[j] + 1 : 0;      // ★ 撞到 R 就清零

那一行的 h[1..m] 就是一张柱状图，而「以第 i 行为底的最大全 F 矩形」 恰好就是那张柱状图里的最大矩形 —— SP1805 那道题， 也就是本章第 5~7 步讲的那一套，一个字都不用改。

每一行跑一次 ⇒ 总共 O(NM)：顶格 1000 × 1000 = 10⁶，本机 10 毫秒。

★ 而所有 F 矩形都必然「以某一行为底」，所以这样枚举不会漏。

2★ 另一条正确的路：悬线法

p4147Hang.cpp★ 悬线法 O(NM)：和单调栈一行代码都不共享

对每个格子维护「往上能拉多长的一条悬线」以及「这条悬线往左 / 往右最远能平移到哪一列」， 三个量都能从上一行 O(1) 递推。

⇒ 它和单调栈那版一行不共享，而且顶格也跑得动 ⇒ 拿来当顶格对拍的参照物正合适（1200 轮 ＋ 顶格两种地图逐字节相同）。 ⚠ 而 O(N²M²) 的枚举暴力在顶格上 20 秒都跑不完（10¹² 次）。

3⚠ 输出的是 3S —— 而这个 bug 的抓获数 ≡ 「答案不为 0」的轮数

p4147NoTri.cpp✗ 忘了乘 3（样例打出 15，当场挡住）
// P4147 · 错法 ①：忘了乘 3 —— 输出的是 S 而不是 3S
//
// ★★ 关键的一步只有一句话：**把柱状图那道题在每一行上各做一遍**。
//   对每个格子先算出「从这一格往上连续有多少个 F」——
//   那就是以这一行为底的柱状图的高度；
//   然后对每一行跑一次本章第 5 步的单调栈，取全局最大。
//   复杂度 O(NM)：顶格 1000 × 1000 = 10⁶。
//
// ⚠ 两处和算法无关、但会当场 WA 的：
//   ① 输出的是 **3 × S**，不是 S（本页第 ③ 步）；
//   ② 输入的字符**之间有空格**（本页第 ④ 步）。
#include <bits/stdc++.h>
using namespace std;


static const int N = 1005;
static int h[N], stk[N];
static char g[N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];      // ★ cin >> char 自己跳过空白


    long long best = 0;
    for (int j = 1; j <= m; j++) h[j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) h[j] = (g[i][j] == 'F') ? h[j] + 1 : 0;   // ★ 撞到 R 就清零
        h[m + 1] = -1;                                    // 哨兵
        int top = 0;                                      // ★ 每一行都从空栈开始
        for (int j = 1; j <= m + 1; j++) {
            while (top && h[stk[top]] >= h[j]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                best = max(best, H * (j - left - 1));
            }
            stk[++top] = j;
        }
    }
    cout << best << '\n';                                 // ✗ 题面要的是 3 × S
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
300 轮 档 0 档 1 全 F 档 2 F 只占 25% 档 3 单行 / 单列
答案 > 0 300 300 298 288
⇒ 真被抓 ★ 300 ★ 300 ★ 298 ★ 288

★★ 四档一个不差 —— 而它抓不满 300 的原因只有一句话： 答案是 0 的时候，0 和 3 × 0 一样。 ⇒ 又一次「说清楚它算了什么」：这个 bug 恒等于「把答案除以 3」， 于是「什么时候抓不到」是白送的推论。

4★★★ 输入里的空格 —— 而它在 M = 1 的时候是对的

p4147Read.cpp✗ 按「每行是一串连续字符」读（样例打出 6）
// P4147 · 错法 ④：按「每行是一串连续的字符」读入
//
// ⚠ 题面写的是「每行 M 个**用空格隔开**的字符」——
//   而绝大多数网格题的输入是不带空格的（第 13/14/30 章那几道都是），
//   于是 `getline` 之后直接拿 line[j] 当第 j 格，就成了这一版。
// ⇒ 它读到的其实是「字符、空格、字符、空格 …」，一半格子变成了空格
//   （空格既不是 F 也就当成了 R）。**算法一个字没错，读进来的地图错了。**
#include <bits/stdc++.h>
using namespace std;


static const int N = 1005;
static int h[N], stk[N];
static char g[N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    string line;
    getline(cin, line);                                   // 吃掉第一行剩下的换行
    for (int i = 1; i <= n; i++) {
        getline(cin, line);
        for (int j = 1; j <= m; j++)                      // ✗ 以为第 j 格就在第 j 个字符上
            g[i][j] = (j - 1 < (int)line.size()) ? line[j - 1] : 'R';
    }


    long long best = 0;
    for (int j = 1; j <= m; j++) h[j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) h[j] = (g[i][j] == 'F') ? h[j] + 1 : 0;   // ★ 撞到 R 就清零
        h[m + 1] = -1;                                    // 哨兵
        int top = 0;                                      // ★ 每一行都从空栈开始
        for (int j = 1; j <= m + 1; j++) {
            while (top && h[stk[top]] >= h[j]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                best = max(best, H * (j - left - 1));
            }
            stk[++top] = j;
        }
    }
    cout << best * 3 << '\n';                             // ★ 三个人各给 S 两银子 ⇒ 3S
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★ 前面那些网格题的输入都不带空格 —— 习惯是跟着题号走的

第 13、14、30 章那几道网格题（P1162、P1443、 P1141）的地图都是一行一个连续字符串，于是 getline 之后直接拿 line[j] 当第 j 格，是最顺手的写法。

这道题的题面写着「每行 M 个用空格隔开的字符」 ⇒ 那样读到的其实是「字符、空格、字符、空格 …」， 偶数列全部变成空格（既不是 F，也就当成了 R）。

★ 而修法只要一个字符：cin >> g[i][j]（cin >> char 本来就跳过所有空白）， 带不带空格它都对。

★ 它在 M = 1 的时候是对的 —— 而这能证

M = 1 时每行只有一个字符，根本没有空格可踩 ⇒ 两版读到的地图完全一样。

档 3（单行 / 单列）300 轮
M = 1 的轮数 124
其中两版答案相同的 ★ 124（一轮不差）
⇒ 这一档总共漏掉 159 轮（另外 35 轮是单行地图上碰巧相同）

⇒ ★★ 「能证的 0」和「碰巧相同」在同一档里同时存在，而把前者数出来，剩下的才是后者。

5⚠ 两个「忘了重置」的错法 —— 一个第一层干净，一个怎么都对不上

p4147Keep.cpp✗ 撞到 R 之后高度没清零（样例打出 60）
// P4147 · 错法 ②：撞到 R 之后高度没清零
//
// ★★ 关键的一步只有一句话：**把柱状图那道题在每一行上各做一遍**。
//   对每个格子先算出「从这一格往上连续有多少个 F」——
//   那就是以这一行为底的柱状图的高度；
//   然后对每一行跑一次本章第 5 步的单调栈，取全局最大。
//   复杂度 O(NM)：顶格 1000 × 1000 = 10⁶。
//
// ⚠ 两处和算法无关、但会当场 WA 的：
//   ① 输出的是 **3 × S**，不是 S（本页第 ③ 步）；
//   ② 输入的字符**之间有空格**（本页第 ④ 步）。
#include <bits/stdc++.h>
using namespace std;


static const int N = 1005;
static int h[N], stk[N];
static char g[N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];      // ★ cin >> char 自己跳过空白


    long long best = 0;
    for (int j = 1; j <= m; j++) h[j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) if (g[i][j] == 'F') h[j]++;   // ✗ 遇到 R 什么都不做
        h[m + 1] = -1;                                    // 哨兵
        int top = 0;                                      // ★ 每一行都从空栈开始
        for (int j = 1; j <= m + 1; j++) {
            while (top && h[stk[top]] >= h[j]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                best = max(best, H * (j - left - 1));
            }
            stk[++top] = j;
        }
    }
    cout << best * 3 << '\n';                             // ★ 三个人各给 S 两银子 ⇒ 3S
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
p4147Stack.cpp✗ 每一行没有从空栈开始（⚠ 样例照样打出 45）
// P4147 · 错法 ③：每一行没有从空栈开始
//
// ★★ 关键的一步只有一句话：**把柱状图那道题在每一行上各做一遍**。
//   对每个格子先算出「从这一格往上连续有多少个 F」——
//   那就是以这一行为底的柱状图的高度；
//   然后对每一行跑一次本章第 5 步的单调栈，取全局最大。
//   复杂度 O(NM)：顶格 1000 × 1000 = 10⁶。
//
// ⚠ 两处和算法无关、但会当场 WA 的：
//   ① 输出的是 **3 × S**，不是 S（本页第 ③ 步）；
//   ② 输入的字符**之间有空格**（本页第 ④ 步）。
#include <bits/stdc++.h>
using namespace std;


static const int N = 1005;
static int h[N], stk[N];
static char g[N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];      // ★ cin >> char 自己跳过空白


    long long best = 0;
    int top = 0;                                          // ✗ top 提到了外面
    for (int j = 1; j <= m; j++) h[j] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) h[j] = (g[i][j] == 'F') ? h[j] + 1 : 0;   // ★ 撞到 R 就清零
        h[m + 1] = -1;                                    // 哨兵
        for (int j = 1; j <= m + 1; j++) {
            while (top && h[stk[top]] >= h[j]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                best = max(best, H * (j - left - 1));
            }
            stk[++top] = j;
        }
    }
    cout << best * 3 << '\n';                             // ★ 三个人各给 S 两银子 ⇒ 3S
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
300 轮 档 0 ★ 档 1 全 F 档 2 稀疏 档 3 单行/单列
地图里有 R（第一层） 299 ★ 0 300 270
⇒ 「高度没清零」被抓 251 ★ 0 191 73
「所有最大矩形都顶到第 1 列」 117 300 59 182
⇒ 「每行没清空栈」被抓 103 300 52 105
★★★ 上面那个第一层是干净的，下面那个怎么都对不上 —— 而这本身是结论

「高度没清零」的第一层写起来毫无悬念：没有 R 就不用清零 ⇒ 档 1（全 F）是 能证的精确 0，另外三档 251 / 191 / 73 说明这份对拍是活的。

「每行没清空栈」就不一样了。它的机理是清楚的 —— 跑完一行之后栈里恒剩一格（末尾那个哨兵，和 SP1805 一模一样）， 于是下一行的「左界」再也回不到 0，顶到第 1 列的那些矩形就丢了。 可照这条写出来的第一层（117 / 300 / 59 / 182）比抓获数（103 / 300 / 52 / 105）大一截， 单行单列那一档更是差了 1.7 倍。

⇒ ★★★ 本轮六道题量出了十来个「触发条件 ≡ 抓获数」，而这一个怎么都写不成 ≡。 原因也说得清：那格残留的哨兵不只丢掉左边界为 1 的矩形，还会扰乱别的宽度 （算出负宽度、被 max 吃掉），两种效应叠在一起。 ⇒ 「≡」是量出来的运气，不是一条规律 —— 写不出来的时候， 老老实实报两层的数，别硬凑。

6★★ 顶格随机的答案只有 30 格 —— 顺手造一份顶格数据，什么都测不出来

顶格 1000 × 1000（10⁶ 格） 最大全 F 矩形 输出
每格 60% 是 F（顺手随机） ★ 30 格 90
全部是 F 10⁶ 格 3 000 000
⇒ 差 ★ 33 333 倍

★★★ 随机 60% 的 F 撒满一百万格，最大的全 F 矩形也只有 30 格（比如 6 × 5）—— 这是随机矩阵的性质：全 F 矩形的面积大约只有 O(log² n) 量级。 ⇒ 于是「顶格随机」这份数据：答案只有两位数、long long 用不上、 边界情形几乎踩不到 —— 它唯一能测的是「跑得完吗」。 ⇒ 又一次「顶格 ≠ 最坏」，而这一轮六道题里这是第四次 （P5788 暴力线性跑完、SP1805 全等高比单调不降还慢一倍、 P2866 随机答案差 4622 倍，加上这一次）。

7★ 对拍这一页

300 轮 档 0 ★ 档 1 全 F 档 2 F 占 25% ★ 档 3 单行 / 单列
逐行柱状图（正解） ★ 0 ★ 0 ★ 0 ★ 0
悬线法 ★ 0 ★ 0 ★ 0 ★ 0
忘了乘 3 300 300 298 288
高度没清零 251 ★ 0 191 73
每行没清空栈 103 300 52 105
按连续字符串读 235 300 137 141
★ 官方样例挡住三个、放过一个
错法 官方样例打出 挡住了吗
忘了乘 3 15 ★ 挡住
高度没清零 60 ★ 挡住
按连续字符串读 6 ★ 挡住
每行没清空栈 45 ⚠ 放过

★ 放过的那个原因很具体：这组样例的最大矩形在右边（第 4~6 列）， 根本不顶到第 1 列 —— 而那正是这个 bug 唯一丢东西的地方。 ⇒ 又一次「这组样例在结构上问不出这个问题」。

8度量程序和生成器

p4147Count.cpp度量程序（本页所有数字都出自它）
p4147Gen.cpp（六个档位）数据生成器
p4147Brute.cpp参照物：前缀和 + 枚举所有子矩形

9一页纸
★★ 关键的一步 每格算「往上连续几个 F」⇒ 每行就是一张柱状图 ⇒ SP1805 原样搬过来
★ 第二条路 悬线法，O(NM)、一行不共享 ⇒ 顶格对拍的参照物（暴力 20 秒跑不完）
⚠ 输出 3S 抓获数 ≡ 「答案 > 0」的轮数（四档全中）—— 因为 0 = 3×0
★★★ 输入带空格 前面几章的网格题都不带 ⇒ 习惯是跟着题号走的；★ 而它在 M = 1 时必然正确（124 ≡ 124）
★ 一个干净的第一层 「高度没清零」：没有 R 就不用清零 ⇒ 全 F 那档是能证的 0
★★★ 一个写不成 ≡ 的 「每行没清空栈」第一层 117 / 抓获 103，单行单列那档差 1.7 倍 ⇒ 「≡」不是规律
★★★ 顶格 ≠ 最坏 顶格随机 60% F 的答案只有 30 格，全 F 是 10⁶ 格 —— 差 33 333 倍