csp信奥赛C高频考点专项训练之前缀和差分 --【二维前缀和】领地选择题目描述作为在虚拟世界里统帅千军万马的领袖小 Z 认为天时、地利、人和三者是缺一不可的所以谨慎地选择首都的位置对于小 Z 来说是非常重要的。首都被认为是一个占地C × C C\times CC×C的正方形。小 Z 希望你寻找到一个合适的位置使得首都所占领的位置的土地价值和最高。输入格式第一行三个整数N , M , C N,M,CN,M,C表示地图的宽和长以及首都的边长。接下来N NN行每行M MM个整数表示了地图上每个地块的价值。价值可能为负数。输出格式一行两个整数X , Y X,YX,Y表示首都左上角的坐标。保证最优解是唯一的。输入输出样例 1输入 13 4 2 1 2 3 1 -1 9 0 2 2 0 1 1输出 11 2说明/提示对于60 % 60\%60%的数据N , M ≤ 50 N,M\le 50N,M≤50。对于90 % 90\%90%的数据N , M ≤ 300 N,M\le 300N,M≤300。对于100 % 100\%100%的数据1 ≤ N , M ≤ 10 3 1\le N,M\le 10^31≤N,M≤1031 ≤ C ≤ min ( N , M ) 1\le C\le \min(N,M)1≤C≤min(N,M)每块地价值的绝对值不超过32767 3276732767。思路分析本题要求在N × M N\times MN×M的网格中找出一个C × C C\times CC×C的子正方形使得子正方形内所有数值之和最大并输出其左上角坐标( X , Y ) (X,Y)(X,Y)行列均从1开始。数据范围N , M ≤ 1000 N,M\le 1000N,M≤1000暴力枚举每个子正方形并求和的时间复杂度为O ( N M C 2 ) O(NM C^2)O(NMC2)不可接受。标准解法是二维前缀和预处理前缀和数组s [ i ] [ j ] s[i][j]s[i][j]表示从( 1 , 1 ) (1,1)(1,1)到( i , j ) (i,j)(i,j)的矩形和。任意子矩形 (x,y) 到 (xC-1,yC-1) 的和可以通过s [ x C − 1 ] [ y C − 1 ] − s [ x − 1 ] [ y C − 1 ] − s [ x C − 1 ] [ y − 1 ] s [ x − 1 ] [ y − 1 ] s[xC-1][yC-1] - s[x-1][yC-1] - s[xC-1][y-1] s[x-1][y-1]s[xC−1][yC−1]−s[x−1][yC−1]−s[xC−1][y−1]s[x−1][y−1]在 O(1) 时间内得到。枚举所有可能的左上角( x , y ) (x,y)(x,y)1 ≤ x ≤ N − C 1 1\le x\le N-C11≤x≤N−C11 ≤ y ≤ M − C 1 1\le y\le M-C11≤y≤M−C1记录最大值和对应坐标即可。时间复杂度O ( N M ) O(NM)O(NM)空间复杂度O ( N M ) O(NM)O(NM)完全满足要求。代码实现#includebits/stdc.husingnamespacestd;inta[1005][1005],s[1005][1005];//a原数组,s前缀和intmain(){intn,m,c;scanf(%d%d%d,n,m,c);for(inti1;in;i){//读入并计算前缀和for(intj1;jm;j){scanf(%d,a[i][j]);s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}}intmx-1e9,ansx1,ansy1;//最大值及对应坐标for(inti1;in-c1;i){//枚举左上角行for(intj1;jm-c1;j){//枚举左上角列inttmps[ic-1][jc-1]-s[i-1][jc-1]-s[ic-1][j-1]s[i-1][j-1];//子正方形和if(tmpmx){//更新最大值mxtmp;ansxi;ansyj;}}}printf(%d %d\n,ansx,ansy);//输出左上角坐标return0;}功能分析输入处理读取N , M , C N,M,CN,M,C和N × M N\times MN×M的矩阵边读入边构建二维前缀和数组s ss。核心计算遍历所有可能的C × C C\times CC×C子正方形左上角位置利用前缀和公式O ( 1 ) O(1)O(1)计算子正方形和并维护最大值及其坐标。输出按照题目要求输出最大值对应的左上角坐标保证唯一解。性能时间复杂度O ( N M ) O(NM)O(NM)对于1000 × 1000 1000\times 10001000×1000的数据轻松通过。空间复杂度O ( N M ) O(NM)O(NM)数组大小1005 × 1005 1005\times 10051005×1005约为 4MB内存安全。【完整系列请查看专栏】信奥赛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;}
