企业官网建设流程全解析

今天要聊的是洛谷 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 一维前缀和：先复习一下老本行

二维前缀和是一维的扩展，所以我建议你先把一维模型在脑子里过一遍。

一维前缀和的思想是：建立一个数组pre，pre[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开始的下标。也就是说，矩阵开成(n+1)行(m+1)列，数据从第1行第1列开始读，第0行和第0列全部保持0。

这样做的好处太明显了：公式里到处是i-1、j-1，如果从0开始，每次都要判断边界，代码会变得又臭又长。而用1-based下标配合vector初始化全0，第0行第0列天然就是0，公式里的s[i-1][j]在i=1时取的是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，那右下角就是(i+len-1, j+len-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和1，regionSum不可能大于面积；但写成“>=”属于逻辑不严谨，万一以后改题面出现其他数字就会出问题。建议从一开始就养成写“==”的习惯。

3.3 给出一份可直接提交的C++代码

下面这份代码我用C++17写，实测在洛谷平台上能直接通过，在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; vector<vector<int>> a(n + 1, vector<int>(m + 1, 0)); vector<vector<int>> s(n + 1, vector<int>(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开始，于是写前缀和时遇到i==0或者j==0的情况，s[i-1]或者s[j-1]就变成负数索引，直接越界。

解决办法很简单：不要从0开始。矩阵开大一圈，下标从1开始，第0行第0列留空。前缀和相关的题几乎都可以用这个办法解决边界问题，这不算耍赖，而是非常常见且稳妥的实现技巧。如果你在代码里写了一大堆if(i==0 && j==0)之类的特判，那你大概率是把自己绕进去了，建议立刻停手，改成1-based下标重写。

4.2 最容易写错的“面积”与“边长”

题目要求输出最大正方形的边长，不是面积。但很多人会顺手在if条件成立时写ans = len * len，把面积存进去，结果样例全1的3×3矩阵输出9而不是3，WA到怀疑人生。

这个问题我建议从源头杜绝：变量名里区分清楚。比如用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 常见错误现象速查表

下面这个表格是我实际排查中总结出来的，按“现象”查“原因”的效率最高。

排查方法有个通用技巧：如果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之前拦截掉大部分低级错误。二维前缀和这种工具，看得懂和自己能写对之间还隔着一层“手推”，跨过去了才算真正掌握。