csp信奥赛C高频考点专项训练之前缀和差分 --【二维前缀和】激光炸弹题目描述一种新型的激光炸弹可以摧毁一个边长为m mm的正方形内的所有目标。现在地图上有n nn个目标用整数x i x_ixi​,y i y_iyi​表示目标在地图上的位置每个目标都有一个价值v i v_ivi​。激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆破范围即那个边长为m mm的边必须与x xx轴y yy轴平行。若目标位于爆破正方形的边上该目标不会被摧毁。现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。可能存在多个目标在同一位置上的情况。输入格式输入的第一行为整数n nn和整数m mm接下来的n nn行每行有3 33个整数x , y , v x, y, vx,y,v表示一个目标的坐标与价值。输出格式输出仅有一个正整数表示一颗炸弹最多能炸掉地图上总价值为多少的目标结果不会超过32767 3276732767。输入输出样例 1输入 12 1 0 0 1 1 1 1输出 11数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 10 4 1 \le n \le 10^41≤n≤1040 ≤ x i , y i ≤ 5 × 10 3 0 \le x_i ,y_i \le 5\times 10^30≤xi​,yi​≤5×1031 ≤ m ≤ 5 × 10 3 1 \le m \le 5\times 10^31≤m≤5×1031 ≤ v i 100 1 \le v_i 1001≤vi​100。思路分析地图坐标范围为0 ≤ x , y ≤ 5000 0 \le x,y \le 50000≤x,y≤5000边长为m mm的正方形可与坐标轴平行放置且落在边上的目标不被摧毁。由于炸弹可以任意平移实数坐标存在一种放置方式使得所有被摧毁的目标均位于正方形的内部而非边界。因此我们可以将问题转化为求一个边长为m mm的正方形区域包含边界内目标价值总和的最大值因为通过微调总能使边界上的目标进入内部或排除而最优解不会依赖于边界。将坐标统一加1 11使下标从1 11开始便于使用二维前缀和。开一个大小为5005 × 5005 5005 \times 50055005×5005的数组存储每个格子的价值同一位置多个目标价值累加。计算二维前缀和s [ i ] [ j ] s[i][j]s[i][j]表示从( 1 , 1 ) (1,1)(1,1)到( i , j ) (i,j)(i,j)的矩形内价值总和。枚举所有边长为m mm的正方形的右下角( i , j ) (i,j)(i,j)利用前缀和公式sum s [ i ] [ j ] − s [ i − m ] [ j ] − s [ i ] [ j − m ] s [ i − m ] [ j − m ] \text{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]得到该正方形内包含边界的价值总和记录最大值。输出最大值结果保证不超过32767 3276732767。代码实现#includebits/stdc.husingnamespacestd;constintN5005;// 坐标最大5000加1后5001留一点余量inta[N][N],s[N][N];// a:原价值, s:前缀和intmain(){intn,m;cinnm;// 读入目标数n和边长mfor(inti0;in;i){intx,y,v;cinxyv;// 读入坐标和价值a[x1][y1]v;// 坐标偏移1累加价值}// 计算二维前缀和for(inti1;i5001;i){for(intj1;j5001;j){s[i][j]a[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1];}}intans0;// 最大价值// 枚举所有可能的边长为m的正方形右下角for(intim;i5001;i){for(intjm;j5001;j){inttmps[i][j]-s[i-m][j]-s[i][j-m]s[i-m][j-m];// 正方形内价值和if(tmpans)anstmp;// 更新最大值}}coutansendl;// 输出结果return0;}功能分析输入处理读取目标数量n nn和正方形边长m mm随后依次读取每个目标的坐标( x , y ) (x,y)(x,y)和价值v vv。将坐标统一加1 11后累加到二维数组a中避免下标越界并统一处理边界。前缀和构建计算二维前缀和数组s使得s [ i ] [ j ] s[i][j]s[i][j]表示从( 1 , 1 ) (1,1)(1,1)到( i , j ) (i,j)(i,j)矩形区域内所有目标的价值总和。这一步将后续的矩形和查询降为O ( 1 ) O(1)O(1)。枚举正方形遍历所有可能作为正方形右下角的点( i , j ) (i,j)(i,j)i , j ≥ m i,j \ge mi,j≥m利用前缀和快速计算以( i − m 1 , j − m 1 ) (i-m1, j-m1)(i−m1,j−m1)为左上角、( i , j ) (i,j)(i,j)为右下角的边长为m mm的正方形内的价值总和。更新最大值。输出结果打印找到的最大总价值。该算法时间复杂度O ( 5000 2 ) O(5000^2)O(50002)空间复杂度O ( 5000 2 ) O(5000^2)O(50002)。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}