激光炸弹题解

题目描述

一款新型激光炸弹可摧毁边长为 $m$ 的正方形区域内全部目标。地图存在 $n$ 个目标，每个目标由坐标 $(x_i, y_i)$ 及价值 $v_i$ 表征。炸弹爆破范围需与坐标轴平行，且边界目标不被摧毁。需求出一颗炸弹所能摧毁的最大总价值。

输入格式 首行包含两个整数 $n$ 与 $m$，分别代表目标数量与炸弹边长。 后续 $n$ 行，每行包含三个整数 $x_i, y_i, v_i$，用以表示目标的坐标和价值。

输出格式 输出一个整数，即最大可摧毁的总价值。

输入输出样例

输入样例

2 1
0 0 1
1 1 1

输出样例

1

题意

激光炸弹的爆破范围是一个边长为 m 的正方形，且这个正方形的边必须与 x 轴和 y 轴平行。

若目标位于爆破正方形的边上，该目标不会被摧毁，即只有完全处于正方形内部的目标才会被摧毁。

地图上有 n 个目标，每个目标用整数坐标 (xi,yi)表示其在地图上的位置，同时每个目标还有一个对应的价值 vi​。

示例分析

2 1 
0 0 1 
1 1 1 

这里 n=2 表示有 2 个目标，m=1 表示激光炸弹爆破范围正方形的边长为 1。两个目标分别位于 (0,0)价值为 1 和 (1,1)价值为 1由于边长为 1 的正方形无法同时将这两个目标都包含在内部，所以最多只能炸掉一个目标，最大总价值为 1 因此输出为 1

本题的核心任务是通过合理选择激光炸弹的投放位置（即确定边长为 m 的正方形的位置），使得该正方形内部包含的目标总价值最大。

9wa的做法(暴力)

思路

直接枚举所有可能的正方形区域，遍历每个区域内的所有点，累加价值。

结果只对了两个点h_h

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5005;
int grid[MAXN][MAXN]; 
int main() {
    int n, m;
    cin >> n >> m;
    m--;
    for (int i = 0; i < n; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        grid[x + 1][y + 1] += v;
    }
    int max_val = 0;
    for (int i = 1; i + m <= 5000; i++) {
        for (int j = 1; j + m <= 5000; j++) {
            int current_sum = 0;
            for (int dx = 0; dx <= m; dx++) {
                for (int dy = 0; dy <= m; dy++) {
                    current_sum += grid[i + dx][j + dy];
                }
            }
            max_val = max(max_val, current_sum);
        }
    }
    cout << max_val;
    return 0;
}

暴力行不通 只能前缀和了

算法思路

关键点：二维前缀和优化

1. 坐标偏移处理：题目中目标坐标范围处于 $[0, 5000]$，将其统一偏移 $+1$ 转变为 $[1, 5001]$，以此规避后续前缀和计算时出现负下标的情况。
2. 二维前缀和构建：
   • 定义二维数组 a[x][y] 用于存储坐标点的价值。
   • 前缀和数组 b[i][j] 表示从 $(1,1)$ 至 $(i,j)$ 的矩形区域总价值，计算公式如下：$$b[i][j] = a[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] $$
3. 爆炸区域计算：
   • 对所有可能的正方形右下角坐标 $(i,j)$ 进行遍历，实际爆炸范围为左上角 $(i - m + 1, j - m + 1)$ 至右下角 $(i,j)$。
   • 区域和公式为：$$sum = b[i][j] - b[i - m][j] - b[i][j - m] + b[i - m][j - m] $$

复杂度分析

• 时间复杂度：$O(5000^2)$，预处理前缀和以及遍历所有可能区域的时间复杂度均为 $O(5000^2)$。
• 空间复杂度：$O(5000^2)$，用于存储二维前缀和数组。

AC 代码（真的吗？）

#include <iostream>
#include <algorithm>
using namespace std; 
const int MAXN = 5005; 
int a[MAXN][MAXN], prefix[MAXN][MAXN]; 
 
int main() {
    int n, m, max_val = 0; 
    cin >> n >> m; 
 
    // 输入目标并更新坐标 
    for (int i = 0; i < n; i++) {
        int x, y, v; 
        cin >> x >> y >> v; 
        a[x+1][y+1]=v;
    }
 
    // 构建二维前缀和
    for (int i = 1; i < MAXN; i++) {
        for (int j = 1; j < MAXN; j++) {
            prefix[i][j] = a[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; 
        }
    }
 
    // 计算最大爆炸区域 
    m = min(m, 5001);  // 处理m过大的情况 
    for (int i = m; i < MAXN; i++) {
        for (int j = m; j < MAXN; j++) {
            int sum = prefix[i][j] - prefix[i - m][j] - prefix[i][j - m] + prefix[i - m][j - m]; 
            max_val = max(max_val, sum); 

不对，怎么90wa？

再读一遍题，发现没有规定一个点只能赋值一次

于是把a[x+1][y+1]=v改成a[x+1][y+1]+=v

就ac力！

AC代码(真)

#include <iostream>
#include <algorithm>
using namespace std; 
const int MAXN = 5005; 
int a[MAXN][MAXN], prefix[MAXN][MAXN]; 
 
int main() {
    int n, m, max_val = 0; 
    cin >> n >> m; 
 
    // 输入目标并更新坐标 
    for (int i = 0; i < n; i++) {
        int x, y, v; 
        cin >> x >> y >> v; 
        a[x+1][y+1]+=v; 
    }
 
    // 构建二维前缀和
    for (int i = 1; i < MAXN; i++) {
        for (int j = 1; j < MAXN; j++) {
            prefix[i][j] = a[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; 
        }
    }
 
    // 计算最大爆炸区域 
    m = min(m, 5001);  // 处理m过大的情况 
    for (int i = m; i < MAXN; i++) {
        for (int j = m; j < MAXN; j++) {
            int sum = prefix[i][j] - prefix[i - m][j] - prefix[i][j - m] + prefix[i - m][j - m]; 
            max_val = max(max_val, sum); 

加强版3.0题解

思路： 题目要求一个边长为pow(m,2)的二维区间。

但是，题目并没有规定边界，只提供了部分下标价值。

所以，我们根据m的最大值51000为边界(题目要求m的边必须与x轴,y轴平行),可炸掉的最大区间为pow(51000,2)。

最终，我们要求的就是在5000*5000的区间内找边长为m的最大子二维子区间。

易错点1:输入是从(0,0)开始的，所以要下标存储时+1(求区间和时要用)。

易错点2:遍历查找二维子区间时要注意下标越界。

//二维区间和推导公式
//cnt[i][j]-sum[i-s][j]-sum[i][j-s]+sum[i-s][j-s]