Just Green Enough

题意

给定一个 $N\times N$ 矩阵，要求统计有多少个子矩形的最小值恰好等于 100。

思路

先看暴力：枚举所有子矩形，直接扫描内部求最小值。

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/**
 * 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-07-11 21:27
 * update_at: 2026-07-11 21:28
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int g[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    long long ans = 0;

    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= n; y1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= n; y2++) {
                    int mn = g[x1][y1];
                    for (int i = x1; i <= x2; i++) {
                        for (int j = y1; j <= y2; j++) {
                            if (mn > g[i][j]) mn = g[i][j];
                        }
                    }
                    if (mn == 100) ans++;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

正解先做一个转化：

text

1
2
3min == 100 的子矩形数量
= 所有元素 >= 100 的子矩形数量
- 所有元素 >= 101 的子矩形数量

所以只需要会计算：给定阈值 limit，有多少个子矩形满足所有元素都 $>= limit$ 。

固定子矩形的上边界 top 和下边界 bottom。对每一列，判断这一列在 top..bottom 之间是否全部满足阈值。

例如某个上下边界下得到一维 01 序列：

列	1	2	3	4	5
是否整列合法	1	1	0	1	1

连续的 1 段才能作为左右边界。长度为 2 的连续 1 段贡献：

text

11 + 2 = 3

个左右区间。

实现时固定 top，逐渐增加 bottom。用 all_good[col] 维护当前上下边界内第 col 列是否仍然全部满足阈值。每增加一行，只要这一行某列小于 limit，这一列就变成 0。

扫描 all_good 时维护当前连续 1 的长度 run：

text

1
2遇到 1：run++, ans += run
遇到 0：run = 0

最后答案就是：

text

1count_at_least(100) - count_at_least(101)

代码

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
59/**
 * 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-07-11 21:27
 * update_at: 2026-07-11 21:28
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n;
int g[MAXN][MAXN];
int all_good[MAXN]; // 当前上下边界内，第 col 列是否全部满足阈值。

long long count_at_least(int limit) {
    long long ans = 0;

    for (int top = 1; top <= n; top++) {
        for (int col = 1; col <= n; col++) {
            all_good[col] = 1;
        }

        for (int bottom = top; bottom <= n; bottom++) {
            int run = 0;
            for (int col = 1; col <= n; col++) {
                if (g[bottom][col] < limit) {
                    all_good[col] = 0;
                }

                if (all_good[col]) {
                    run++;
                    ans += run;
                } else {
                    run = 0;
                }
            }
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    cout << count_at_least(100) - count_at_least(101) << '\n';

    return 0;
}

复杂度

枚举上下边界和列，count_at_least 是 $O(N^3)$ 。

调用两次，时间复杂度仍为 $O(N^3)$ 。

空间复杂度为 $O(N^2)$ 。

总结

本题的关键是补集计数：最小值恰好为 100，可以拆成两个“全都不小于某个阈值”的计数。

固定上下边界后，二维矩形计数变成一维连续 1 子段计数，这是常见的二维降维技巧。

目录

题意

思路

代码

复杂度

总结