luogu-P2004 领地选择

GESP C++ 五级练习题，二维前缀和的应用。题目难度⭐⭐★☆☆，适合进阶练习二维数组处理和子矩阵求和，洛谷难度等级普及-。

luogu-P2004 领地选择

题目要求

题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 $C \times C$ 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 $N,M,C$，表示地图的宽和长以及首都的边长。

接下来 $N$ 行每行 $M$ 个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数 $X,Y$，表示首都左上角的坐标。保证最优解是唯一的。

输入输出样例 #1

输入 #1

3 4 2
1 2 3 1
-1 9 0 2
2 0 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)$ 为右下角的矩形区域内所有元素的和。

预处理公式：

其中 a[i][j] 是当前位置的数值。通过容斥原理，我们可以在 $O(N \cdot M)$ 的时间内计算出所有的前缀和。

子矩阵求和公式：

对于任意一个以 $(x1, y1)$ 为左上角，$(x2, y2)$ 为右下角的子矩阵，其元素和可以通过以下公式在 $O(1)$ 时间内计算得出：

在本题中，我们要找的是边长为 $C$ 的正方形。如果左上角是 $(i, j)$，那么右下角就是 $(i+C-1, j+C-1)$。

3. 算法代码流程

1. 读取 $N, M, C$ 以及矩阵数据。
2. 利用递推公式计算二维前缀和数组 pre。
3. 枚举所有可能的首都左上角坐标 $(i, j)$，其中 $1 \le i \le N - C + 1$，$1 \le j \le M - C + 1$。
4. 利用 $O(1)$ 的公式计算当前正方形区域的价值和，并维护最大值及其对应的坐标。
5. 输出结果。

4. 注意事项

• 数据范围：虽然单个格子的价值在 int 范围内，但 $1000 \times 1000$ 个格子累加可能会超过 int 的表示范围，因此前缀和数组和结果变量需要使用 long long 类型。
• 初始值：由于地块价值可能为负数，最大价值 max_sum 初始化时应该设为一个极小值（如 LLONG_MIN），而不能设为 0。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号