今天要聊的是洛谷 P1387 最大正方形。这道题在GESP C五级的前缀和练习里算得上“标准课代表”因为它把二维前缀和的三板斧——建表、区域查询、枚举判断——全都在一道题里完整走了一遍。先说结论这题最适合用二维前缀和来做先预处理一个前缀和矩阵再枚举所有可能的正方形用O(1)的区域和判断正方形内部是否全是1最后输出最大边长。整个过程思路清晰、写法固定、坑也典型非常适合正在冲GESP五级、或者刚学完二维前缀和想找题练手的朋友。我第一次做这道题也是拿来当二维前缀和的“验收题”做完之后再去刷子矩阵相关题目明显觉得手顺了很多所以这次把完整的拆解、代码和踩坑记录整理出来。1. 先搞清楚题目到底在考什么1.1 用大白话把P1387讲明白题目给一个n行m列的矩阵矩阵里每个格子只有0和1。你要找到一个最大的正方形并且这个正方形里面的所有格子都必须是1最后输出这个正方形的边长。举个例子一个3×3的全1矩阵答案就是3因为整个矩阵就是一个全1正方形如果左下角有一个0那答案可能就变成2因为边长3的正方形里面混进了0不满足要求如果整个矩阵全是0答案就是0因为压根找不到任何全1正方形。数据范围不大n和m都不超过100。听起来很简单对吧但“找最大的全1正方形”这个需求如果处理方式不对写出来的代码会非常难看甚至直接超时。这道题的核心价值在于它逼着你去思考“怎么快速判断一个正方形区域里有没有0”而二维前缀和就是解决这个问题的最自然工具。1.2 为什么说它是GESP五级的前缀和“课代表”GESP五级的知识点里数组、字符串和简单算法是重头戏前缀和刚好卡在这个阶段。一级到四级你基本在跟分支循环、数组读写打交道到五级开始引入“预处理思想”先把数据算好存起来后面用的时候不重新扫描直接拿现成结果。这个思想一出来暴力做法的很多问题就迎刃而解。P1387完美对应了这个考点。它不考你多复杂的数学推导也不考什么冷门数据结构就考三件事二维前缀和怎么建、区域和怎么查、枚举边界怎么控制。这三件事搞明白了二维前缀和的基本功就扎实了。而且GESP的编程题风格偏“直给”题目描述不绕弯考点集中P1387这类题练熟之后应对五级考试里的前缀和相关题目会从容很多。1.3 做之前需要已经掌握什么在做这道题之前我建议你先确认自己有这几个基础会写一维前缀和知道pre[i] pre[i-1] a[i]这个公式并且能解释为什么区间和是pre[r] - pre[l-1]。熟悉二维数组的遍历尤其是双重for循环里行列下标的对应关系。有一点复杂度概念能大概判断一个暴力算法在给定数据范围下会不会超时。如果你一维前缀和已经写得滚瓜烂熟那恭喜你二维前缀和就是在一维基础上多套一层循环公式稍微多几个项而已。如果你连一维前缀和都还没完全吃透我建议先回到一维题把区间和搞明白了再来做这道题否则公式背下来了也是一头雾水。2. 思路拆解从暴力到二维前缀和2.1 暴力写法的复杂度一眼就劝退最直观的暴力想法枚举所有可能的左上角位置再枚举一个边长然后把这个正方形内部的所有格子都扫一遍看有没有0。如果全是1就更新答案。这个写法在n和m都等于100时到底有多慢我们可以简单估算一下正方形的边长从1到100每个边长下左上角的取法大约有(101-len)²种所有正方形的数量加起来接近34万。每个正方形内部平均格子数也不少最坏情况下总循环次数会达到十亿级别。即便你能提前break只要极端数据里答案很小这个代码跑起来就是灾难。当然n和m只有100实际测评可能不会卡到最坏情况彻底超时但“暴力能过”和“算法正确”是两回事。在GESP或信奥赛的评测环境中你不能赌数据善良必须写一个复杂度可控的解法。前缀和把“检查内部是否全1”这个最耗时的操作从O(len²)降到了O(1)整个程序瞬间变成约一百万次操作这才是靠谱的解法。2.2 一维前缀和先复习一下老本行二维前缀和是一维的扩展所以我建议你先把一维模型在脑子里过一遍。一维前缀和的思想是建立一个数组prepre[i]表示原数组从第1个元素到第i个元素的总和。构建公式是pre[i] pre[i-1] a[i]。查询时想知道下标l到r这段的和直接算pre[r] - pre[l-1]。用人话解释前缀和相当于一本“累计账本”你记下每一笔钱到目前为止总共攒了多少。想知道第l天到第r天一共花了多少钱就把第r天的累计减去第l-1天的累计中间如果你从第l-1天开始算正好剩下l到r这一个区间。这个“累计后相减”的想法就是整个前缀和思想的核心。二维只是把“一天到一天”变成“一个矩形区域到另一个矩形区域”。2.3 二维前缀和用容斥思想一次记住二维前缀和的构建公式长这样s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]其中s[i][j]表示以(1,1)为左上角、(i,j)为右下角这个矩形内所有元素的和。为什么要减一个s[i-1][j-1]因为s[i-1][j]覆盖的是第一行到第i-1行、第一列到第j列的部分s[i][j-1]覆盖的是第一行到第i行、第一列到第j-1列的部分。这两块加起来会重叠一个区域——也就是第一行到第i-1行、第一列到第j-1列这个重叠区域恰好就是s[i-1][j-1]。所以要先减去它保证每个格子只被算一次。你可以想象成两片长方形拼图总有重合的部分合在一起时必须扣掉一次重贴的面积。有了s之后查询任意一个矩形区域的和就很简单了。假设想查以(x1,y1)为左上角、(x2,y2)为右下角这个矩形的和公式是sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]这个公式也符合容斥思想先用大矩形的总和s[x2][y2]当底然后减掉上方多出去的部分s[x1-1][y2]再减掉左方多出去的部分s[x2][y1-1]但上方和左方都减过一次的那块重叠区域也就是s[x1-1][y1-1]被多减了一次所以要加回来。这两个公式不建议死记。我自己的记忆方法是看到s[i-1][j]和s[i][j-1]时脑海里立刻浮现一个坐标轴想象两个矩形怎么重叠看到查询公式时想象从一个大矩形里切掉上边和左边两条再把切重合的左上角加回来。画过一遍图之后公式基本就变成肌肉记忆了。2.4 为什么这道题是前缀和的标准应用P1387是一个01矩阵要判断一个正方形区域是否全是1。这里有一个很关键的性质矩阵里只有0和1所以一个区域的“和”本质上就是这个区域内1的个数。如果这个个数等于区域内所有格子的总数那就证明里面没有0全是1。这个“用和的数量反推是否存在0”的思路就是前缀和类题目的灵魂。它不是用前缀和直接把答案算出来而是用前缀和快速提供“某个区域有多少个1”这个信息再由你根据这个信息做判断。掌握了这个套路碰到“判断一个区域是否全为某种值”的题第一反应就应该是前缀和。3. 完整实现从公式到能跑通的代码3.1 预处理阶段每一格都存“左上角到这里的和”实现二维前缀和时我强烈建议使用从1开始的下标。也就是说矩阵开成(n1)行(m1)列数据从第1行第1列开始读第0行和第0列全部保持0。这样做的好处太明显了公式里到处是i-1、j-1如果从0开始每次都要判断边界代码会变得又臭又长。而用1-based下标配合vector初始化全0第0行第0列天然就是0公式里的s[i-1][j]在i1时取的是s[0][j]完全合法不会越界。构建过程可以在读入矩阵的同时完成for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]; } }注意这里必须先把a[i][j]读进来再更新s[i][j]。有些同学习惯先读完整矩阵再单独写循环求前缀和也可以但要注意别把两件事混在一起导致顺序出错。3.2 判断阶段区域和等于面积就是全1假设当前枚举的正方形左上角是(i,j)边长是len那右下角就是(ilen-1, jlen-1)。这个区域的1的个数可以通过区域和公式一次算出来int x2 i len - 1; int y2 j len - 1; int regionSum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1]; if (regionSum len * len) { ans len; }len * len是这个正方形区域的面积也就是格子总数。如果regionSum等于格子总数说明这个区域里的1占满了每一个格子没有0就是一个合法的全1正方形。这里用“”而不是“”是因为矩阵只有0和1regionSum不可能大于面积但写成“”属于逻辑不严谨万一以后改题面出现其他数字就会出问题。建议从一开始就养成写“”的习惯。3.3 给出一份可直接提交的C代码下面这份代码我用C17写实测在洛谷平台上能直接通过在VS Code配好C环境后本地也能跑。你可以直接抄去提交也可以自己动手敲一遍后者收获更大。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n 1, vectorint(m 1, 0)); vectorvectorint s(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]; } } int ans 0; int limit min(n, m); // 枚举边长 for (int len 1; len limit; len) { // 枚举左上角 for (int i 1; i len - 1 n; i) { for (int j 1; j len - 1 m; j) { int x2 i len - 1; int y2 j len - 1; int regionSum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1]; if (regionSum len * len) { ans len; } } } } cout ans \n; return 0; }代码不长核心就三块构建前缀和、枚举、判断。我把这个代码原封不动提交到洛谷P1387结果是通过的。如果中途出现WA大概率不是思路问题而是下标或边界的小错误下面第4节会专门说。3.4 几个能提速但没必要硬上的优化对于n和m只有100的数据上面的枚举写法已经很快了但我还是想提几个优化思路因为你会看到很多题解里这么写理解了它们以后遇到更大的数据也能用跳过过短的边长如果当前边长len已经小于等于当前的ans那这个长度不可能产生更大的答案可以直接continue。这个优化在枚举边长从小到大时很安全因为ans只会越变越大。从大到小枚举边长外层边长从limit往下走一旦找到一个可行的正方形这个边长就是最大答案可以直接结束全部循环。这种写法思路更“贪心”但要注意别把break放在错误的位置否则可能提前退出导致漏掉更大答案。对于刚开始练的同学我建议还是从小到大枚举代码更稳。二分答案由于“是否存在边长为len的全1正方形”具有单调性如果边长len可行那小于len的所有边长一定都可行。因此可以二分答案每次用O(nm)的时间检查是否存在边长mid的全1正方形整体复杂度变成O(nm*log(min(n,m)))。在小数据下这个优化看不出来但在n和m到500甚至1000时差距就出来了。你可能会想既然有DP解法能做到O(n*m)为什么还要用前缀和其实这道题有一个非常经典的动态规划做法用f[i][j]表示以(i,j)为右下角的最大全1正方形边长递推式是f[i][j] min(f[i-1][j], f[i][j-1], f[i-1][j-1]) 1。这个做法更高效但它是另一个知识点。我们现在要练的是前缀和所以刷题时应该先把前缀和写法吃透DP解法可以作为拓展之后找DP专项练习时再专门研究。千万不要在一道题里同时练两个不熟练的新知识点效果反而差。4. 实测踩坑与排查方法4.1 下标从0开始导致的前缀和边界地狱这是我见过最多人踩的坑我自己也踩过。有人习惯于二维数组下标从0开始于是写前缀和时遇到i0或者j0的情况s[i-1]或者s[j-1]就变成负数索引直接越界。解决办法很简单不要从0开始。矩阵开大一圈下标从1开始第0行第0列留空。前缀和相关的题几乎都可以用这个办法解决边界问题这不算耍赖而是非常常见且稳妥的实现技巧。如果你在代码里写了一大堆if(i0 j0)之类的特判那你大概率是把自己绕进去了建议立刻停手改成1-based下标重写。4.2 最容易写错的“面积”与“边长”题目要求输出最大正方形的边长不是面积。但很多人会顺手在if条件成立时写ans len * len把面积存进去结果样例全1的3×3矩阵输出9而不是3WA到怀疑人生。这个问题我建议从源头杜绝变量名里区分清楚。比如用side表示边长用area表示方格数。判断的时候写area len * len更新答案的时候写ans len。写代码时别图省事变量名起得清楚一点这比事后再调试划算得多。4.3 全0矩阵、单行单列这类边界数据怎么测提交之前我习惯先手动构造几个边界用例在本地跑一遍确认没问题再交。针对这道题最值得测的是全0矩阵比如2×2全是0预期答案0。单行矩阵比如1×5全是1预期答案1因为正方形边长不可能超过1。全1矩阵比如4×4全是1预期答案4。混合矩阵比如3×3只有右上角一个0预期答案2。边界数据能帮你快速定位很多隐蔽bug。我在全1矩阵上曾经遇到过答案输出0的情况后来查了半天发现是limit写成了m而不是min(n,m)导致边长循环根本没进入。4.4 常见错误现象速查表下面这个表格是我实际排查中总结出来的按“现象”查“原因”的效率最高。错误现象可能原因快速排查方法答案偏小比如3×3全1输出2区域和公式漏加了s[i-1][j-1]打印几个区域的query值跟手算结果对比答案输出面积而不是边长更新答案时写了len * len检查更新语句是不是ans len全1矩阵输出0limit写错或边长循环没有进入打印limit的值确认是min(n,m)段错误/越界矩阵开成n行m列没留1-based边界全部改成n1和m1样例过了但大数据超时还在用三重循环扫描正方形内部检查是否使用了区域和公式答案偶尔大1判断条件用了数据不严谨时可能误判严格使用判定并确认矩阵只有0和1数组内部值莫名其妙混乱读入a和计算s的顺序搞反了把读入放在计算之前或分开两个循环排查方法有个通用技巧如果WA了先不要急着改代码写一个输出语句把某个小矩阵的前缀和数组s全部打印出来然后手动算一遍看哪一步跟手算不一致。这种方式定位公式错误特别快比你盯着代码干瞪眼高效太多。5. 从P1387延伸出去前缀和的题型连接5.1 一维前缀和、树状数组、前缀和的继承关系一维前缀和解决的是“静态数组中频繁查询区间和”的问题。它的限制在于如果数组里的某个数被修改了后面的所有前缀和都要跟着变更新成本很高。树状数组可以理解为“支持单点修改的一维前缀和”。它用lowbit把前缀和维护成一棵虚拟树查询和修改都变成O(log n)。虽然和P1387关系不大但你在刷题过程中一定会遇到递进关系静态前缀和解决不了动态修改于是引入树状数组。我提这个不是让你现在就去学树状数组而是希望你意识到前缀和不是孤立知识点。GESP七级、八级的内容会逐渐往动态数据结构上靠P1387这种静态前缀和题就是把地基打牢的必经环节。地基不稳后面学树状数组、线段树的时候你会在区间合并和离散化上反复被绊倒。5.2 同套路变体最大全1子矩形与最大子矩阵和P1387是把“正方形”作为目标如果把条件改成“矩形”前缀和枚举的思路就会立刻显得吃力因为矩形的长和宽都可以独立变化枚举左上角加右下角就是O(n²m²)数据稍大就扛不住。这时候就要上更高级的技巧比如悬线法或者单调栈。还有一道很经典的“最大子矩阵和”题它的做法是用前缀和预处理每一列的区间和然后枚举上下边界把二维问题压缩成一维最大子段和问题。你会发现这里前缀和依然扮演着核心角色——它负责把每个上下边界之间的列和快速算出来剩下的就是DP或贪心。如果你把P1387练熟了再去碰这两类题你的手感会是连贯的。反之如果你连二维前缀和区域查询都写不顺后面这些题你会更加吃力。5.3 二分答案与P1387的组合拳前面3.4提到过二分答案优化这里稍微展开一点因为这个思路在很多题目里特别值得复用。“是否存在边长为mid的全1正方形”这个问题是有单调性的边长小的时候容易满足边长大了才可能失败。于是我们可以二分最大边长把“求最大值”转换成“判断可行性”。auto check [](int len) - bool { for (int i 1; i len - 1 n; i) { for (int j 1; j len - 1 m; j) { int x2 i len - 1; int y2 j len - 1; int regionSum s[x2][y2] - s[i-1][y2] - s[x2][j-1] s[i-1][j-1]; if (regionSum len * len) return true; } } return false; }; int l 0, r min(n, m), ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } }这种“单调性 二分答案”的模式在信奥题里非常常见。你可能会在GESP六级或七级的题目里再次遇到它所以现在看懂这个套路算是一种提前储备。最后分享一点个人的刷题体会。P1387这种题下手写代码之前一定要先在草稿纸上画一遍前缀和矩阵。我当时自己手算了一个3×3的全1矩阵一格格地把s填完再去套区域和公式发现所有符号错误在这一步就暴露了写代码反而变得非常顺畅。另外我强烈建议你准备一组自己的测试数据我常用的是一组全1、一组全0、一组单行、一组随机混合每次写完题先自测再提交能在评测WA之前拦截掉大部分低级错误。二维前缀和这种工具看得懂和自己能写对之间还隔着一层“手推”跨过去了才算真正掌握。