一、题意分析1. 题目条件平面上存在n nn个目标每个目标坐标( x , y ) (x,y)(x,y)拥有价值v vv同一坐标可叠加多个目标价值激光炸弹爆炸范围是边长为m mm、边平行坐标轴的正方形规则落在正方形四条边上的目标不会被摧毁只有正方形内部的目标才计入总价值目标求投放一颗炸弹能摧毁的目标总价值最大值。2. 样例解析输入2 1 0 0 1 1 1 1正方形边长m 1 m1m1只有严格处于正方形内部的点才会被炸毁。我们把所有坐标 1 11偏移原( 0 , 0 ) (0,0)(0,0)变为( 1 , 1 ) (1,1)(1,1)当枚举右下角( 1 , 1 ) (1,1)(1,1)时对应查询边长为1的矩形区域内仅包含点( 1 , 1 ) (1,1)(1,1)总价值为1也就是样例输出。点( 1 , 1 ) (1,1)(1,1)原坐标是( 1 , 1 ) (1,1)(1,1)会落在边长为1的正方形边界上无法选取。因此全局最大总价值为1。3. 模型转化边长为m mm、不含边界的正方形等价于右下角为( i , j ) (i,j)(i,j)、左上角为( i − m , j − m ) (i-m,j-m)(i−m,j−m)的开区间矩形。坐标整体加1偏移后我们只需要查询左上角( i − m 1 , j − m 1 ) (i-m1,j-m1)(i−m1,j−m1)、右下角( i , j ) (i,j)(i,j)的闭矩形刚好对应所有严格在正方形内部的点。问题转化为经典静态二维矩形求和使用二维前缀和求解。二、核心算法二维前缀和1. 二维前缀和定义设s [ i ] [ j ] s[i][j]s[i][j]代表从左上角( 1 , 1 ) (1,1)(1,1)到右下角( i , j ) (i,j)(i,j)整个矩形内所有目标的总价值。递推公式s [ i ] [ j ] s [ i − 1 ] [ j ] s [ i ] [ j − 1 ] − s [ i − 1 ] [ j − 1 ] v a l ( i , j ) s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] val(i,j)s[i][j]s[i−1][j]s[i][j−1]−s[i−1][j−1]val(i,j)s [ i − 1 ] [ j ] s[i-1][j]s[i−1][j]上方矩形总和s [ i ] [ j − 1 ] s[i][j-1]s[i][j−1]左侧矩形总和s [ i − 1 ] [ j − 1 ] s[i-1][j-1]s[i−1][j−1]左上角区域被重复计算需要减去v a l ( i , j ) val(i,j)val(i,j)当前坐标点叠加的目标价值。2. 固定边长矩形求和公式对于右下角( i , j ) (i,j)(i,j)、边长为m mm的矩形左上角坐标为( i − m , j − m ) (i-m,\ j-m)(i−m,j−m)区域总价值s u m s [ i ] [ j ] − s [ i − m ] [ j ] − s [ i ] [ j − m ] s [ i − m ] [ j − m ] sum s[i][j] - s[i-m][j] - s[i][j-m] s[i-m][j-m]sums[i][j]−s[i−m][j]−s[i][j−m]s[i−m][j−m]三、完整解题步骤步骤1初始化与读入数据定义二维数组s存储坐标价值与前缀和数组上限5005覆盖坐标最大5000的范围读取目标总数n nn、正方形边长m mm循环读取每个目标的坐标x , y x,yx,y、价值v vv执行x, y坐标偏移将原0开头坐标转为从1开始规避前缀和下标0的边界判断在s[x][y]上累加价值处理同一坐标多个目标的叠加情况。步骤2预处理全局二维前缀和双重循环遍历全部坐标范围1~5001套用二维前缀和递推公式一次性预处理出所有矩形的总价值。预处理完成后任意矩形区域的总价值都可以在O ( 1 ) O(1)O(1)时间内算出。步骤3枚举所有合法正方形统计最大价值枚举正方形右下角坐标i 、 j i、ji、j循环起点设置为m mm保证左上角坐标i − m 、 j − m i-m、j-mi−m、j−m不会小于0避免数组越界对每一组右下角代入矩形求和公式计算当前正方形能炸毁的目标总价值使用变量res持续记录遍历过程中出现的最大总价值。步骤4输出结果遍历全部合法正方形后res存储全局最优解打印输出。四、代码分段讲解1. 常量与全局数组constintN5005;intn,m;// n个目标 边长为m的正方形ints[N][N];// 价值二维前缀和数组N 5005 N5005N5005题目坐标最大值为5000偏移后最大下标5001数组预留安全空间s数组复用先存储单点目标价值预处理后存储前缀和。2. 读入数据坐标偏移for(inti0;in;i){intx,y,v;scanf(%d%d%d,x,y,v);x,y;// 坐标1消除下标0s[x][y]v;}x,y是关键优化省去对i 0 / j 0 i0/j0i0/j0的特殊边界判断s[x][y] v多个目标在同一坐标时价值直接累加。3. 二维前缀和预处理for(inti1;i5001;i){for(intj1;j5001;j){s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1];}}严格套用二维前缀和递推公式完成全图预处理。4. 枚举所有正方形求最大值intres0;for(intim;i5001;i){for(intjm;j5001;j){resmax(res,s[i][j]-s[i-m][j]-s[i][j-m]s[i-m][j-m]);}}循环从m开始保证左上角下标不越界代入固定边长矩形求和公式计算当前正方形总价值res max(res, ...)不断更新全局最优答案。5. 输出printf(%d\n,res);打印一颗炸弹能炸毁的最大总价值。五、完整代码实现#includecstdio#includealgorithmusingnamespacestd;constintN5005;intn,m;ints[N][N];intmain(){scanf(%d%d,n,m);// 读入数据并坐标偏移for(inti0;in;i){intx,y,v;scanf(%d%d%d,x,y,v);x,y;// 坐标1消除下标0s[x][y]v;}// 预处理二维前缀和for(inti1;i5001;i){for(intj1;j5001;j){s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1];}}// 枚举所有正方形求最大值intres0;for(intim;i5001;i){for(intjm;j5001;j){intsums[i][j]-s[i-m][j]-s[i][j-m]s[i-m][j-m];resmax(res,sum);}}printf(%d\n,res);return0;}六、复杂度分析时间复杂度O ( max ⁡ ( 5001 2 , n ) ) O(\max(5001^2, n))O(max(50012,n))读入数据O ( n ) O(n)O(n)预处理前缀和O ( 5001 2 ) O(5001^2)O(50012)枚举正方形O ( ( 5001 − m ) 2 ) O((5001-m)^2)O((5001−m)2)总体复杂度由预处理决定约为2.5 × 10 7 2.5 \times 10^72.5×107次操作在1秒内可完成空间复杂度O ( 5005 2 ) O(5005^2)O(50052)约为25 × 10 6 25 \times 10^625×106个int约100MB在题目限制内七、题型总结适用场景静态二维网格、无修改操作、大量矩形求和查询核心要点坐标偏移把0起点坐标转为1起点简化前缀和边界逻辑几何转化不含边界的正方形等价固定边长矩形查询模板通用性二维前缀和是信奥基础模板可拓展到任意大小矩形求和问题拓展区分如果题目存在单点、区间修改操作则不能使用前缀和需改用二维树状数组/二维线段树。八、常见错误与调试技巧1. 数组越界错误循环边界处理不当访问s[-1][j]或s[i][-1]解决确保所有下标从1开始枚举时从m开始2. 坐标偏移遗漏错误忘记执行x, y导致前缀和计算错误解决在读入数据后立即偏移3. 价值叠加处理错误同一坐标多个目标时使用赋值而非累加解决使用而非4. 边界条件当m 0 m0m0时需要特殊处理但题目保证m ≥ 1 m \geq 1m≥1当m 5000 m 5000m5000时炸弹覆盖整个区域答案等于所有目标价值总和九、测试用例测试1样例输入2 1 0 0 1 1 1 1输出1测试2边界测试1 5000 0 0 100输出100测试3多目标叠加3 2 1 1 10 1 1 20 2 2 30输出60(1,1)和(2,2)都在边长为2的正方形内测试4大范围测试100 10 // 随机生成100个目标需要验证算法效率十、学习建议掌握前置知识一维前缀和 → 二维前缀和 → 三维前缀和练习题目P1719 最大加权矩形P2004 领地选择P3406 海底高铁一维前缀和应用拓展学习差分数组与前缀和的互逆关系二维树状数组支持单点修改二维线段树支持区间修改查询总结本题是二维前缀和的经典应用关键在于理解坐标偏移的几何意义和前缀和的递推公式。掌握这个模板后可以解决大量类似的静态矩形求和问题。