浅析[HNOI2003]激光炸弹

https://ac.nowcoder.com/acm/problem/20032
题目：

• 一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。
• 现在地图上有n(N ≤ 10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。
• 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。
• 若目标位于爆破正方形的边上，该目标将不会被摧毁。（这是可能的干扰项：注意激光炸弹爆破范围的边界不一定要在整数坐标点上。）

思路：

1. 二维前缀和：
   f [ i ] [ j ] 表示前 i 行，前 j 列的 val 值之和。

2. 容斥原理：
   （参考离散数学中集合之间的关系）
   要计算对角线从（x1，y1）到（x2，y2）的正方形中（x1<x2,y1<y2) 的所有值之和，结合前缀和，只需要如下操作：
   正方形所围成的范围内所有值之和 = f [ x2, y2 ] - f [ x1, y2 ] - f [ x2, y1 ] + f [ x1, y1 ]
   其中 f [ x1, y1 ] 为被重复减去后补上的。

下面为两份AC代码；
第一份代码：

#include<stdio.h>
#include<string.h>
const int maxn = 1e4+7;
int pos[maxn][maxn] = {0};
int main () {
    int n, r;
    scanf("%d %d", &n, &r);
    int x, y, val;
    int maxx = r, maxy = r;
    while (n--) {
        scanf("%d %d %d", &x, &y, &val);
        pos[x][y] = val;
        if (maxx < x) maxx = x;
        if (maxy < y) maxy = y;
    }

    //边界条件——行 
    for (int j = 1; j <= maxy; j++) {
        pos[0][j] += pos[0][j-1];
    }
    //边界条件——列 
    for (int i = 1; i <= maxx; i++) {
        pos[i][0] += pos[i-1][0];
    }

    //前缀和初始化 
    for (int i = 1; i <= maxx; i++) {
        for (int j = 1; j <= maxy; j++) {
            pos[i][j] += pos[i-1][j] + pos[i][j-1] - pos[i-1][j-1];
        }
    }

    //判断 
    int max = pos[r-1][r-1];
    for (int i = r; i <= maxx; i++) {
        for (int j = r; j <= maxy; j++) {
            int temp = pos[i][j] - pos[i-r][j] - pos[i][j-r] + pos[i-r][j-r];
            if (max < temp) {
                max = temp;
            }
        }
    }

    //边界条件判断——行 
    for (int i = r; i <= maxx; i++) {
        int temp = pos[i][r-1] - pos[i-r][r-1];
        if (max < temp) {
            max = temp;
        }
    }
    //边界条件判断——列 
    for (int j = r; j <= maxy; j++) {
        int temp = pos[r-1][j] - pos[r-1][j-r];
        if (max < temp) {
            max = temp;
        }
    }
    printf("%d", max);
    return 0;
}

第二份代码：

#include<stdio.h>
#include<string.h>
const int maxn = 1e4+7;
int pos[maxn][maxn] = {0};
int main () {
    int n, r;
    scanf("%d %d", &n, &r);
    int x, y, val;
    int maxx = r, maxy = r;
    while (n--) {
        scanf("%d %d %d", &x, &y, &val);
        x++;
        y++;
        pos[x][y] = val;
        if (maxx < x) maxx = x;
        if (maxy < y) maxy = y;
    }

    for (int i = 1; i <= maxx; i++) {
        for (int j = 1; j <= maxy; j++) {
            pos[i][j] += pos[i-1][j] + pos[i][j-1] - pos[i-1][j-1];
        }
    }

    int max = pos[r][r];
    for (int i = r; i <= maxx; i++) {
        for (int j = r; j <= maxy; j++) {
            int temp = pos[i][j] - pos[i-r][j] - pos[i][j-r] + pos[i-r][j-r];
            if (max < temp) {
                max = temp;
            }
        }
    }

    printf("%d", max);
    return 0;
}

两份代码的区别：题目的数据坐标是从（0，0）记录的，第一份的二维数组从（0，0）开始存储，第二份的整数数据故意平移一格，从（1，1）开始存储，这样不用单独判断边界条件，更加方便简洁。

第一种方式注意需要考虑边界条件————这很容易漏掉造成代码通过率只有 90% 的情况。