[HNOI2003] 激光炸弹

题目解析

这是一道非常经典的**二维前缀和（2D Prefix Sum）**题目。

题目虽然提到“激光炸弹”、“正方形”、“边界不包含”等几何概念，但由于坐标范围较小且均为整数，其实质是在一个二维矩阵中，寻找一个 $m \times m$ 的子矩阵，使得子矩阵内的元素之和最大。

核心解题思路

坐标转换（处理边界）
- 题目中给出的坐标 $x, y$ 是从 $0$ 开始的。为了方便计算前缀和（避免数组下标越界，利用下标 $0$ 作为边界哨兵），我们通常将所有读入的坐标 $+1$ ，即把坐标映射到 $[1, 5001]$ 的范围内。
- 题目提到“若目标位于爆破正方形的边上，该目标不会被摧毁”。这在离散的整数格点问题中，意味着一个边长为 $m$ 的正方形实际上能覆盖 $m \times m$ 个格点（只要我们合理调整放置位置，比如放在 $x.5$ 的位置）。
- 结论：你可以直接理解为我们需要在网格中圈出一个 $m \times m$ 的矩形区域，求其中的数值和。
二维前缀和（Precomputation）
- 定义：设 $S[i][j]$ 表示从矩形左上角 $(1,1)$ 到右下角 $(i,j)$ 这一范围内所有目标的价值之和。
- 递推公式（容斥原理）：
  
  $S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + \text{value}[i][j]$
- 这个步骤的时间复杂度是 $O(W \times H)$ ，其中 $W, H$ 是地图的最大边长（约 5000）。
枚举与查询（Optimization）
- 我们需要找到一个边长为 $m$ 的正方形区域总和最大。
- 我们可以枚举正方形的右下角坐标 $(i, j)$ 。为了保证正方形能放下， $i$ 和 $j$ 至少要从 $m$ 开始遍历。
- 子矩阵求和公式：以 $(i, j)$ 为右下角，边长为 $m$ 的正方形区域的和为：
  
  $\text{Sum} = S[i][j] - S[i-m][j] - S[i][j-m] + S[i-m][j-m]$
- 我们在遍历全图的过程中维护一个最大值即可。

图解二维前缀和

构造 $S[i][j]$ ：绿色区域 = 蓝色 + 黄色 - 重叠的红色 + 当前点。
计算子矩阵：想要紫色区域的和 = 总的大矩形 - 上方矩形 - 左侧矩形 + 左上角被多减去的一次。

代码实现 (C++)

C++

#include <iostream>
#include <algorithm>

using namespace std;

// 题目坐标最大为5000，为了防止越界和从1开始计数，我们开大一点
const int MAXN = 5005;

// s数组用于存储二维前缀和
// 注意内存限制，int类型 5005*5005*4 bytes ≈ 100MB，通常是可以的
int s[MAXN][MAXN];

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 处理输入
    // 记录最大的坐标范围，减少不必要的遍历（虽然直接遍历到5001也可以）
    int max_x = 0, max_y = 0; 

    for (int i = 0; i < n; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        // 将坐标 +1，变为 1-based index，方便前缀和计算
        // 多个目标可能在同一个位置，所以要用 +=
        s[x + 1][y + 1] += v;
        
        max_x = max(max_x, x + 1);
        max_y = max(max_y, y + 1);
    }

    // 预处理二维前缀和
    // 坐标范围固定最大到 5001 即可
    // 这里的 R 是我们遍历的右边界，至少要遍历到 max_x 和 max_y
    // 为了省事，直接设常数 5001 也是常用的做法，因为复杂度允许
    int R = 5001; 

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= R; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
        }
    }

    // 枚举所有可能的边长为 m 的正方形
    int ans = 0;
    
    // 如果 m 大于地图最大尺寸，则直接取全图的和（或者将 m 限制在 R 以内）
    // 但通常不需要特判，因为下面的循环条件 i >= m 会处理
    // 唯一要注意的是题目没说 m 一定小于 5000，如果 m > 5001，直接输出全图总和
    // 我们可以简单把 m 限制一下
    /* 注意：如果 m > R，炸弹比地图大，下面的循环不会执行，ans 保持 0。
       所以最好将 m 设为 min(m, R)。
       例如：地图只有 (1,1)，R=5001，m=6000。炸弹能覆盖所有点。
    */
    m = min(m, R);

    for (int i = m; i <= R; i++) {
        for (int j = m; j <= R; j++) {
            // 利用前缀和计算子矩阵的和
            // 右下角为(i, j)，边长为 m
            int current_val = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];
            ans = max(ans, current_val);
        }
    }

    cout << ans << endl;

    return 0;
}

易错点解析

坐标重合：题目提示“可能存在多个目标在同一位置上的情况”，所以在输入时必须使用 += 而不是 =，否则会覆盖之前的目标价值。
坐标越界与偏移：题目输入坐标包含 0，前缀和通常需要 i-1，如果下标是 0 会导致 s[-1] 越界。因此必须将所有坐标 +1。
炸弹范围 $m$ ：
- 题目给的数据范围 $m$ 可能很大。虽然题目说 $x, y \le 5000$ ，但没严格说 $m \le 5000$ 。如果 $m$ 比最大的坐标还大，理论上可以覆盖整个区域。在代码中通过 m = min(m, 5001) 可以巧妙处理这种情况，防止循环不执行。
内存限制：int s[5005][5005] 大约占用 100MB 内存。如果题目限制极为严格（比如 64MB），可能需要用 short（因为题目说结果不超过 32767，说明单点价值不高，前缀和可能也存得下？不，前缀和是累加的，会很大，结果是指最终答案）。
- 修正：题目只说输出结果（最大值）不会超过 32767？这通常是针对 $v_i$ 很小的数据。但为了保险，标准解法依然用 int。100MB 在现代竞赛题目（通常 128MB 或 256MB）中是安全的。
边界排除的理解：
- 很多人纠结“边界上的点不算”。但在离散网格中，如果我们将一个 $m \times m$ 的正方形的右下角对准格点 $(i, j)$ （实际上是看作 $(i, j)$ 这个格子的右下角），那么它覆盖的格点范围就是行 $[i-m+1, i]$ ，列 $[j-m+1, j]$ 。这正好包含了 $m$ 行 $m$ 列，完全符合题目对于“能容纳多少个整数点”的数学抽象。

参考

https://www.luogu.com.cn/article/qehett1m

[HNOI2003] 激光炸弹

目录

题目解析

核心解题思路

图解二维前缀和

代码实现 (C++)

易错点解析

参考