【GESP】C++五级练习题（二维前缀和） luogu-P2004 领地选择
GESP C++ 五级练习题，二维前缀和的应用。题目难度⭐⭐★☆☆，适合进阶练习二维数组处理和子矩阵求和，洛谷难度等级普及-。
luogu-P2004 领地选择
题目要求
题目描述
作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。
首都被认为是一个占地 $C \times C$ 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。
输入格式
第一行三个整数 $N,M,C$，表示地图的宽和长以及首都的边长。
接下来 $N$ 行每行 $M$ 个整数，表示了地图上每个地块的价值。价值可能为负数。
输出格式
一行两个整数 $X,Y$，表示首都左上角的坐标。保证最优解是唯一的。
输入输出样例 #1
输入 #1
1
2
3
4
3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1
输出 #1
1
1 2
说明/提示
对于 $60\%$ 的数据，$N,M \le 50$。
对于 $90\%$ 的数据，$N,M \le 300$。
对于 $100\%$ 的数据，$1 \le N,M \le 10^3$，$1 \le C \le \min(N,M)$。每块地价值的绝对值不超过 32767。
题目分析
这道题目要求我们在一个 $N \times M$ 的矩阵中找到一个 $C \times C$ 的正方形区域，使得该区域内所有元素的和最大。
1. 暴力解法
如果我们枚举每一个可能的左上角坐标 $(i, j)$，然后通过两层循环去计算以 $(i, j)$ 为起点的 $C \times C$ 区域的和，单次计算的复杂度是 $O(C^2)$。总的时间复杂度将会是 $O(N \cdot M \cdot C^2)$。
考虑到题目中 $N, M \le 1000$，如果 $C$ 也接近 1000，计算量将达到 $10^9$ 级别，这显然会超时。
2. 优化的解法：二维前缀和
为了快速计算任意一个子矩阵的和，我们可以使用二维前缀和技术。我们定义 pre[i][j] 表示以 $(1, 1)$ 为左上角，$(i, j)$ 为右下角的矩形区域内所有元素的和。
预处理公式：
\[pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]\]其中 a[i][j] 是当前位置的数值。通过容斥原理，我们可以在 $O(N \cdot M)$ 的时间内计算出所有的前缀和。
子矩阵求和公式：
对于任意一个以 $(x1, y1)$ 为左上角，$(x2, y2)$ 为右下角的子矩阵，其元素和可以通过以下公式在 $O(1)$ 时间内计算得出： \(Sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]\) 在本题中，我们要找的是边长为 $C$ 的正方形。如果左上角是 $(i, j)$，那么右下角就是 $(i+C-1, j+C-1)$。
3. 算法代码流程
- 读取 $N, M, C$ 以及矩阵数据。
- 利用递推公式计算二维前缀和数组
pre。 - 枚举所有可能的首都左上角坐标 $(i, j)$，其中 $1 \le i \le N - C + 1$，$1 \le j \le M - C + 1$。
- 利用 $O(1)$ 的公式计算当前正方形区域的价值和，并维护最大值及其对应的坐标。
- 输出结果。
4. 注意事项
- 数据范围：虽然单个格子的价值在
int范围内，但 $1000 \times 1000$ 个格子累加可能会超过int的表示范围，因此前缀和数组和结果变量需要使用long long类型。 - 初始值：由于地块价值可能为负数，最大价值
max_sum初始化时应该设为一个极小值（如LLONG_MIN），而不能设为 0。
示例代码
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
#include <climits>
#include <iostream>
typedef long long ll;
// a[i][j] 存储每个格子的价值
// pre[i][j] 存储 (1,1) 到 (i,j) 的矩形区域内的价值总和（二维前缀和）
int a[1005][1005];
ll pre[1005][1005];
int main() {
// N, M 为地图的宽和长，C 为首都的边长
int N, M, C;
std::cin >> N >> M >> C;
// 读取输入并计算二维前缀和
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
std::cin >> a[i][j];
// 二维前缀和公式：
// 当前点的前缀和 = 上方的前缀和 + 左方的前缀和 -
// 左上方重复计算的部分 + 当前点的值
pre[i][j] =
pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
}
}
// 初始化最大价值为 long long 的最小值，防止因负数导致错误
ll max_sum = LLONG_MIN;
int x, y; // 记录最优解的左上角坐标
// 枚举所有可能的首都左上角坐标 (i, j)
// 注意边界条件：i + C - 1 <= N 且 j + C - 1 <= M
for (int i = 1; i + C - 1 <= N; i++) {
for (int j = 1; j + C - 1 <= M; j++) {
// 利用二维前缀和计算以 (i, j) 为左上角，边长为 C
// 的正方形区域的价值和 公式：右下角前缀和 - 上方多余部分 -
// 左方多余部分 + 左上方多减的部分
ll cur_sum = pre[i + C - 1][j + C - 1] - pre[i - 1][j + C - 1] -
pre[i + C - 1][j - 1] + pre[i - 1][j - 1];
// 如果当前区域价值更大，则更新最大值和坐标
if (cur_sum > max_sum) {
max_sum = cur_sum;
x = i;
y = j;
}
}
}
// 输出结果
std::cout << x << " " << y << "\n";
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)，考试认证学员交流，互帮互助
