匿名用户·2026/5/16markdown1# 黑白格 题解 2 3## 题目分析 4 5我们有一个 $n$ 行 $m$ 列的网格，每个格子是黑色（用 `1` 表示）或白色（用 `0` 表示）。需要找到一个子矩形，使得其中包含的黑色格子数量 **至少为 $k$**，并且该子矩形的总面积（即包含的格子总数）尽可能小。如果不存在这样的子矩形，输出 $0$。 6 7题目保证 $n, m \le 100$，$k \le n \times m$。 8 9## 解题思路 10 11### 暴力枚举 12 13最直接的想法是枚举所有可能的子矩形：子矩形由左上角 $(x_1, y_1)$ 和右下角 $(x_2, y_2)$ 确定。对于每一个子矩形，我们可以遍历它内部的所有格子，统计其中黑色格子的个数。如果个数 $\ge k$，就用它的面积 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ 更新答案。 14 15但这样做的复杂度是 $O(n^3 m^3)$（枚举边界 $O(n^2 m^2)$，内部统计 $O(nm)$），在 $n, m \le 100$ 时显然会超时。 16 17### 二维前缀和优化 18 19为了快速计算任意子矩形内黑色格子的数量，我们可以使用 **二维前缀和** 技巧。 20 21定义 $b[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 这个矩形区域内黑色格子的总数。根据容斥原理，$b[i][j]$ 可以通过以下公式递推： 22 23$$b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]$$ 24 25其中 $a[i][j]$ 是原网格中第 $i$ 行第 $j$ 列的值（黑色为 $1$，白色为 $0$）。 26 27有了前缀和数组，对于任意一个左上角为 $(x_1, y_1)$、右下角为 $(x_2, y_2)$ 的子矩形，其内部的黑色格子数量可以直接用 $O(1)$ 时间得到： 28 29$$cnt = b[x_2][y_2] - b[x_1-1][y_2] - b[x_2][y_1-1] + b[x_1-1][y_1-1]$$ 30 31这样，我们只需要枚举所有子矩形的边界 $x_1, y_1, x_2, y_2$（$1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le m$），利用前缀和 $O(1)$ 判断黑色格子个数是否 $\ge k$，并更新最小面积。 32 33### 边界处理小技巧 34 35我们可以像参考代码那样，将矩形的边界定义为半开半闭区间：假设矩形实际占用的行是从 $x_1+1$ 到 $x_2$，列是从 $y_1+1$ 到 $y_2$。此时高度为 $x_2 - x_1$，宽度为 $y_2 - y_1$，面积为 $(x_2 - x_1) \times (y_2 - y_1)$。对应的前缀和查询也稍有变化，但本质相同。 36 37两种方式都可以，只要保证查询正确即可。下面给出的代码采用常规的闭区间写法，更加直观。 38 39## 算法步骤 40 411. 读入 $n, m, k$ 和 $n \times m$ 的 `01` 字符串。 422. 构建原网格 $a[i][j]$，并同时计算出二维前缀和数组 $b[i][j]$。 433. 初始化答案 $ans$ 为一个足够大的数（例如 $10^9$）。 444. 枚举所有可能的子矩形： 45 - 左上角行号 $x_1$ 从 $1$ 到 $n$； 46 - 左上角列号 $y_1$ 从 $1$ 到 $m$； 47 - 右下角行号 $x_2$ 从 $x_1$ 到 $n$； 48 - 右下角列号 $y_2$ 从 $y_1$ 到 $m$。 495. 对于每个子矩形，用前缀和公式计算出黑色格子数 $cnt$。 506. 如果 $cnt \ge k$，则子矩形面积为 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$，用该面积更新 $ans$ 的最小值。 517. 最后，如果 $ans$ 仍然是初始的无穷大值，说明不存在符合条件的子矩形，输出 $0$；否则输出 $ans$。 52 53## 时间复杂度分析 54 55- 构建二维前缀和数组需要遍历每个格子，时间复杂度 $O(nm)$。 56- 枚举子矩形的四重循环，总循环次数约为 $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2} \approx \frac{n^2 m^2}{4}$。对于 $n, m \le 100$，大约为 $2.5 \times 10^7$ 量级，每次内层操作是 $O(1)$ 的前缀和查询和比较，可以在时限内通过。 57- 总时间复杂度 $O(n^2 m^2)$。 58- 空间复杂度 $O(nm)$，用于存储网格和前缀和。 59 60在 $n, m = 100$ 的极限数据下，$2.5 \times 10^7$ 的循环在现代评测机上通常可以在 $1$ 秒内完成，而且常数较小，因此该方法是可行的。 61 62## 参考代码 63 64下面是 C++ 实现代码，采用通俗的闭区间写法，便于理解： 65 66```cpp 67#include <iostream> 68#include <algorithm> 69using namespace std; 70 71const int MAXN = 105; 72int a[MAXN][MAXN]; // 存储原网格 73int b[MAXN][MAXN]; // 二维前缀和 74 75int main() { 76 ios::sync_with_stdio(false); 77 cin.tie(0); 78 79 int n, m, k; 80 cin >> n >> m >> k; 81 82 // 读入网格并构建前缀和 83 for (int i = 1; i <= n; i++) { 84 for (int j = 1; j <= m; j++) { 85 char c; 86 cin >> c; 87 a[i][j] = c - '0'; // '0' 转 0，'1' 转 1 88 // 二维前缀和公式 89 b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]; 90 } 91 } 92 93 int ans = 1e9; // 初始化为极大值 94 95 // 枚举所有子矩形 96 for (int x1 = 1; x1 <= n; x1++) { 97 for (int y1 = 1; y1 <= m; y1++) { 98 for (int x2 = x1; x2 <= n; x2++) { 99 for (int y2 = y1; y2 <= m; y2++) { 100 // 计算子矩形内的黑色格子数 101 int cnt = b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] + b[x1-1][y1-1]; 102 if (cnt >= k) { 103 int area = (x2 - x1 + 1) * (y2 - y1 + 1); 104 ans = min(ans, area); 105 } 106 } 107 } 108 } 109 } 110 111 // 如果 ans 未被更新，说明无解，输出 0；否则输出 ans 112 if (ans == 1e9) ans = 0; 113 cout << ans << endl; 114 115 return 0; 116}
a[i][j]：存放原始网格，1 表示黑色，0 表示白色。b[i][j]：二维前缀和，表示从 (1,1) 到 (i,j) 的矩形内黑色格子的总数。c 时，直接利用 c - '0' 将其转为整型，并同时更新前缀和。ans 仍为极大值，说明没有符合要求的子矩形，按题目要求输出 0。本题考察了二维前缀和的运用以及暴力枚举子矩形的思路。在数据范围较小时，O(n2m2) 的算法完全可行。通过前缀和优化统计过程，避免了对每个子矩形进行 O(nm) 的遍历，从而保证了程序在时限内运行完毕。理解二维前缀和的构建与查询是解决这类网格计数问题的关键。