一场区域赛结束真正能被记住的往往不是榜单上的排名而是那些赛场上卡了两个小时、下来之后一拍大腿的题。这篇接上一篇继续写 2025 年 ICPC 沈阳区域赛的题解梳理主要挑我在赛后复盘里觉得最有价值的几道题展开有快速拿分的贪心有需要优化才能过的 DP也有几道题 AC 率不高的原因根本不在算法本身而在读写开销和状态设计的细节上。如果你是准备区域赛的选手这篇的定位是“赛后复盘笔记”不是官方题解合集。题号顺序我按赛场难度和讲解价值重新排过每组都会先说思路再补实现细节和卡点最后给一段我自己的教训总结。代码以 C17 为主部分题目我给了复杂度推导。1. 先说选题这场的题单我挑哪些出来写沈阳这场整体给我的感觉是签到题和简单题非常友好中档题的分层做得比较明显难题的思维量集中但代码量不算爆炸。这种题单结构其实很适合训练队伍的比赛策略——前两个小时能不能把简单题全部稳住直接决定你在中档题上的心态和剩余时间。我选了五道题作为这期博客的主体题号核心考察点赛场定位讲解重点A排序 贪心区间覆盖变形签到/快拿分贪心策略证明B线性 DP前缀和优化中档从 O(n²) 到 O(n log n) 的剪枝路线C图论建模状态压缩中档偏上状态设计如何避开重复计算D线段树区间合并懒标记下推中档维护信息的边界定义E哈希 二分字符串匹配变体中档复杂度分析上的陷阱这几道题里B 和 D 是最值得反复咀嚼的B 的优化思路在很多区域赛题里都会复用D 的坑则完全属于“样例过了但大数据 TLE/MLE”的典型场景。2. 签到与简单题赛场前两小时怎么把分拿稳2.1 A 题排序后扫一遍但要证明贪心成立A 题题面我赛后简写如下给 n 个区间每个区间有一个收益 w_i要求选若干个互不重叠的区间让总收益最大n 最大 2×10⁵。第一眼这就是经典区间调度问题但是收益不是单位长度所以不能直接按右端点排序后无脑选。正确做法是按右端点排序然后用线段树或树状数组维护“到当前位置为止的最大收益”。在赛场上我们先用了一个更直接的贪心版本结果在样例扩展测试上 WA 了一次原因很典型区间权重不相等时按右端点排序后“能选就选”的策略在局部最优上会翻车。比如区间 [1,3] 收益 100 和 [2,4] 收益 99按右端点排序先看 [1,3]选了它[2,4] 就不能再选但最优解其实是选 [2,4] 再加一个更早的区间。所以最后实现走了 DP 离散化把区间端点离散化状态 dp[i] 表示在坐标 i 之前能拿到的最大收益转移就是要么继承 dp[i-1]要么取所有右端点等于 i 的区间用 dp[l-1] w 来更新。树状数组维护前缀最大值即可。这个思路代码不长但比起无脑贪心多了一个证明维度签到题里算稍有区分度。struct Seg { int l, r, w; bool operator(const Seg other) const { return r other.r; } }; // 离散化后按 r 排序树状数组前缀 max 更新复杂度 O(n log n)离散化时注意区间端点是闭区间左端点取 l 还是 l-1 取决于你 DP 状态的下标语义。我们队在这个小细节上差点处理错后面 D 题也遇到类似的“下标边界”问题建议各位在写区间类 DP 时把闭区间转换统一写成一个函数。2.2 赛场上的读题顺序策略这场我们队的读题顺序是 C、A、B、E、D原因是 C 题题面最短适合先确定它是不是签到。结果 C 是一道伪签到实际难度比 A 高我们多花了十五分钟才发现这一点。我的建议是开局让代码手先过一遍所有题的样例解释不用读全题面只看输入输出样例能不能猜出基本题意。今年沈阳的 A 和 B 都能靠样例猜出九成直接省掉大量读题时间。这个习惯我们练了大半年区域赛上效果很明显。3. 把 O(n²) 摁进 O(n log n)一道 DP 的剪枝路线3.1 原题语义与我重构后的版本B 题原题我重构一下核心结构给一个长度为 n 的数组 a要求把数组切成若干段每段的代价是“段内不同元素数量”的平方求最小总代价。n ≤ 10⁵a_i ≤ n。第一反应是裸 DP设 f[i] 表示前 i 个元素的最小代价那么f[i] min(f[j] cost(j1, i))其中 j 从 0 到 i-1。这个转移一看就是 O(n²) 的n 到 10⁵ 直接爆炸。但这里有个关键观察平方项增长很快段内不同元素数量超过某个阈值时不如直接每个元素单独成段——单元素段的代价恒为 1所以总代价上界是 n。于是可以设阈值 K只枚举那些段内不同元素数量 ≤ K 的转移。这个 trick 在很多“平方代价分段 DP”里都能用核心原因在于平方函数的凸性超过一定长度后分段一定更优。3.2 阈值 K 的选取与复杂度推导K 取多少合适如果某一段的不同元素数量超过 K它的代价至少是 (K1)²而如果把它拆成若干个单元素段总代价不超过 K1。所以只要 (K1)² K1即 K ≥ 1 时这样的段就不可能是最优解的一部分。更精确地说如果当前全局最优上界是 n全部分成单段那么任何代价大于 n 的段都不可能出现在最优解里因此 K ⌊√n⌋ 就够了。转移时维护一个双指针滑动窗口窗口内维护不同元素数量 cnt。对于固定的 i左端点 j 往左移动一格就加入一个元素我们用 last 数组记录每个元素上一次出现的位置实时维护 cnt。枚举所有 cnt ≤ K 的左端点用 f[j] 更新 f[i]同时用当前窗口的 cnt² 作为代价。枚举完左端点后再往前移动 i窗口自动扩展。这里的细节是双指针维护的是“以 i 为右端点、不同元素数量 ≤ K 的最左边界”。超过边界之后的转移可以直接 break因为再往左 cnt 只会更大必然不会更优。实测 K √n 时总转移量是 O(n√n)对 10⁵ 的数据完全跑得动。3.3 我踩过的坑last 数组的初始化这道题我第一次写的时候last 数组初始化为 0但元素值可能从 0 开始导致第一个元素被误判为“已出现过”窗口 cnt 从 0 开始多算了一格。WA 了三发才定位到。建议统一把 last 初始化为 -1并保证 a_i 的取值不会出现负数这个坑在字符串哈希、双指针类题目里也经常出现属于“初始化污染状态”的典型案例。for (int i 0; i n; i) { // 枚举合法左端点 while (ptr i cnt K) { // 收缩左边界 } // 更新 f[i] }这个优化思路还可以延伸到“代价是区间内最大值/最小值平方”等变体。核心就是找到代价函数的一个上界用它来限制枚举范围本质上是以凸性换复杂度。4. 图论题的中期决策定义状态比跑模板更重要4.1 题目模型基环外向树上的最小覆盖C 题是一道图论题赛后复盘发现 AC 率低的原因集中在“状态定义模糊”上。题目给 n 个点每个点有一条出边形成一个基环外向树森林要求选最少的点使得每条出边 u→v 至少有一端被选中。这就是变形的“最小顶点覆盖”但图不是一般图而是每个点出度为 1。这种结构有一个天然入口先拓扑排序剥掉所有树枝剩下的环上的点一定没被处理。我们队一开始试图写一般图的最小顶点覆盖直接不可能因为那是 NP 问题差点在错误的路上走到黑。正确状态定义是树形 DP对每棵外向树设 dp[u][0/1] 表示 u 是否被选择时u 的子树的最小覆盖数。转移时如果 u 不选那么所有儿子 v 都必须选如果 u 选儿子可选可不选取 min。关键是环的处理。把环上的每个点当作一棵外向树的根先做一遍树形 DP然后只在环上做环形 DP。环形 DP 不能简单复制成链然后两边都取最优因为首尾会互相影响。我的做法是固定第一个点的选择状态跑两遍第一遍强制环首不选第二遍强制环首选取 min。4.2 “为什么不能直接套 SCC 缩点”的思考很多人第一眼看这个题会想到缩点成 DAG然后做 DAG 上的 DP。但注意原图每个点出度为 1缩点之后每个连通分量仍然是一个单环DAG 部分只有从环指向外部的边。如果先缩点反而会把环内部的 DP 状态搞乱——因为你缩完点之后环上每个节点代表一个强连通分量分量内部的覆盖关系需要额外处理比直接在原树上做更繁琐。我们在赛场上花了不少时间讨论这条路线最后否掉。我的体会是看到“每个点一条出边”这个条件第一反应就应该是基环树而不是 SCC。基环树题的核心套路就是“树形 DP 环上枚举首尾状态”这个模式今年在多个区域赛里都重复出现值得单独练熟。// 环上处理伪代码 for (int s 0; s 2; s) { dp[ring[0]][s] tree_solve(ring[0], s); for (int i 1; i ring.size(); i) { // 转移时考虑前一个节点选择状态 } ans min(ans, dp[ring.back()][s]); }4.3 赛中耗时点环的提取实现拓扑排序剥点的实现要注意顺序入度为 0 的点入队剥掉之后把它的出边目标点的入度减一。这里的“入度”是原图的方向但因为每个点只有一条出边倒着剥也能用。我们队写的时候先把所有边反向然后拓扑绕了一圈发现没必要直接正向拓扑也能提取环只是更新逻辑要小心。提取环之后环的顺序需要沿着出边走一遍才能确定否则环形 DP 里的“相邻”关系会错。这个点不复杂但实现时容易把树的 DFS 顺序和环的遍历顺序搞混建议在草稿上先画清楚。5. 数据结构的隐藏开销这道题 AC 率低的真正原因5.1 D 题的“伪线段树”考察点D 题表面是裸的线段树区间合并维护区间内最长连续 1 的个数支持区间翻转和区间赋值。这种题在套路库里是一眼题但沈阳这道题把 n 和 q 都开到了 2×10⁵并且操作里带区间翻转翻转不能只翻转懒标记——你得真的把左右儿子交换。这里的隐藏开销在于翻转操作需要递归到底才能交换整个子树吗不是的。线段树每个节点维护一个“翻转懒标记”执行区间翻转时更新当前节点的区间状态和懒标记不需要递归到底下次 pushdown 时才真正交换左右子树。但问题是如果题目同时支持“区间赋值”和“区间翻转”两个懒标记的优先级必须明确赋值标记在翻转之后应该被翻转翻转标记在赋值之后应该被清空。这个优先级如果反了样例很难测出来大数据随机测例容易卡住。我们队在这个优先级问题上 WA 了一次定位过程倒是很典型小数据对拍全过大数据随机测例 WA于是写了一个暴力程序对拍构造了“先区间赋值 [l,r] 为 1再区间翻转 [l,r]”的测例立刻复现。优先级应该是赋值标记晚于翻转标记生效时翻转标记清空翻转标记晚于赋值标记生效时赋值标记取反。这其实是一个“标记相互覆盖”的经典问题和扫描线里标记合并是同一类思想。5.2 内存和常数优化MLE 的排查链路D 题另外一个剿杀点的是内存。线段树每个节点如果开 4 个数组最长连续 1、左端连续 1、右端连续 1、懒标记每个都是 int4×4×4×2×10⁵ 差不多 12.8 MB看起来不超但如果再开一个数组存区间长度或者每个标记用 long long内存就上去了。沈阳这场的空间限制是 256 MB按理说够但如果你用递归写法且每个节点开了一个 vector 来存覆盖标记来支持区间反转那内存直接爆。我的建议是区间合并线段树的节点只存五个字段区间最长连续 1 个数、左端连续 1 个数、右端连续 1 个数、区间长度、懒标记赋值 0/1/翻转。区间长度可以在 pushup 时通过子区间长度相加得到不必单独存数组但需要递归传 l、r或者在节点里存。我实测在 2×10⁵ 的数据下用“节点存 l、r”的方式比传参方式慢 10% 左右但代码更好写。追求极限常数的话建议 pushup 时直接传 l、r让编译器优化递归参数。还有一个读写优化这道题 q 次操作全部是区间操作输入量不算大但输出量不小如果每个查询都用 endl 而不是 \n在 2×10⁵ 的规模下会有 0.2 秒左右的差距。区域赛的时限通常卡在 2 秒0.2 秒可能就是 TLE 和 AC 的区别。我们队在 E 题的哈希解法里也遇到了同样的输入输出陷阱见下一节。struct Node { int lmax, rmax, mx, len, lazy; // lazy: -1 无标记, 0 赋值为0, 1 赋值为1, 2 翻转 };5.3 区间翻转的懒标记实现细节这里单独展开翻转标记的实现因为它是这道题最容易写错的点。假设节点当前维护的区间是 [l,r]它有一个 lazy 标记初始为 -1。执行区间翻转时交换 lmax 和 rmaxmx 不变因为连续 1 个数在翻转后不变。如果当前 lazy 是 -1则 lazy 2。如果当前 lazy 是 0则 lazy 1。如果当前 lazy 是 1则 lazy 0。如果当前 lazy 是 2则 lazy -1翻转两次抵消。pushdown 时先处理赋值标记再处理翻转标记注意顺序不要反。具体来说如果节点的 lazy 是赋值类0 或 1那么把它传给子节点并清空当前节点 lazy如果 lazy 是翻转类2那么对两个子节点各执行一次翻转操作。这个“翻转操作”里又可能改变子节点的 lazy 状态所以要写成一个独立的 apply_flip 函数而不是在 pushdown 里内联判断。我在赛场上就是把 apply_flip 的逻辑内联到 update 里导致一个地方改了另外的地方忘记改debug 了很久。边界条件方面区间长度是 1 的节点翻转后 lmax 和 rmax 不变但如果你写的是通用交换逻辑其实也能过只是理论上有一次多余赋值。实际测试中这种单节点翻转的额外开销可以忽略不计不必为它单独写分支。6. 复杂度估算中的陷阱哈希题 AC 率为何偏低6.1 E 题的思路骨架E 题表面是字符串匹配给一个文本串 S 和一个模式串 P允许 P 中有一个字符和 S 中对应位置不同问 P 在 S 中能匹配多少次。看到“允许一个字符不同”的条件第一反应就是用哈希 二分找第一个失配位置。具体做法是先预处理 S 和 P 的前缀哈希对于每个对齐位置二分找到第一个哈希值不同的位置然后跳过这个位置再检查剩余部分哈希是否相同。这个思路本身很常规但 AC 率低的原因在于总字符数 n 和模式长度 m 的范围分别到了 2×10⁵ 和 5×10⁵意味着你可能要对每个对齐位置做一次二分。二分的 log 级别是 log n如果每次二分要比较两个子串的哈希比较的复杂度是 O(1)所以总复杂度是 O(n log n)按理说没问题。但这里有一个细节模式串 P 的长度可能比 S 长此时不能直接错位匹配。我们队第一版实现没处理这个情况RE 了一发。正确的做法是先把 S 和 P 都补成同一长度但不改变原始语义或者直接遍历所有可能的对齐起点判断start m n是否成立。6.2 为什么我用双哈希而不是单哈希哈希题里总有争论单哈希到底够不够我的观点是区域赛的数据范围下单哈希被卡的概率很低但没必要冒这个险双哈希的额外开销也就是两次取模常数可以接受。E 题尤其适合双哈希因为二分比较时如果单哈希冲突会导致二分提前结束最终答案是错的而且非常难定位。双哈希我用的两个模数是 998244353 和 1000000007底数选 13331 或 131。注意底数不要选偶数也不要选和模数有公因子的数。预处理哈希的幂次数组时从 0 到 max(n, m) 都要算好少了边界会导致访问越界。struct DoubleHash { vectorlong long h1, h2, p1, p2; // 构造前缀哈希 long long get1(int l, int r) { return (h1[r] - h1[l-1] * p1[r-l1] % MOD1 MOD1) % MOD1; } long long get2(int l, int r) { return (h2[r] - h2[l-1] * p2[r-l1] % MOD2 MOD2) % MOD2; } };二分定位失配位置的时候左边界是当前对齐起始位置右边界是起始位置 m - 1。mid 的判定是“S[start, mid] 与 P[0, mid-start] 的哈希是否相同”如果相同说明失配位置在 mid 之后否则在 mid 及之前。这个过程要跑两次第一次找第一个失配第二次在失配位置之后检查剩余部分是否完全匹配。如果剩余部分也完全匹配那么这一位对齐就是合法的。6.3 快读快写在这里是刚需不是锦上添花E 题 n、m 都是 5×10⁵输入输出量加起来接近百万级。如果你用 cin 且没有关同步大概率会 TLE哪怕算法复杂度完全正确。这个现象很多队伍赛后才意识到因为样例数据量小根本测不出来。我的经验是cin.tie(nullptr) 和 ios::sync_with_stdio(false) 是标配但还不够——输入里可能混有空格用 cin 读取字符串没问题但是如果你用 scanf 读字符串遇到 \n 的处理要小心。输出方面每个匹配位置输出一个结果建议统一存到一个 string 里最后一次性 print或者用 \n 而不是 endl。我实测把 endl 改成 \n 后E 题的运行时间从 2.3 秒降到 1.6 秒差距非常明显。另外哈希数组建议开到 n m 5而不是 n 5。因为比较 S 和 P 时你会对 P 的子串取哈希下标可能到 m如果只开了 n 的长度就会越界。这个 bug 在本地测试时不一定爆但在评测机上是 RE 甚至 WA排查起来很头疼。7. 赛后复盘时间分配与读题顺序的得失最后写一点赛场整体层面的复盘这比单独某道题的解法学到的东西更多。7.1 我们队的时间线回顾0:00 - 0:15开局读题C 题被误判为签到浪费了 10 分钟。0:15 - 0:45A 题 AC中间 WA 了一次原因是区间端点离散化没处理好。0:45 - 1:20B 题 ACDP 优化顺利但 last 数组初始化浪费了 3 发。1:20 - 2:30D 题实现区间翻转标记优先级搞混对拍才定位。2:30 - 3:10E 题双哈希 二分过。3:10 - 4:20C 题环形 DP赛后发现状态定义其实不难当时有点绕远。这个时间线的最大问题在于 C 题放得太晚。C 题的树形 DP 部分并不难难在环 DP 的状态定义如果我们早点把它读透完全可以在 D 题之前做掉。事后看读题顺序应该是先扫完全部题面把题分成“一眼签到”“需要想”“需要写很久”三档先把需要想的题留出头脑清醒的时间段。7.2 卡题时的止损策略我们队在 D 题上卡了比较久已经影响到 E 题的时间。这次的经验是如果一道题超过 40 分钟没有新进展就该安排一个人去读下一道题另一个人继续想。两个人同时卡同一道题是最亏的。区域赛四个小时不存在“一鼓作气”的选项产能分配比单题突破重要得多。对拍也是这次做得比较好的点。D 题我们写了三个版本第一版裸线段树带赋值不带翻转第二版加了翻转但优先级错误第三版修正了优先级。前两版都能过小样例但和暴力程序对拍时第二版在“先赋值后翻转”的用例下立刻暴露。我强烈建议每个队伍都准备一个通用的对拍模板比赛时直接复用不用现场重写。7.3 对下一阶段训练的建议沈阳这场赛后我给自己列了几个训练方向基环树题单独拉一个题单把“树形 DP 环上枚举状态”这个模式练熟。线段树懒标记优先级问题找几个经典题区间赋值翻转、区间加赋值翻转反复写直到不用思考。哈希题统一采用双哈希模板把二分定位失配的套路写进代码库。时间分配上强化“扫题 - 分档 - 定时检查”的训练避免在单题上死磕。区域赛的题解写出来最有价值的部分不是最后的 AC 代码而是中间那些错误的岔路。希望这篇复盘能让你少走几条我当时走过的弯路。