csp信奥赛C高频考点专项训练之前缀和差分 --【二维前缀和】最大正方形题目描述在一个n × m n\times mn×m的只包含0 00和1 11的矩阵里找出一个不包含0 00的最大正方形输出边长。保证矩阵里有至少一个1 11。输入格式输入文件第一行为两个整数n , m ( 1 ≤ n , m ≤ 100 ) n,m(1\leq n,m\leq 100)n,m(1≤n,m≤100)接下来n nn行每行m mm个数字用空格隔开0 00或1 11。输出格式一个整数最大正方形的边长。输入输出样例 1输入 14 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1输出 12思路分析使用二维前缀和快速计算任意子矩阵的和。对于全1正方形其内部所有元素和为边长的平方。枚举所有可能的正方形左上角(i,j)和边长len利用前缀和公式sum s[ilen-1][jlen-1] - s[i-1][jlen-1] - s[ilen-1][j-1] s[i-1][j-1]判断是否等于len*len记录最大边长即可。代码实现#includebits/stdc.husingnamespacestd;intn,m,a,s[105][105],ans0;// s为前缀和数组ans记录最大边长intmain(){cinnm;// 读入行数列数for(inti1;in;i)for(intj1;jm;j){cina;// 读入当前值0/1s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a;// 计算二维前缀和}// 枚举左上角和边长for(inti1;in;i)for(intj1;jm;j){for(intlen1;ilen-1njlen-1m;len){intsums[ilen-1][jlen-1]-s[i-1][jlen-1]-s[ilen-1][j-1]s[i-1][j-1];// 子矩阵和if(sumlen*len)ansmax(ans,len);// 全1则更新答案}}coutansendl;// 输出结果return0;}功能分析输入整数n,m和n×m的 0/1 矩阵。前缀和构建s[i][j]存储从(1,1)到(i,j)的矩形内 1 的个数。枚举判断三层循环枚举左上角(i,j)和边长len通过前缀和O(1)求得子矩阵和若等于len²则说明该正方形全为 1更新最大边长。输出最大全 1 正方形的边长。复杂度O(n·m·min(n,m))最坏100³ 1e6。【完整系列请查看专栏】信奥赛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;}
