企业官网建设流程全解析

一场区域赛结束，真正能被记住的往往不是榜单上的排名，而是那些赛场上卡了两个小时、下来之后一拍大腿的题。这篇接上一篇，继续写 2025 年 ICPC 沈阳区域赛的题解梳理，主要挑我在赛后复盘里觉得最有价值的几道题展开：有快速拿分的贪心，有需要优化才能过的 DP，也有几道题 AC 率不高的原因根本不在算法本身，而在读写开销和状态设计的细节上。

如果你是准备区域赛的选手，这篇的定位是“赛后复盘笔记”，不是官方题解合集。题号顺序我按赛场难度和讲解价值重新排过，每组都会先说思路，再补实现细节和卡点，最后给一段我自己的教训总结。代码以 C++17 为主，部分题目我给了复杂度推导。

1. 先说选题：这场的题单我挑哪些出来写

沈阳这场整体给我的感觉是：签到题和简单题非常友好，中档题的分层做得比较明显，难题的思维量集中但代码量不算爆炸。这种题单结构其实很适合训练队伍的比赛策略——前两个小时能不能把简单题全部稳住，直接决定你在中档题上的心态和剩余时间。

我选了五道题作为这期博客的主体：

这几道题里，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(j+1, i))，其中 j 从 0 到 i-1。

这个转移一看就是 O(n²) 的，n 到 10⁵ 直接爆炸。但这里有个关键观察：平方项增长很快，段内不同元素数量超过某个阈值时，不如直接每个元素单独成段——单元素段的代价恒为 1，所以总代价上界是 n。

于是可以设阈值 K，只枚举那些段内不同元素数量 ≤ K 的转移。这个 trick 在很多“平方代价分段 DP”里都能用，核心原因在于平方函数的凸性：超过一定长度后分段一定更优。

3.2 阈值 K 的选取与复杂度推导

K 取多少合适？如果某一段的不同元素数量超过 K，它的代价至少是 (K+1)²，而如果把它拆成若干个单元素段，总代价不超过 K+1。所以只要 (K+1)² > K+1，即 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、懒标记，每个都是 int，4×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 和 rmax，mx 不变（因为连续 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 { vector<long long> h1, h2, p1, p2; // 构造前缀哈希 long long get1(int l, int r) { return (h1[r] - h1[l-1] * p1[r-l+1] % MOD1 + MOD1) % MOD1; } long long get2(int l, int r) { return (h2[r] - h2[l-1] * p2[r-l+1] % 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:45：A 题 AC，中间 WA 了一次，原因是区间端点离散化没处理好。
• 0:45 - 1:20：B 题 AC，DP 优化顺利，但 last 数组初始化浪费了 3 发。
• 1:20 - 2:30：D 题实现，区间翻转标记优先级搞混，对拍才定位。
• 2:30 - 3:10：E 题双哈希 + 二分，过。
• 3:10 - 4:20：C 题环形 DP，赛后发现状态定义其实不难，当时有点绕远。

这个时间线的最大问题在于 C 题放得太晚。C 题的树形 DP 部分并不难，难在环 DP 的状态定义，如果我们早点把它读透，完全可以在 D 题之前做掉。事后看，读题顺序应该是：先扫完全部题面，把题分成“一眼签到”“需要想”“需要写很久”三档，先把需要想的题留出头脑清醒的时间段。

7.2 卡题时的止损策略

我们队在 D 题上卡了比较久，已经影响到 E 题的时间。这次的经验是：如果一道题超过 40 分钟没有新进展，就该安排一个人去读下一道题，另一个人继续想。两个人同时卡同一道题是最亏的。区域赛四个小时，不存在“一鼓作气”的选项，产能分配比单题突破重要得多。

对拍也是这次做得比较好的点。D 题我们写了三个版本：第一版裸线段树带赋值不带翻转，第二版加了翻转但优先级错误，第三版修正了优先级。前两版都能过小样例，但和暴力程序对拍时，第二版在“先赋值后翻转”的用例下立刻暴露。我强烈建议每个队伍都准备一个通用的对拍模板，比赛时直接复用，不用现场重写。

7.3 对下一阶段训练的建议

沈阳这场赛后，我给自己列了几个训练方向：

• 基环树题单独拉一个题单，把“树形 DP + 环上枚举状态”这个模式练熟。
• 线段树懒标记优先级问题，找几个经典题（区间赋值+翻转、区间加+赋值+翻转）反复写，直到不用思考。
• 哈希题统一采用双哈希模板，把二分定位失配的套路写进代码库。
• 时间分配上，强化“扫题 - 分档 - 定时检查”的训练，避免在单题上死磕。

区域赛的题解写出来，最有价值的部分不是最后的 AC 代码，而是中间那些错误的岔路。希望这篇复盘能让你少走几条我当时走过的弯路。