【GESP】C++五级真题（前缀和思想考点） luogu-P10719 [GESP202406 五级] 黑白格
GESP C++ 2024年6月五级真题，前缀和思想考点，难度⭐⭐⭐☆☆，属于五级真题中比较简单的。洛谷难度等级普及/提高−
luogu-P10719 [GESP202406 五级] 黑白格
题目要求
题目描述
小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数 $n,m,k$，含义如题面所示。
之后 $n$ 行，每行⼀个长度为 $m$ 的 $\texttt{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\texttt{0}$，则对应格子为白色，否则为黑色。
输出格式
输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 $0$。
输入输出样例 #1
输入 #1
1
2
3
4
5
4 5 5
00000
01111
00011
00011
输出 #1
1
6
说明/提示
样例解释
对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，至少包含 $5$ 个黑色格子的最小子矩形的四个顶点为 $(2,4)$，$(2,5)$，$(4,4)$，$(4,5)$，共包含 $6$ 个格子。
数据范围
对于全部数据，保证有 $1\le n,m\le 100$，$1\le k\le n\times m$。
| 子任务编号 | 得分 | $n,m$ |
|---|---|---|
| $1$ | $20$ | $\le 10$ |
| $2$ | $40$ | $n=1$，$1\le m\le 100$ |
| $3$ | $40$ | $\le 100$ |
题目分析
解题思路
二维前缀和——把“数黑格”变成 $O(1)$ 查询
先扫一遍网格，用
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (s[i-1][j-1]=='1')
把以 $(1,1)$ 为左上角、$(i,j)$ 为右下角的矩形黑格总数存下来。
之后任意子矩形黑格数只需一次加减即可得到，为后面暴力枚举省下大量时间。四重循环——暴力但足够快
固定左上角 $(i,j)$，右下角 $(l,r)$ 从 $(i,j)$ 开始向右下“拖”矩形。
一旦黑格数 $\ge k$，立刻用 $(l-i+1)\times(r-j+1)$ 更新当前最小面积。无解处理
若跑完所有矩形都没出现 $\ge k$ 的情况，答案输出 $0$；否则输出记录到的最小面积。
复杂度
时间：$O(n^2m^2)\approx 10^8$，空间：$O(nm)$ 前缀和数组。
本题是五级“前缀和 + 暴力枚举”标准套路，六层循环纯暴力会超时。
示例代码
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
#include <iostream>
#include <vector>
// 前缀和数组，pre_sum[i][j] 表示从 (1,1) 到 (i,j) 的矩形中黑色格子的总数
int pre_sum[105][105];
int main() {
int n, m, k;
std::cin >> n >> m >> k; // 读入行数、列数、至少需要的黑色格子数 k
std::vector<std::string> strs(n);
for (int i = 0; i < n; i++) {
std::cin >> strs[i]; // 读入每行的 01 串，'1' 表示黑色格子
}
// 计算二维前缀和，注意下标从 1 开始，方便边界处理
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 计算二维前缀和：pre_sum[i+1][j+1] 表示从 (1,1) 到 (i+1,j+1) 矩形内黑色格子总数
// 递推公式：当前矩形和 = 上方矩形和 + 左方矩形和 - 左上重叠矩形和 + 当前格子值
// 这样即可 O(1) 得到任意子矩形和，为后续四重循环快速判断提供基础
pre_sum[i + 1][j + 1] = pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j]
+ (strs[i][j] == '1' ? 1 : 0);
}
}
bool flag = false; // 标记是否找到满足条件的子矩形
int min_count = n * m; // 初始化最小格子数为整个网格大小
// 四重循环枚举所有可能的子矩形
// (i,j) 为子矩形左上角，(l,r) 为右下角
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int l = i; l <= n; l++) {
for (int r = j; r <= m; r++) {
// 利用前缀和快速计算当前子矩形内的黑色格子数
// 利用二维前缀和公式：子矩形 (i..l, j..r) 的黑色格子数
// = 右下角大矩形和 - 上方矩形和 - 左侧矩形和 + 左上角重叠矩形和
int cur_count = pre_sum[l][r] - pre_sum[i - 1][r]
- pre_sum[l][j - 1] + pre_sum[i - 1][j - 1];
if (cur_count >= k) {
// 更新最小格子数
min_count = std::min(min_count, (l - i + 1) * (r - j + 1));
flag = true;
}
}
}
}
}
// 输出结果，若未找到则输出 0
if (flag) {
std::cout << min_count << std::endl;
} else {
std::cout << 0 << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
