1. 从洛谷 P1387 看 GESP 五级的前缀和考点如果你刷过洛谷的普及组题单大概率见过 P1387 这道“最大正方形”。我第一次做它的时候看到“最大正方形”四个字第一反应是动态规划——这是很多人的本能反应。但那次我正好在准备 GESP 五级的前缀和专题于是强迫自己换一条路用二维前缀和加二分答案能不能做结果不仅做出来了而且对二维前缀和的理解比刷十道模板题都深刻。今天这篇就完整拆解这条路顺便把 DP 解法也放在一起对比让你一道题同时吃透两个知识点。这道题本身不复杂给你一个 n 行 m 列的 0/1 矩阵找一个最大的、全部由 1 组成的正方形输出它的边长。GESP 五级的大纲里前缀和属于“基础算法”的重要分支考试中经常借这种“一眼看着像 DP”的题目来考察你对区间求和工具的理解。换句话说如果你只会 DP 而不会前缀和遇到考场上那道“换皮”的题可能就懵了。所以我建议你把前缀和这个解法当成主方案先掌握DP 作为对照理解。1.1 题目在说什么题目输入格式不复杂第一行两个整数 n、m接下来 n 行每行 m 个整数每个整数要么是 0 要么是 1。要求输出一个整数表示矩阵中最大的、完全由 1 组成的正方形的边长。看个简单例子2 3 1 1 1 1 1 0这个矩阵里从左上角开始有一个 2×2 的全 1 方块1 1 1 1所以答案是 2。注意“最大正方形”必须是正的正方形边长相等不能是长方形而且正方形内不能出现任何 0哪怕只有角落一个 0 也不行。这个限制正是后面用前缀和做可行性判断的核心。数据范围方面洛谷原题 n、m 通常不超过 100。这个范围其实很宽松O(n³) 暴力都能过但作为 GESP 五级练习不能用“暴力能过”来安慰自己而是要想清楚更优的做法以及每个做法背后的适用条件。如果你去翻题解区会发现大部分人写的是 DP但用前缀和二分可以做到 O(nm log min(n,m))在 n、m 到 1000 甚至更大时依然能打这是它最大的价值。1.2 为什么说这是“前缀和练习”标题里明确写着“前缀和练习”这意味着出题者/整理者希望你在做这道题时把重点放在前缀和这个工具上而不是 DP。GESP 五级大纲中前缀和经常和“区间求和”“二维矩阵操作”绑定出现而 P1387 恰好是一个“给定矩阵反复询问某个正方形区域内的和”的问题。如果没有前缀和检查一个边长为 k 的正方形是否全为 1最朴素的做法是遍历这个正方形里的每一个格子复杂度 O(k²)。如果要枚举所有正方形总复杂度会飙升到 O(nm·min(n,m)²) 级别。用二维前缀和把每个区域的求和降到 O(1) 之后我们才能用二分答案去枚举边长否则二分本身也救不了暴力检查的复杂度。所以这道题的正确打开方式是先建立“二维前缀和可以快速回答子矩阵和”的直觉再想到“正方形全为 1 等价于这个正方形区域的和等于 k²”最后用二分把“求最大边长”转化为“判断某个边长是否可行”。三个环节一环扣一环哪个理解不到位都容易卡壳。这也是为什么我说它是一道非常典型的前缀和综合练习题。2. 二维前缀和一维区间和的升级版2.1 一维前缀和从 O(n) 到 O(1)在进入二维之前先快速回顾一维前缀和。给定一个数组 a[1] 到 a[n]我们可以预处理一个前缀和数组 s其中 s[i] a[1] a[2] ... a[i]。这样要查询 a[l] 到 a[r] 的和只需要计算 s[r] - s[l-1]时间复杂度是 O(1)。这个操作的本质是用“预处理时的加法”换“查询时的减法”。一维查询是一次减法二维查询会变成四次加减法因为二维比一维多了一个维度需要处理重叠区域的容斥关系。很多同学一上来就记二维前缀和的公式死记硬背很容易把符号搞反。建议你先理解它的几何意义s[i][j] 表示从矩阵左上角 (1,1) 到 (i,j) 这个矩形范围内所有数的和。如果你能把这个“矩形面积和”的图景刻在脑子里后面的公式自己就能推出来。2.2 二维前缀和的构造加两次减一次二维前缀和的构造公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j];这个公式看着有点绕其实可以这样理解pre[i][j] 这个大矩形等于上方的矩形 pre[i-1][j] 加上左边的矩形 pre[i][j-1]。但这两个矩形都包含了左上角那块 pre[i-1][j-1]所以加了两次必须减掉一次最后再加上当前格子 a[i][j]。这就是“容斥”思想。举一个生活化的例子你想知道一个大长方形菜园里种了多少棵菜可以先数上面一半再数左面一半但左上角那个小方块被数了两次所以要扣掉一次最后再加上右下角新发现的菜。二维前缀和就是把这个思路用数学公式固定下来。代码层面注意下标从 1 开始pre 数组的 0 行、0 列全部初始化为 0。这样处理 i1 或 j1 时pre[0][j]、pre[i][0]、pre[0][0] 都参与运算但不会越界。全局数组默认就是 0不需要手动初始化。2.3 任意子矩阵和四步容斥构建好 pre 数组之后我们要查询从 (x1, y1) 到 (x2, y2) 这个子矩阵的和公式是sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1];这里同样是容斥整体大矩形 pre[x2][y2] 减去上方多出来的部分、减去左方多出来的部分但左上角那一块被减了两次所以要加回来。你可以类比一维一维是一次减法二维是两次减法加一次加法多出来的一个维度对应多一次容斥。以 2.1 里那个 2×3 矩阵为例构建后 pre 的值是pre[1][1] 1pre[1][2] 2pre[1][3] 3pre[2][1] 2pre[2][2] 4pre[2][3] 4查询左上角 2×2 区域从 (1,1) 到 (2,2)的和就是 pre[2][2] - pre[0][2] - pre[2][0] pre[0][0] 4 - 0 - 0 0 4正好等于 2×2 全 1 的和说明公式没问题。如果你在本地调试时不确定自己的前缀和写没写对这就是一个非常好的手算验证方法。3. 二分答案 前缀和把求“最大”变成判“可行”3.1 单调性是二分的基石看到“最大正方形边长”第一反应可能是直接枚举边长从 1 试到 min(n,m)每试一个边长就扫描一遍矩阵。这样总复杂度大约是 O(nm·min(n,m))在 n、m 只有 100 时能过但数据一旦变大就吃力。更聪明的办法是二分答案因为这个问题具备一个关键性质单调性。如果边长为 k 的全 1 正方形存在那么边长小于 k 的全 1 正方形一定也存在——你只需要从那个大正方形里切出一个左上角的小正方形即可。反过来如果边长 k 不存在那么边长大于 k 的也一定不存在因为更大的正方形如果存在里面必然包含了某个 k×k 的全 1 区域。这个“越大的越难满足”的单调性正是二分答案可以使用的信号。我们的目标从“找最大边长 k”变成了“判断给定的 mid 是否可行”而可行性的判断正好可以交给前缀和 O(1) 完成。二分答案把外层枚举从 O(min(n,m)) 降到了 O(log min(n,m))效果非常明显。3.2 check 函数怎么写check 函数的任务很简单判断是否存在某个边长为 len 的全 1 正方形。做法是枚举所有可能的左上角位置 (i,j)用二维前缀和计算以它为左上角、边长为 len 的正方形区域和然后看这个和是否等于 len×len。如果矩阵里全是 1区域和自然等于 len×len只要出现一个 0区域和就会比 len×len 小。所以等值判断就能准确区分“全 1”和“有 0”。枚举左上角时要注意边界条件左上角坐标 i 必须满足 i len - 1 n即正方形不能超出矩阵下边界同理 j len - 1 m不能超出右边界。很多同学会在这里写成 i len n导致最后一行或最后一列永远枚举不到如果最大正方形恰好贴边答案就会偏小。这个细节后面还会再强调。下面是 check 函数的一种实现配合 pre 数组可以做到每次查询 O(1)bool check(int 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 sum pre[x2][y2] - pre[i-1][y2] - pre[x2][j-1] pre[i-1][j-1]; if (sum len * len) return true; } } return false; }这个函数在任何 len 大于 0 时都不会越界因为 pre 数组的 0 行 0 列全是 0。如果 len 为 0公式本身没有意义所以我们二分时把左边界设为 1用答案变量单独兜底处理全 0 矩阵的情况。3.3 复杂度估算与数据范围构建二维前缀和需要 O(nm) 的时间。二分答案的区间是 [1, min(n,m)]所以二分次数是 O(log min(n,m))。每一次 check 都要遍历所有可能的左上角位置数量大约是 (n - len 1) × (m - len 1)最坏情况下约等于 nm 个位置每个位置一次前缀和查询是 O(1)。所以总复杂度为 O(nm log min(n,m))。空间上需要一个 pre 二维数组大小和原矩阵相同所以空间复杂度是 O(nm)。原题 n、m 只有 100这个复杂度看起来“杀鸡用牛刀”但它展示了一套可以迁移到更大数据范围的通用方法。如果 n、m 都到 1000O(nm log min(n,m)) 大概是 1000×1000×10 10^7 量级依然能在常规时限内跑完而纯暴力枚举边长加遍历正方形则是 O(nm·min(n,m)²)这时候早就超时了。4. 完整代码与边界细节4.1 C 代码把前面所有思路拼起来就是下面这份完整代码。我用的是最朴素的写法重点在于把逻辑说清楚方便你直接照着敲。#include bits/stdc.h using namespace std; const int MAXN 105; int a[MAXN][MAXN]; int pre[MAXN][MAXN]; int n, m; bool check(int 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 sum pre[x2][y2] - pre[i-1][y2] - pre[x2][j-1] pre[i-1][j-1]; if (sum len * len) return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]; } } int l 1, 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; } } cout ans \n; return 0; }我在读入 a[i][j] 的同时就顺手构建了 pre省去一次双重循环。这样做完全没问题但有个前提你心里要清楚 pre[i-1][j]、pre[i][j-1]、pre[i-1][j-1] 这三个值在循环进行到 (i,j) 的时候都已经被计算过了。如果不太习惯也可以先单独读入 a再单独循环构建 pre逻辑更直白损失一点常数时间而已。4.2 二分边界与答案初始化二分模板我用的是闭区间写法l1rmin(n,m)while(lr)mid(lr)/2。当 check(mid) 为真时说明 mid 可行但可能存在更大的边长所以更新 ansmid并把左边界 l 调到 mid1当 check(mid) 为假时说明 mid 太大把右边界 r 调到 mid-1。这个模板不容易死循环前提是你必须用心维护“左闭右闭”的区间含义。答案变量 ans 初始化为 0而不是 1。这是很多同学容易踩的坑如果矩阵里一个 1 都没有最大正方形边长应该是 0但如果你把 ans 初始化为 1二分结束会直接输出 1造成错误。虽然洛谷 P1387 的原题数据不一定有这个极端情况但 GESP 考试可能会故意放一个全 0 矩阵来卡粗心的人养成 ans0 的习惯更稳妥。另一种常用的写法是把二分区间设为 [0, min(n,m)]但 check(0) 会变成一种特殊情况处理起来反而麻烦。我更推荐 l1、ans0 的组合正常情况二分找答案全 0 时 check(1) 直接失败ans 保持 0一举两得。4.3 数组下标从 1 开始的好处我刻意让矩阵下标从 1 开始而不是从 0 开始。原因很简单前缀和公式里有大量 i-1、j-1、x1-1 之类的表达式如果矩阵下标从 0 开始那么当 i0 时 i-1 就会变成 -1要么特判一堆边界要么给 pre 数组多开一圈并偏移下标。从 1 开始的话pre[0][j] 和 pre[i][0] 天然就是 0所有公式无需任何分支判断代码瞬间清爽很多。这不是什么高深技巧但很多人写前缀和时习惯沿用平时数组从 0 开始的做法结果在边界处理上反复出错。我的建议是只要题目没有强制要求从 0 读入写前缀和相关代码一律从 1 开始。你只需要在读入时让 i、j 从 1 循环到 n、m其他逻辑全部顺势简化。5. 对照动态规划如何解决同一道题5.1 状态与转移P1387 还有一个更经典的解法动态规划。定义 dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。如果 a[i][j] 本身是 0那么以它为右下角不可能形成任何全 1 正方形所以 dp[i][j]0。如果 a[i][j] 是 1情况就值得推敲了。要形成一个边长为 k 的正方形并且右下角是 (i,j)那么它的上方 (i-1,j) 这个位置必须能提供一个边长为 k-1 的正方形左方 (i,j-1) 也必须能提供一个边长为 k-1 的正方形左上角 (i-1,j-1) 同样如此。三个条件缺一不可所以if (a[i][j] 1) dp[i][j] min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) 1; else dp[i][j] 0;最终的答案就是所有 dp[i][j] 里的最大值。这个转移只需 O(1) 时间整体复杂度是 O(nm)比前缀和二分还快一个 log 因子。5.2 为什么是 min 不是 max这是 DP 解法里最核心的问题。直观上可能会想三个方向都取最大值再加一不是能拼出更大的正方形吗错。你真正需要的是三个方向同时“够用”。用生活化的例子来说你想在墙角放一个方形的收纳柜它要贴着左墙、后墙和墙角。如果左墙到墙角只有 1 米后墙到墙角有 2 米墙角对角线区域也只有 1 米那你能放的柜子边长只能是 1 米而不是 2 米。因为最短的那块空间卡住了整个柜子。dp 转移里的三个方向就是这堵“左墙”“后墙”和“墙角区域”任何一个方向不够长整体就扩大不了。如果写成 max就会出现一个很隐蔽的错误比如一个 L 形区域横向和纵向分别都有很长的 1但斜对角没有形成足够大的方块max 会把不存在的正方形“脑补”出来。所以在理解 DP 解法时一定要反复跟自己确认正方形是二维整体不是一维线段的叠加必须取三个方向的短板也就是最小值。5.3 两种解法怎么选我个人的看法是如果是 GESP 五级的前缀和练习优先写前缀和二分。原因很直接——这道题放在“前缀和练习”标题下训练目标就是让你熟练使用二维前缀和你写 DP 虽然也能过但练不到这个知识点。而且前缀和二分的思路更通用将来遇到“最大子矩阵”“子矩阵和等于某个值”这类问题你会有更灵活的武器。如果是正式比赛且你非常确定这道题可以用 DP那 DP 的 O(nm) 复杂度确实更优代码也更短。但 DP 的难点在于证明转移方程如果你对“为什么取 min”没有十足把握比赛时可能会犹豫。相比之下前缀和二分几乎没有需要“顿悟”的环节每一步都是机械而清晰的推导更适合在时间紧张时稳定输出。6. 实战踩坑与调试经验6.1 前缀和公式写错的一种典型症状二维前缀和公式最容易写错的是 pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j] 中间的符号。有人会把减号写成加号或者漏掉最后那个 a[i][j]。这种错误很隐蔽因为程序不会崩溃但输出会莫名其妙地偏大。症状非常好认check 函数里明明某个正方形区域内有 0但算出来的 sum 却等于 len×len导致错误地判定为“可行”。根本原因是 pre 数值整体被高估区域和也跟着虚高。排查方法也很简单随便取一个已知的小矩阵比如 2×2 全 1 矩阵手算一遍 pre 应该是什么值再打印出来对比。只要你愿意花三分钟做一次手算验证这类错误基本能当场暴露。6.2 二分死循环和答案偏小二分部分最常见的两个问题一个是死循环一个是答案偏小。死循环通常源于更新边界时用了 rmid 或 lmid而没有 1/-1。闭区间模板里如果 check(mid) 为真说明答案至少是 mid下一步要往更大的方向试探所以 lmid1如果 check(mid) 为假说明 mid 太大了下一步要往小方向试探所以 rmid-1。两边都做好 1/-1循环一定会在有限步内退出。答案偏小的原因我前面提到过枚举左上角时边界写成了 i len n而不是 i len - 1 n。比如 n4len3i len 4 4 会让 i 最大取到 1而实际上 i 可以取 1 或 2。这个 bug 在矩阵比较小或最大正方形不贴边时很难发现但一旦最大正方形正好贴着最后一行或最后一列答案就会少 1。调试时可以专门构造一个“最大正方形在右下角”的测试数据比如一个 5×5 矩阵右下角是 3×3 全 1看看程序能不能输出 3。6.3 对拍用暴力验证一切无论你写的是前缀和还是 DP我都强烈建议在本地写一个暴力版本用来对拍。暴力思路很简单枚举所有可能的左上角 (i,j)再枚举边长 k逐个格子检查正方形内是否全为 1。只要 n、m 不超过 5这个暴力程序瞬间就能跑完。对拍的具体流程是写一个随机数据生成器生成几组 n、m 都很小的 0/1 矩阵分别跑暴力和你的优化算法比对输出是否一致。如果结果不一致就打印出矩阵、两个程序的输出然后人工分析哪一步出了问题。这个方法不需要任何高深工具但几乎能帮你解决所有隐藏 bug尤其是前缀和这类“公式看着对但一跑就错”的情况。6.4 GESP 考场上的一点建议最后聊点考场上实际有用的经验。GESP 五级的前缀和题目通常不会给特别夸张的数据范围所以你不必为了常数优化过度纠结更重要的是把思路写清楚降低出错率。我一般按这个顺序做题先把题意完全读懂确定输入输出格式然后看数据范围如果 n、m 很小可以先在草稿纸上想清楚暴力解法确保自己对题意理解正确再往优化方向想看能不能用前缀和或者 DP。P1387 这种题关键词“矩阵”“全 1”“正方形”出现时应该立刻在脑子里弹出两个候选方案前缀和二分、DP。你可以都推一遍选自己最有把握的那个写。写完之后不要立刻提交先拿手算样例走一遍流程确认输出符合预期再交上去。另一个容易被忽视的点是读入优化。虽然 n、m 不影响大局但加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是一个好习惯避免某些测试点数据偏大时 cin 成为瓶颈。如果考试环境实在不允许用 bits/stdc.h就把头文件换成标准的 iostream、algorithm 等核心代码不用变。做完之后我习惯再用全 0 矩阵和全 1 矩阵各测一次前者应该输出 0后者应该输出 min(n,m)这两个极端情况能过滤掉大部分边界错误。