企业官网建设流程全解析

看到“ABC 杂题选讲3”这个标题，常刷 AtCoder 的朋友应该已经反应过来了：这里说的是 AtCoder Beginner Contest，不是 Mac 上那个删不掉的 ABC 输入法。这期我把近期几场 ABC 里值得反复咀嚼的题挑了三道出来，不是按比赛顺序，而是按套路分类，正好对应模拟、贪心、树形 DP 三类最常考的东西。适合刚打完比赛、想把盲区补上的朋友，也适合那些能稳定 AC 前四题、但遇到 E 题 F 题就卡住的选手。这三道题分别是七段数码管模拟、区间调度贪心，以及树上的最大权独立集。本文会完整走一遍从读题、建模、暴力到正解的思考过程，给出可以直接提交的代码，最后再集中说说比赛里最常见的几类翻车问题。

1. 内容整体设计与思路拆解

1.1 为什么第三期选这三道题

ABC 的题目分布其实很有规律，A/B 题考基本功，C/D 题开始上思维，E/F 题在算法基础上还要看熟练度。杂题选讲的选题原则，不是把每道题都讲一遍，而是挑那些“模型可复用、换张皮还能考”的题。这次选的七段数码管模拟，就是一个典型的读题坑题：题目本身代码量很小，但对题面条件的理解要求极高，很多人一上来就按“完全匹配”去判断，结果漏掉一半答案。区间调度则是贪心里面最容易出反例的一类，它考的不是代码而是证明，能写出一段 sort 加 for 循环的人很多，但能说清楚为什么这么取最优的人并不多。第三题树上的最大权独立集，是一道标准的树形 DP，暴力枚举子集是指数级的，显然过不了，必须把树结构拆成子问题自底向上合并。这类题是很多选手从“手速场”过渡到“思维场”的分水岭，值得单独拎出来讲。

1.2 难度梯度和读题策略

三道题在难度上正好可以连成一条进阶线。第一题只需要耐心，细心读题就能做；第二题需要你能证明贪心策略，不然换个条件就容易被卡；第三题需要一定的 DP 状态设计经验，属于 ABC 中 E 题左右的难度。对还没到那个阶段的朋友，我建议按顺序看，不要直接跳到树形 DP，因为贪心的证明思路和 DP 的状态设计是一脉相承的，都是“先找到一个局部最优结构，再考虑怎么递归合并”。

这里顺便说一下 ABC 的读题顺序。它的题面有时候很长，但信息密度不一定高，尤其是模拟题，大段英文或日文描述翻来覆去就讲一个规则。我自己习惯先看样例，再回去读题面，这样更容易抓住输入输出格式和边界条件。而树形 DP 的题面通常很短，反而需要自己补全很多隐含条件，比如树是否无向、权值有没有可能是负数、允不允许选空集。这些在动手写代码之前都要确认，不然写完才发现方向错了。

1.3 杂题选讲与完整比赛复盘的区别

完整比赛复盘一般按 A 到 F 讲，这样能还原赛场上的时间线，但容易让人陷入“这题我见过差不多”的错觉。杂题选讲不一样，它把不同场次里具有共性的题挑出来集中训练，好处是能快速建立“模型识别”能力。以后你看到区间问题，会下意识想贪心还是 DP；看到树上选点，会下意识想独立集相关状态。所以这一期我不做题号罗列，而是按“模拟、贪心、树 DP”三个专题展开，每个专题都用一道完整题目做例子。希望读者看完之后不是只会做这三道题，而是能把分析方法带走，遇到新题时能套用。

2. 核心细节解析与实操要点

2.1 七段码模拟：把现实规则变成查表

七段码大家应该都有印象，电子表、电梯楼层显示器都是它。七段分别用字母 a 到 g 表示，a 在上面横，b 在右上竖，c 在右下竖，d 在下面横，e 在左下竖，f 在左上竖，g 在中间横。数字 0 到 9 各自由其中若干段点亮组成，比如数字 1 只点亮 b 和 c，数字 8 点亮全部七段。

这种题如果你用一堆 if-else 去写，也不是不行，但代码会非常啰嗦，而且很容易写错。正确的做法是先把 0 到 9 的亮灭状态预处理成一张表，让程序去查表，而不是让程序去判断“哪根线连着哪个数字”。表结构可以用字符串，也可以用二进制掩码。对初学者来说，字符串数组最直观，每一位对应一个段，从左到右固定为 a、b、c、d、e、f、g 的顺序。

下面是我常用的表：

注意这里每一位的顺序必须固定，不然后面比较的时候会出大问题。实际比赛题面可能会换一种顺序，比如按 abcdef 还是按 fbgcde 之类，这时候你只需要把表里的字符串和题目给的顺序对齐就行。七段码的模拟题难不在代码，而在“把现实规则转换成程序能查的表”这个能力，这种能力在任何需要维护映射关系、状态表的场景里都能迁移。

2.2 贪心题怎么证明“按结束时间排序”

区间调度是贪心算法里的经典题：给定 N 个区间，每个区间代表一个工作的开始时间和结束时间，一个人同一时刻只能做一个工作，问最多能完成多少个工作。

很多人的第一反应是按开始时间排序，或者按区间长度排序，但这两种都会出问题。按开始时间排序，你可能先选了一个特别长的区间，把后面所有短区间都挡住了；按长度排序，你可能选了一个时间位置很差的长区间，导致左右两边都接不上。正确的贪心策略是按右端点升序排序，每次选当前能选的、且结束时间最早的区间。为什么这样最优？可以用替换法证明：假设最优解的第一个区间是 [L, R]，而所有区间里右端点最早的是 [l, r]。因为 r 是全局最小的右端点，所以 r <= R。用 [l, r] 替换 [L, R]，后续区间能使用的剩余时间只会变多不会变少，因此不会破坏最优性。这样一步一步替换下去，贪心策略总能构造出最优解。

这个证明思路特别重要，因为很多贪心题不是靠直觉蒙对的，而是靠这种“局部替换不劣”的论证。比赛里你可能没时间写完整证明，但至少要能用反例快速验证自己的排序策略是否可靠。

2.3 树上 DP 的状态设计：选 / 不选

树形 DP 是 ABC 里 E 题的常客，核心思路是把一棵树从根往叶子拆成子问题，再用 DFS 回传结果。最经典的一类就是“最大权独立集”：给定一棵树，每个点有权值，选择一些点，使得任何一条边的两个端点不能同时被选，求最大点权和。

如果直接枚举所有子集，复杂度是 2^N，N 稍微大一点就爆炸。但树有一个非常好的性质：对于某个节点，它的决策只会影响它的父亲和孩子，不会影响更远的节点。所以我们只要站在一个节点的角度，考虑“我选”和“我不选”两种情况就行。定义 dp[u][0] 表示以 u 为根的子树上，不选 u 时能获得的最大值；dp[u][1] 表示选 u 时能获得的最大值。

转移分两类。如果 u 选了，那么它的所有直接子节点都不能选，所以 dp[u][1] 等于 u 的权值加上所有子节点的 dp[v][0] 之和。如果 u 不选，那每个子节点可以自由选择选或是不选，所以 dp[u][0] 等于所有子节点的 max(dp[v][0], dp[v][1]) 之和。最后在根节点取 max(dp[root][0], dp[root][1]) 就是答案。

这个状态设计思路可以迁移到很多树上问题，比如“树上染色”、“树上覆盖”等，核心都是把“某个点的状态会影响邻居”这个关系转化成状态之间的依赖。

3. 实操过程与核心环节实现

3.1 第一题：七段码分 ABC

题目描述可以这样理解：有一段坏了的七段数码管，你观察到某个数字显示出来的亮灭状态，这个状态可能对应 0 到 9 中的多个数字，因为某些段可能坏了，导致它本该亮而不亮。给你长度为 7 的 01 串，1 表示看到该段亮，0 表示看到该段灭，问有多少个数字能产生这个观察结果。

这道题的关键逻辑是“坏段只会让亮的变成灭，不会让灭的变成亮”。所以当你看到某一段是 1 时，这个数字对应的该段必须本来就是亮的；当你看到某一段是 0 时，不能排除这个数字原本该亮，只是恰好这段坏了。换句话说，判断数字 d 是否可能，只需要对每一位比较：如果输入的 s[i] 是 1，但 seg[d][i] 是 0，那么这个数字不可能；如果 s[i] 是 0，不管 seg[d][i] 是 0 还是 1，都可能是。

举一个极端例子：输入全 0，也就是全部七段都灭。按全灭来想，好像一个数字都不应该，但实际上所有数字都可能，因为所有段都可能坏掉了。这个样例如果能跑出来答案是 10，说明你的判断逻辑才是对的。

完整代码：

#include <bits/stdc++.h> using namespace std; string seg[10] = { "1111110", // 0 "0110000", // 1 "1101101", // 2 "1111001", // 3 "0110011", // 4 "1011011", // 5 "1011111", // 6 "1110000", // 7 "1111111", // 8 "1111011" // 9 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; vector<int> ans; for (int d = 0; d < 10; d++) { bool ok = true; for (int i = 0; i < 7; i++) { if (s[i] == '1' && seg[d][i] == '0') { ok = false; break; } } if (ok) ans.push_back(d); } cout << ans.size() << '\n'; if (!ans.empty()) cout << ans.front() << '\n'; return 0; }

代码本身很短，但里面藏着一个最容易被忽略的思维惯性：很多人看到“匹配”就以为是 s[i] 必须和 seg[d][i] 完全相等，于是输入 1111111 时只输出 8，看起来对；但输入 0110000 时就会漏掉 7，因为 7 的 a 段本应亮，但可能坏了，所以观察到 0110000 完全有可能。这类题考的不是你会不会写循环，而是你会不会把题面里的“损坏”转换成正确的约束条件。

3.2 第二题：排序贪心的完整推导

题目描述：有 N 个工作，第 i 个工作需要占用从 L_i 到 R_i 的连续时间，同一时刻只能做一个工作，问最多能完成多少个工作。

给一个具体的例子。假设有五个工作：

(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)

按直觉，先做 (1,3)，然后可以做 (4,7)，再做 (8,10)，一共三个。这个解确实是最优的。但如果你按开始时间排序，先选 (1,3)，第二个选 (2,5)，后面就全被挡掉了，只能做两个，所以按开始时间排序是错的。

正确的做法是先把所有区间按右端点从小到大排序。右端点相同的话，按左端点从小到大排序，但这不是必须的，主要是为了保持一个稳定顺序。然后维护一个变量 last，表示当前已选区间中最后一个区间的结束时间。遍历排序后的区间，如果当前区间的开始时间不小于 last，说明可以和前面的不相交，于是选择它，并把 last 更新为当前区间的结束时间；否则跳过。

完整代码：

#include <bits/stdc++.h> using namespace std; struct Node { int l, r; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<Node> a(N); for (int i = 0; i < N; i++) { cin >> a[i].l >> a[i].r; } sort(a.begin(), a.end(), [](const Node& x, const Node& y) { if (x.r != y.r) return x.r < y.r; return x.l < y.l; }); int ans = 0; int last = -1e9; for (const auto& x : a) { if (x.l >= last) { ans++; last = x.r; } } cout << ans << '\n'; return 0; }

这里有一个很容易踩的坑：x.l >= last表示两个区间端点重合时，可以看作不冲突。但有些题目里，端点重合也算冲突，比如“时间点不能重复占用”，这时候判断条件就要改成x.l > last。我见过很多选手就是因为没看清楚题面里的这句话，导致 WA，所以强烈建议在代码里注释标注一下当前判断用的是>=还是>。

还有一个常见的扩展问题：如果每个工作有收益，问最大收益而不是最大数量，那上面这个贪心就不对了。因为贪心只能保证选最多的区间，不能保证收益总和最大。这时候需要按右端点排序后做 DP，再配合二分查找“前一个不冲突的区间”，复杂度是 O(N log N)。贪心题最怕的就是换个问题条件还在套旧思路，所以每做一道题都要想清楚它依赖的“无后效性”到底成不成立。

3.3 第三题：树上最大权独立集

题目描述：一棵树有 N 个节点，每个节点有一个权值 w_i，你需要选一些节点，要求一条边上的两个端点不能同时被选，问能选出来的最大权值和是多少。

树长得很像一个倒挂的家谱，每个节点只需要考虑自己节点内部的子树。这里我们任意选择 1 号节点作为根，开始 DFS。DFS 的过程中要传入当前节点的父节点，防止走回已经访问过的节点，否则会在树上死循环或者重复计算。

从叶子往根看，一个叶子的 dp[leaf][0] = 0，表示不选它；dp[leaf][1] = w[leaf]，表示选它。对非叶子节点 u，先用子节点的结果把 dp[u][0] 和 dp[u][1] 累加起来。选 u 时，所有子节点都不能选，所以加上 dp[v][0]；不选 u 时，子节点选不选都行，所以加上 max(dp[v][0], dp[v][1])。

完整代码：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<long long> w(N + 1); for (int i = 1; i <= N; i++) { cin >> w[i]; } vector<vector<int>> g(N + 1); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<array<long long, 2>> dp(N + 1); function<void(int, int)> dfs = [&](int u, int fa) { dp[u][0] = 0; dp[u][1] = w[u]; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } }; dfs(1, 0); cout << max(dp[1][0], dp[1][1]) << '\n'; return 0; }

这里强调一点：dp 数组一定要开成 long long。ABC 的题目里 N 可以到 2e5，每个点权值到 1e9，总和能到 2e14，int 完全装不下。很多选手树形 DP 写得没问题，就是最后被这个溢出坑了，比赛里白白交一发 WA。

第二个要提醒的是建树的时候一定要双向加边。树本身是无向图，你只加一条边的话，从根往叶子遍历时可能漏掉以邻接表形式访问不到的部分，最终甚至会导致一个孤立点没有被访问。这个错误很隐蔽，因为小数据有时候恰好能跑对，到大规模数据就会出问题。

第三个要提醒的是递归深度。树如果退化成一条链，递归深度可能达到 2e5，有些环境下默认栈会爆。AtCoder 的评测环境通常还好，但如果你在自己电脑上测试，建议先加编译选项或者改成栈。实际上 C++ 的function + lambda在极端深度下比普通递归函数更容易爆栈，因为 lambda 对象有额外开销。如果有顾虑，可以改成普通成员函数，或者写一个非递归的 DFS 手动维护栈，不过这在 ABC 里不是常态，知道这个风险就行。

4. 常见问题与排查技巧实录

4.1 模拟题把“亮灭匹配”搞反

七段码那道题有一个非常值得记住的测试样例：输入0000000时，正确答案应该是 10，而不是 0。因为七段全灭，可能是所有段都坏了，所以 0 到 9 全部都有可能。遇到这种题，先在心里过一遍这个样例，如果代码输出 0，那说明你把约束条件写反了。

同样思路可以推广到很多“设备损坏”类的模拟题：观察到的 0 不一定是真的 0，可能是因为坏了；观察到的 1 一定是真的 1。这类题在 ABC 里反复出现，核心就是“故障只会造成假阴性，不会造成假阳性”。如果你在做别的题时也遇到“部分信息缺失”的状态判断，想想这个道理，很多坑都能提前避开。

4.2 区间调度里的端点判断

区间调度最常 WA 的地方不是排序，而是端点比较。题目里如果明确说“结束之后可以立刻开始下一个工作”，那就是x.l >= last；如果题目说“同一时间点只能属于一个工作”，那就是x.l > last。这两种情况在 ABC 里都出现过，而且题目描述通常只有一字之差。

我自己的习惯是在读题时把这句话画出来，再在代码里用注释标记，比如：

// 这里允许端点重合，所以用 >= if (x.l >= last)

如果写完以后还不确定，就造一个边界数据测试，比如两个区间(1, 2)和(2, 3)，看输出是 1 还是 2，就能快速验证自己理解的题意。

4.3 树形 DP 的递归坑与数据范围

树形 DP 的报错通常集中在几个地方。

第一，递归死循环。很多新手刚写完 DFS 会忘记传 fa，或者判断v == fa写成了v != fa，导致在树上反复横跳直接爆栈。第二，只遍历子节点却用了全局数组来防止重复访问。如果这棵树不是以 1 为根的有向图，很容易重复加子节点，导致 dp 值偏大。第三，数据范围。前面已经说了，dp 要用 long long。第四，输入编号从 0 开始还是从 1 开始，这个问题看着小，但最容易在初始化数组时越界。

排查的时候不要只看代码，先检查样例。如果样例过了，再自己构造一个特别小的树，比如三个节点一条链，手工算一下期望答案，用笔算完再跟程序输出对比。这比盯着屏幕找 bug 高效得多。

4.4 调试三件套：小样例、暴力对拍、打印中间量

我打 ABC 有一个习惯：只要写完题，就先测题面样例，再测自己构造的极端小样例，最后如果还有时间就写一个暴力程序去对拍。对拍不需要多复杂，写一个答案正确的暴力版本，数据范围开到 N <= 10，随机生成几百组数据，跑一遍看结果是否一致。如果暴力过不了样例，那说明题目理解错了；如果暴力能过但正解不过，那问题大概率出在优化逻辑上。

打印中间量也很实用。树形 DP 里，你可以临时在 DFS 里加一句cerr << u << " " << dp[u][0] << " " << dp[u][1] << endl;，看每个节点的状态是不是符合预期。提交前记得删掉，不然会输出一堆额外内容导致 WA。

4.5 现场比赛怎样用这套思路

ABC 的时间压力下，不要一上来就写代码。读完题优先归类：这是模拟、贪心、DP、图论还是数学？如果是模拟，先把状态表建好；如果是贪心，先找一个反例验证自己的策略；如果是树上问题，先想状态定义。三道题正好对应了三个分类，做题时也这样去分类，至少能把 90% 的问题放到熟悉框架里解决。

最后再分享一个我自己的习惯。每次比赛结束，我不急着去对别人题解，而是把当时没 AC 的题按“错误类型”登记一下，比如“七段码那题是 0/1 判断反了”“树形 DP 是忘了 long long”。这个系列选讲就是在这种登记表上攒出来的。下一期你们想听哪一类题目，可以留言，我优先安排。