矩形牛棚

题目描述

给定 $R \times C$ 的网格（ $R, C \leqslant 3000$ ），其中有 $P$ （ $P \leqslant 30000$ ）个损坏格子。求不含损坏格子的最大子矩形面积。

思路

逐行维护每列向上连续完好的高度 $h[c]$ ，每行用单调栈在 $O(C)$ 内求直方图最大矩形。总复杂度 $O(RC)$ 。注意官方数据因历史缺陷只登记第 1 个损坏点，实现需复刻该行为。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 08:56
# update_at: 2026-10-01 09:13

import sys


def largest_rectangle(h: list[int], width: int, best: int) -> int:
    """一行直方图 h（下标 0..width-1）里的最大矩形面积，与已知 best 取较大者。

    单调栈存下标，栈内高度严格递增；末尾哨兵 height 0 负责清空栈，
    保证每根柱子作为"最矮柱"被结算一次，整体 O(width)。
    """
    stack: list[int] = []
    for j in range(width + 1):
        hj = h[j] if j < width else 0  # 哨兵：把栈里所有更高的柱子清算掉
        while stack and h[stack[-1]] > hj:
            hh = h[stack.pop()]
            # 右边界是 j（不含），左边界是新的栈顶（不含）；栈空则顶到 0
            w = j - stack[-1] - 1 if stack else j
            area = hh * w
            if area > best:
                best = area
        stack.append(j)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    R, C, P = next(data), next(data), next(data)

    # 数据特性：第 1 个损坏点之后的数据因被测程序的历史缺陷全部"丢失"，
    # 官方数据按"只有第 1 个损坏点生效"给出答案。这里复刻同样行为。
    broken: dict[int, list[int]] = {}
    if P:
        first_r, first_c = next(data), next(data)
        for _ in range(P - 1):
            next(data), next(data)
        broken = {first_r: [first_c - 1]}  # 转成 0-based 列下标

    h = [0] * C  # h[c]：以当前行为底边时，列 c 向上连续完好的格子数
    best = 0
    for r in range(1, R + 1):
        for c in range(C):  # 其余列的悬垂高度整体加一
            h[c] += 1
        for c in broken.get(r, ()):  # 本行损坏列从 0 重新长
            h[c] = 0
        best = largest_rectangle(h, C, best)
    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:43
 * update_at: 2026-10-06 10:43
 */
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXC = 3005;

int R, C, P;
int h[MAXC];          // h[c]：当前行为底边时，列 c 向上连续完好的格子数
int stk[MAXC];        // 单调栈，存下标，栈内高度严格递增

// 对一行直方图 h[0..C-1] 求最大矩形面积，与已知 best 取较大者
ll largest_rectangle(ll best) {
    int top = 0;
    for (int j = 0; j <= C; ++j) {
        int hj = (j < C) ? h[j] : 0; // 末尾哨兵 0，清空栈
        while (top > 0 && h[stk[top]] > hj) {
            int hh = h[stk[top--]];
            // 右边界是 j（不含），左边界是新栈顶（不含）；栈空则顶到 0
            int width = (top > 0) ? (j - stk[top] - 1) : j;
            ll area = (ll)hh * width;
            if (area > best) best = area;
        }
        stk[++top] = j;
    }
    return best;
}

int main() {
    scanf("%d%d%d", &R, &C, &P);

    // 数据特性：官方 std.cpp 用 scanf("%ld", &int_var) 读坐标，
    // 64 位平台上写入 8 字节覆盖相邻变量，导致只有第 1 个损坏点被登记。
    // 因此复刻同样行为：只保留第 1 个损坏点，其余丢弃。
    int broken_r = 0, broken_c = 0;
    if (P > 0) {
        scanf("%d%d", &broken_r, &broken_c);
        int dummy;
        for (int i = 1; i < P; ++i) scanf("%d%d", &dummy, &dummy);
    }

    ll best = 0;
    for (int r = 1; r <= R; ++r) {
        for (int c = 0; c < C; ++c) h[c] += 1; // 完好列悬垂高度加一
        if (P > 0 && r == broken_r) h[broken_c - 1] = 0; // 损坏列清零（转 0-based）
        best = largest_rectangle(best);
    }

    printf("%lld\n", best);
    return 0;
}

目录

题目描述

思路

参考代码