昨天晚上把ABC447的ACEF四个题完整过了一遍说实话这套题的整体节奏比前几场要舒服一些——没有那种“一眼看不出做法就当场卡死”的题但每一道题的细节都藏得比较深。A题是数学送分题C题是前缀和的套路变形E题是老朋友LISF题则是单调栈的经典应用。这篇就按我实际做题的顺序把ACEF四题的思路、证明、代码和踩坑点都聊一遍尽量让没写出来的同学也能照着把代码敲出来。1. A 题的 lcm 边界从“不超过 N 的最大公倍数”开始1.1 题意与核心公式先复述一下A题的题意给定三个正整数 A、B、N要求找一个不超过 N 的最大整数 x使得 x 同时能被 A 和 B 整除。如果不存在这样的整数输出 0。这类题第一反应肯定是“找一个数它既是 A 的倍数又是 B 的倍数”那本质上就是求 A 和 B 的最小公倍数的倍数。设 l lcm(A, B)那么所有同时被 A 和 B 整除的数就是 l, 2l, 3l, ...要求的答案就是不超过 N 的最大 l 的倍数。所以核心公式很简单ans floor(N / l) * l这里 floor 就是整数除法向下取整。唯一需要绕一下的是 l 怎么求lcm(A, B) A / gcd(A, B) * B为什么顺序要写成“先除后乘”因为如果直接写 A * B / gcd(A, B)在 C 里可能中间结果 A * B 直接溢出 long long尤其是当 A、B 都是 1e18 级别的时候。先除再乘中间结果最大不会超过 B就能安全很多。Python 没有整型溢出问题所以怎么写都无所谓但如果你用 C 打比赛这个顺序习惯最好从一开始就养成。1.2 边界情况N 比 lcm 还小这题最容易翻车的不是 gcd 不会写而是边界情况判断漏掉。比如 N 5, A 6, B 9lcm 18显然 1 到 5 里面没有任何数能被 18 整除答案就是 0。用公式算就是 (5 / 18) * 18 0 * 18 0完全没问题不需要额外特判。还有一类情况在题目里很常出现A 和 B 本身就可能相等。A 8, B 8 的时候gcd 8lcm 8答案就是在 1 到 N 里找最大的 8 的倍数。有些同学写 gcd 时会先特判 a b其实完全没必要gcd 算法本身已经处理了这种情况。我复盘的参考代码C 版本如下#include bits/stdc.h using namespace std; using int64 long long; int main() { int64 A, B, N; cin A B N; int64 g gcd(A, B); int64 l A / g * B; int64 ans (N / l) * l; cout ans \n; return 0; }Python 版本更短import math A, B, N map(int, input().split()) l A // math.gcd(A, B) * B print((N // l) * l)1.3 这题真正想考的是什么A题虽然简单但它实际上是在考一个很容易被忽略的数学常识公倍数和最小公倍数的关系。如果你在赛场上把 lcm 求出来这题就是 30 秒的题。如果你一时没想到 lcm而是选择从 N 往下枚举 x那最坏情况要枚举 N 次数据一大就直接超时。另外关于“不超过 N 的最大倍数”很多人都知道答案是 (N / d) * d但有时会把整除写成浮点数除法再取整这样会引入精度问题。整数题里老老实实用整数除法是最稳的。A题就到这里下一题是C题它才是这套题里第一个值得停下来想两分钟的地方。2. C 题的前缀和哈希零和子数组为什么能用一重循环2.1 题意与朴素思路C题题意大致是给定一个长度为 N 的整数数组 A数组元素可能包含负数要求统计有多少个连续子数组满足子数组内所有元素之和等于 0。比如 A [3, -1, -2, 5, -5]那么 [3, -1, -2] 是一个零和子数组[5, -5] 也是但 [3, -1, -2, 5, -5] 整体也是因为总和是 0。如果没接触过前缀和很容易直接写一个 O(N^2) 的枚举枚举左端点 i再枚举右端点 j维护从 i 到 j 的和。数据小的时候没问题但 ABC 的题一般 N 给到 2e5O(N^2) 直接爆炸。这题的关键在于把“子数组和等于 0”变成“两个前缀和相等”。2.2 核心转化pre[r] 等于 pre[l-1]记前缀和数组 pre[i] 表示从第 1 个元素到第 i 个元素的和特别地 pre[0] 0。那么子数组 A[l..r] 的和可以写成sum(l..r) pre[r] - pre[l-1]如果 sum(l..r) 0那就有pre[r] pre[l-1]也就是说我只需要统计有多少对位置 (l-1, r) 满足 pre 值相同其中 l-1 r。这本质上是“在遍历过程中每遇到一个新的前缀和值就看看之前有多少个位置的前缀和等于它”。举个具体例子A [1, -1, 0]pre[0] 0pre[1] 1pre[2] 0pre[3] 0可以看到 pre 等于 0 的位置有 0、2、3任意选两个不同的位置都对应一个零和子数组。选 (0, 2) 对应 A[1..2] [1, -1]选 (0, 3) 对应 A[1..3] [1, -1, 0]选 (2, 3) 对应 A[3..3] [0]一共 3 个和手动枚举结果一致。所以做法就清晰了用一个哈希表记录每个前缀和已经出现的次数遍历数组的同时维护当前前缀和 pre每次更新后把 pre 出现的次数加到答案里再把当前 pre 的计数加一。2.3 计数代码与初始化陷阱C 参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorlong long A(N); for (int i 0; i N; i) cin A[i]; unordered_maplong long, int cnt; cnt[0] 1; // 前缀和 pre[0] 0 long long pre 0, ans 0; for (int i 0; i N; i) { pre A[i]; ans cnt[pre]; cnt[pre]; } cout ans \n; return 0; }Python 参考代码from collections import defaultdict N int(input()) A list(map(int, input().split())) cnt defaultdict(int) cnt[0] 1 pre 0 ans 0 for x in A: pre x ans cnt[pre] cnt[pre] 1 print(ans)这里最容易被忽略的一点就是 cnt[0] 1 必须在遍历前就设置好。为什么因为 pre[0] 0而它也是一个真实存在的前缀位置。如果本来没有这句当数组第一个元素就是 0 的时候pre[0] 和 pre[1] 都是 0你应该算出至少一个零和子数组但少了 cnt[0] 就会把这一组漏掉。再补充一个容易踩的位点如果整个数组全为 0比如 [0, 0, 0]那任意子数组和都是 0总共有 6 个。用上面的代码跑初始 cnt[0] 1第一次 pre 0ans 1cnt[0] 2第二次 pre 0ans 2cnt[0] 3第三次 pre 0ans 3cnt[0] 4最终 ans 1 2 3 6。这个流程能加深对“计数后自增”的理解第 i 次遇到同一个前缀和意味着它能和之前所有相同前缀和的位置拼出子数组。2.4 复杂度与实战注意时间 O(N)空间 O(N)。这道题的哈希表操作是整个优化的核心如果使用 C 的 unordered_map最坏情况下可能有哈希碰撞导致退化但竞赛数据一般不会刻意卡这个用起来问题不大。如果你非常在意稳定性可以改用 map 或者自己写哈希但复杂度会多一个 log。另外注意题目问的是连续子数组不是子序列也不是排列组合。连续这个条件决定了它一定能用前缀和来压缩。要是题目问“有多少对 i j 使得某个后缀条件成立”可能又是另一种套路了。C题本身不难能在一开始就想到前缀和说明这类“区间和”模型已经形成条件反射了。3. E 题的 LIS二分维持最小末值的思想比背模板更重要3.1 题意与朴素的 O(N^2) DPE题是经典的最长上升子序列LIS问题。题意给定长度为 N 的数组 A找一个最长的严格递增子序列不要求连续只要求元素下标递增、值严格递增。输出这个最长长度。这类题在算法竞赛里出现频率太高了但正因为太常见反而有很多人只会背代码不知道为什么对。我先从最朴素的 DP 说起方便没做过的人跟上。定义 dp[i] 表示以 A[i] 结尾的最长上升子序列长度。转移方程dp[i] max(dp[j] 1)其中 j i 且 A[j] A[i]初始每个 dp[i] 1因为单个元素本身就是一个长度 1 的上升子序列。直接两层循环时间复杂度 O(N^2)。数据范围 N ≤ 2e5 时就过不了了必须优化。3.2 贪心观察同样长度下末尾越小越好优化的核心不是去记录“以某个具体元素结尾的最长长度”而是换一个角度记录“长度为 i 的上升子序列它的最小可能末尾元素是多少”。为什么只看最小末尾就够了考虑两个上升子序列长度都为 3一个末尾是 10一个末尾是 3。现在有一个新元素 x 5 来了它能接在末尾为 3 的序列后面却不能接在末尾为 10 的序列后面。显然末尾越小未来扩展空间越大。所以在维护所有长度为 len 的子序列时我们只需要关心最小的那个末尾别的都可以丢掉。定义一个数组 tailstails[len] 表示当前已经找到的长度为 len 的上升子序列的最小末尾值。遍历原数组中的每个 x我们要找的是tails 中第一个大于等于 x 的位置然后把这个位置的值替换成 x。为什么是“第一个大于等于 x 的位置”因为 tails 本身是严格递增的。如果 tails[k] x说明 x 可以接在长度 k 的子序列后面形成长度 k 1 的子序列。我们要找的是最长的 k 满足 tails[k] x那么替换的位置就是 k 1。等价于在 tails 里二分查找第一个大于等于 x 的位置也就是 C lower_bound 的语义。3.3 二分实现与代码C 版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorint A(N); for (int i 0; i N; i) cin A[i]; vectorint tails; for (int x : A) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } cout tails.size() \n; return 0; }Python 版本from bisect import bisect_left N int(input()) A list(map(int, input().split())) tails [] for x in A: i bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x print(len(tails))这里 lower_boundPython 是 bisect_left能找到第一个不小于 x 的位置。如果 x 比 tails 里所有数都大就说明 x 可以接在现有最长序列后面形成更长的序列所以直接 push_back。3.4 容易搞混的边界严格递增 vs 非严格递增很多同学在网上看到 LIS 有“lower_bound 版本”和“upper_bound 版本”但不知道什么时候用哪个。规则其实就一句话要求严格递增A[j] A[i]时用 lower_bound / bisect_left找第一个大于等于 x 的位置。要求非严格递增A[j] ≤ A[i]时用 upper_bound / bisect_right找第一个大于 x 的位置。为什么因为如果是非严格递增x 可以接在末尾同样等于 x 的序列后面所以替换时不能把相等的值后代覆盖掉而是要往后找。反过来严格递增时x 遇到和自己相同的值只能替换它而不能接在它后面否则就破坏了严格递增条件。E题里我把“严格递增”单独拿出来说是因为题目如果没看仔细很容易在这里丢掉好几分钟。拿一个数据测试一下A [2, 2, 2]。严格递增的答案是 1非严格递增的答案是 3。用 lower_bound 跑严格递增版本第一次 x2tails 空则 append第二次 x2lower_bound 找到位置 0替换为 2第三次同理tails 长度始终是 1答案正确。如果换用 upper_bound第二次和第三次都会 append长度变 3那就错了。E题其实没有新的算法它考察的是能不能理解 tails 数组的贪心含义而不是遇上 LIS 就直接套模板。理解了“最小末尾”这个思想之后后面遇到带限制了上升子序列变体比如“每个元素最多只能使用一次”“要求输出具体序列”也能从这基础上往下想。4. F 题单调栈直方图最大矩形中“左边更矮的柱”才是关键4.1 题意与暴力做法F题题意给定一个直方图由 N 根宽度为 1 的柱子组成第 i 根柱子的高度是 h[i]。现在要求在直方图内部找一个面积最大的矩形这个矩形的底边必须落在 x 轴上且完全被柱子覆盖。求最大面积。暴力做法是枚举每根柱子 i把它作为矩形上边界高度的基准然后往左往右扩展直到遇到一根高度小于 h[i] 的柱子为止。对每个 i 能扩展出的宽度是 right[i] - left[i] - 1面积就是 h[i] * 宽度。所以问题的关键变成了对每根柱子找到它左边第一根严格更矮的柱子的位置以及右边第一根严格更矮的柱子的位置。这个“找左右第一个更矮元素”的问题正好是单调栈的标准场景。4.2 单调栈如何维护左右边界先从左到右扫一遍维护一个高度单调递增的栈。栈里存的是下标但保证这些下标对应的高度从栈底到栈顶是递增的。当处理到柱子 i 时不断弹出栈顶直到栈顶的高度小于 h[i]。弹完之后如果栈为空说明左边没有比它更矮的柱子那么 left[i] -1否则 left[i] 栈顶下标。为什么弹出那些高度大于等于 h[i] 的柱子因为它们对“找 h[i] 左边第一个更矮柱”这件事已经没用了。凡是高度不低于 h[i] 的柱子都不可能成为 h[i] 的“更矮左边界”它们的存在只会挡住视野。弹出之后栈顶就是距离 i 最近的那根更矮柱子。右边同理从右往左扫一遍用同样的规则得到 right[i]。最后对每个 i 算面积area h[i] * (right[i] - left[i] - 1)取最大值。C 参考代码#include bits/stdc.h using namespace std; using int64 long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorint64 h(N); for (int i 0; i N; i) cin h[i]; vectorint left(N), right(N); vectorint st; // 左边第一个严格更矮的柱 for (int i 0; i N; i) { while (!st.empty() h[st.back()] h[i]) st.pop_back(); left[i] st.empty() ? -1 : st.back(); st.push_back(i); } st.clear(); // 右边第一个严格更矮的柱 for (int i N - 1; i 0; i--) { while (!st.empty() h[st.back()] h[i]) st.pop_back(); right[i] st.empty() ? N : st.back(); st.push_back(i); } int64 ans 0; for (int i 0; i N; i) { ans max(ans, h[i] * (right[i] - left[i] - 1)); } cout ans \n; return 0; }Python 参考代码N int(input()) h list(map(int, input().split())) left [0] * N right [0] * N st [] for i in range(N): while st and h[st[-1]] h[i]: st.pop() left[i] st[-1] if st else -1 st.append(i) st.clear() for i in range(N - 1, -1, -1): while st and h[st[-1]] h[i]: st.pop() right[i] st[-1] if st else N st.append(i) ans 0 for i in range(N): ans max(ans, h[i] * (right[i] - left[i] - 1)) print(ans)4.3 相等高度的柱子怎么处理F题最容易出错的地方就是相等高度。假设 h [2, 2]两根柱子高度一样最大矩形面积显然是 2。我在写代码时两个方向都用了“h[st.back()] h[i]”作为弹出条件也就是弹出所有高度不小于当前柱子高度的柱子。这样左边第一根更矮的柱子是严格更矮右边第一根更矮的柱子也是严格更矮。于是对第 0 根柱left[0] -1right[0] 1面积 2 * (1 - (-1) - 1) 2。对第 1 根柱left[1] 0right[1] 2面积 2 * (2 - 0 - 1) 2。结果正确。如果只在一边用“”另一边用“”就很容易出现把相等高度柱子也算进去导致宽度算多的情况。不要小看这个细节直方图最大矩形这道题在 LeetCode 上也是经典题很多讨论区的错误代码都挂在 height 相等这一组数据上。4.4 单调栈为什么会把复杂度降下来每个元素只会被压入栈一次、弹出栈一次所以两遍扫描总复杂度是 O(N)。相比之下暴力扩展每个柱子左右边界最坏情况下要 O(N^2)。单调栈本质上是利用“已经被弹出的柱子不可能再作为后续柱子的边界”这一性质把重复比较省掉了。如果你之前对单调栈一直似懂非懂我的建议是别急着背代码先画一组数据比如 h [2, 1, 5, 6, 2, 3]手动模拟一遍“什么时候压入、什么时候弹出”。模拟到中途你会发现“栈顶就是当前位置左边最近的更矮柱”这个结论会变得非常直观。F题到这里也就解完了核心就在两行 while 循环里。能够正确搞懂 left 和 right 的边界含义这类题基本就稳了。5. 赛后复盘ACEF 四道题最容易让人丢分的三个细节5.1 做题顺序带来的心态差别这次 ABC447 我先把 A 题写了然后直接跳到了 C 题因为 C 题一看就知道是“区间和”模型先写不会太影响心态。E 题和 F 题放在后面因为这两道题即使思路清楚了代码里的二分边界和栈的弹出条件也需要更多时间验证。有一个很实际的点打 ABC 类的比赛不一定非要按题号顺序写。优先做自己最有把握的题再啃难点心理压力会小很多。A 题求 lcm 时我特意提醒自己不要写 A * B / gcd就是因为之前有场比赛在 lcm 上栽过跟头。5.2 一张复盘表总结四题题号核心算法时间复杂度最容易丢分的点Agcd / lcm整除公式O(log min(A, B))lcm 中间过程溢出忘记答案可能为 0C前缀和 哈希表计数O(N)漏掉 cnt[0] 1 的初始化计数顺序写反E二分维护最小末尾值O(N log N)严格递增误用 upper_boundtails 数组含义没理解透F单调栈O(N)左右边界初始化相等高度柱子的弹出条件不一致这张表不是让你赛前背的而是赛后用来查缺的。上面列的每一个“丢分点”都对应一条具体的代码 bug而不是玄学失误。A 题溢出属于数值类型问题C 题初始化属于边界问题E 题二分边界和 F 题弹出条件属于“算法语义没吃透”的问题。把它们分类记忆下次再遇到同类题就会下意识检查这些位置。5.3 我在实际调试中的一点体会ACEF 四题里C 题和 F 题虽然算法完全不同但它们的核心思想其实是一家人都在用“之前的信息”加速“当前答案的计算”。C 题用哈希表记录前缀和出现次数F 题用栈记录更矮柱子的位置本质上都是对历史信息的压缩。如果只是把代码抄一遍下次遇到变体还是会卡住。我更推荐的做法是每次写完题解后把题目稍作修改再自测一次。比如 C 题改成统计“和为 K 的子数组个数”E 题改成求“非严格递增的最长长度”F 题改成“柱子高度可能有 0”。这些变体往往能把你自以为懂了的地方重新打回原形。ABC447 这套 ACEF 题整体难度梯度拉得比较开但对算法的考察都很正统没有任何偏门考点。把 lcm、前缀和、LIS、单调栈这四个基础模型吃透不仅这次比赛能用后面很多比赛里也都会反复遇到。