基本算法题. 激光炸弹
地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意： 不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤R≤109
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1输出样例：
1:four_leaf_clover:题解 --- 二维前缀和
一维前缀和
对于一个数列，如果要计算任一区间内所有数字的和，可以暴力枚举该区间内每个数字并相加，其时间复杂度为O(N)。
前缀和，顾名思义就是第几个数之前的数之和，可以使用DP来预处理(复杂度O(N))，dp[i]表示到第i个数（包括它自身）为止前面所有数的和，从而得出状态转移方程dp[i+1] = dp[i] + num[i+1]，num[i+1]表示数组中第i+1个数字。这样要计算闭区间[i,j]的和就是dp[j]-dp[i-1] DP预处理后计算复杂度O(1))。
二维前缀和
建立在一维前缀和的基础上，如果要求一个矩阵内任意一个子矩阵中所有数字之和，就可以使用二维前缀和。此处还是使用DP进行预处理，dpi表示矩阵起始点与(i,j)两点之间所组成的矩阵内所有数字之和。也就是说二维前缀和实际上就是二维数组上的前缀和了。一维数组的前缀和也是一个一维数组，同样地，二维数组的前缀和也是一个二维的数组。
可以得出dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j]
本题详细思路可以对照注释进行理解。
:memo:代码展示
#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
PLL calc(LL n, LL m) {
if(n == 0) return {0, 0};
LL len = 1ll << (n - 1); // n - 1级图构成n级图平移时的单位长度
LL cnt = 1ll << (n - 1) * 2; // n - 1级图中所含的元素个数
LL cnk = m / cnt; // 在n级图中，编号为m的元素所属块的编号
LL idx = m % cnt; // 在n级图中，编号为m的元素在所属块中的编号
PLL pos = calc(n - 1, idx); // 在n级图中，编号为m的元素在所属块中的坐标
LL x = pos.x, y = pos.y;
// 根据n级图中某个块的编号和这个块中某个元素的坐标，确定n - 1级图的坐标变换
// 注意：离散坐标系跟实数坐标系有些许差别，不考虑这些差别
// 结果必然是抓耳挠腮。hh
if(cnk == 0) return {y, x}; // 没有平移，虽是旋转，坐标关系容易确定
if(cnk == 1) return {x, y + len}; // 单纯平移
if(cnk == 2) return {x + len, y + len}; // 单纯平移
if(cnk == 3) return {len * 2 - y - 1, len - x - 1}; // 旋转又平移
}
LL rounding(double a) {
LL b;
if(a > 0) b = (a * 2 + 1) / 2;
else b = (a * 2 - 1) / 2;
return b;
}
int main() {
int times;
cin >> times;
while(times--) {
LL n, a, b;
cin >> n >> a >> b;
PLL pa = calc(n, a - 1);
PLL pb = calc(n, b - 1);
//double x = pa.x - pb.x, y = pa.y - pb.y;
//printf("%.0lf\n", sqrt(x * x + y * y) * 10.00);
LL x = pa.x - pb.x, y = pa.y - pb.y;
double dist = sqrt(x * x + y * y);
cout << rounding(dist) << endl;
}
return 0;
}【:dart:知识点：深入理解二维前缀和】
可以看出，前缀和数组里每一个位置都表示原数组当前index左上方的数字的和。
比如像图里面画的：prefixSum[3, 3] = src[0~2, 0~2]的和;
二维前缀和数组要怎么计算出来呢？
可以分为四种情况
- i ==0 && j == 0，只有一个直接赋值即可：prefixSum[0, 0] = src[0, 0]。
- i==0，最左边的一排，图中黄色部分，prefixSum[0, j] = prefixSum[0, j-1] + src[0, j]；
- j==0，最上面一排，途中红色部分，prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];
- i!=0 || j!=0，图中绿色部分，
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];
