第17章 模拟赛与复盘¶
本章收录两场完整模拟赛的解题记录、一个图论专项训练，以及赛后复盘补缺的分类练习。 每场模拟赛包含五道题目，覆盖贪心、图论、动态规划、二分图等核心算法专题。 赛后复盘部分按知识点分类梳理补充练习，帮助查漏补缺、巩固薄弱环节。
本章结构如下：
| 小节 | 内容 | 对应训练计划 |
|---|---|---|
| 17.1 | 模拟赛1（五题完整题解） | ACM Day3 |
| 17.2 | 图论专项训练（练习题单） | ACM Day6-7 |
| 17.3 | 模拟赛2（五题完整题解） | ACM Day8 |
| 17.4 | 复盘与补缺（23 道分类练习） | ACM Day13 |
17.1 模拟赛1（ACM Day3）¶
模拟赛1共五道题，涵盖贪心模拟、图论环检测、拓扑排序、二分图染色和树形DP， 难度从Medium到Hard递进。建议比赛时长4小时，按照题目难度由易到难依次攻克。
| 题号 | 来源 | 难度 | 算法标签 |
|---|---|---|---|
| T1 | CF 1919C | Medium | 贪心、排序、模拟 |
| T2 | CF 977E | Medium | 图论、环检测、DFS |
| T3 | CF 510C | Medium | 拓扑排序、建图 |
| T4 | CF 1144F | Medium | 二分图、染色、构造定向 |
| T5 | AT dp_v | Hard | 树形DP、换根DP |
T1 - CF 1919C (Medium) 贪心模拟¶
题号说明
本题对应训练计划中的 CF 1919C - Grouping Increases（难度 1400）。 注意：CF 原题题面是"把序列划分成两个子序列，最小化两个子序列中相邻上升对的总数"，正解为贪心维护两个子序列的结尾值； 下面正文按训练时使用的简化改编题面讲解，刷原题时请以链接中的题面为准。
题意分析¶
题目描述
给定一个长度为 \(n\) 的正整数数组 \(nums\)，以及一个正整数 \(k\)。你可以执行以下操作任意次：
- 选择数组中的一个元素，将其减少 \(1\)。
你的目标是使数组中 恰好 有 \(k\) 个元素相等。求在满足条件的前提下，这 \(k\) 个相等元素的 最大值 是多少。
数据范围：\(1 \le k \le n \le 2 \times 10^5\)，\(1 \le nums[i] \le 10^9\)。
输入格式：
第一行两个整数 \(n, k\)；第二行 \(n\) 个整数表示数组 \(nums\)。
输出格式：
输出一个整数，表示 \(k\) 个相等元素的最大值。
样例：
关键观察
由于每次操作只能 减少 元素的值，所以 \(k\) 个相等元素的值一定 不超过 原数组中的最大值。 我们希望这 \(k\) 个元素的值尽可能大，因此应该优先选择数组中较大的元素，将它们减少到某个相同的值。
思路推导¶
第一步：排序
将数组从大到小排序。排序后，前 \(k\) 个元素就是数组中最大的 \(k\) 个值。
第二步：贪心分析
我们希望找到一个目标值 \(target\)，使得数组中至少有 \(k\) 个元素可以通过减少操作变成 \(target\)。
显然，\(target\) 越大越好。由于操作只能减少，\(target\) 不能超过排序后第 \(k\) 大的元素（即 nums[k-1]，0-indexed）。
第三步：确定答案
- 如果我们将目标值设为
nums[k-1]（排序后第 \(k\) 大的数），那么前 \(k\) 个元素都可以通过减少操作变为这个值。 - 我们不需要检查更小的目标值，因为我们的目标是 最大化 这 \(k\) 个相等元素的值。
- 因此答案就是排序后第 \(k\) 大的元素。
第四步：验证
以样例为例：排序后 \(nums = [5, 4, 3, 2, 1]\)，取 \(k = 3\)，第 \(3\) 大的元素为 \(3\)。 - \(5 \to 3\)（减 2 次） - \(4 \to 3\)（减 1 次） - \(3 \to 3\)（不需要操作）
恰好 \(k = 3\) 个元素等于 \(3\)，总操作次数为 \(3\) 次。如果目标值设为 \(4\)，则只有 \(2\) 个元素 \(\ge 4\)，不满足 \(k = 3\) 的要求。
易错点
- 注意排序方向，是从大到小排序（降序）。
- 数组下标从 \(0\) 开始，第 \(k\) 大的元素对应下标
k-1。 - 不要混淆"第 \(k\) 大"和"第 \(k\) 小"的概念。
完整C++代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// 从大到小排序
sort(nums.begin(), nums.end(), greater<int>());
// 第k大的元素就是答案
// 因为前k个最大的元素都可以减少到nums[k-1]
cout << nums[k - 1] << "\n";
return 0;
}
代码说明
greater<int>()实现降序排序，使得nums[0]为最大元素。- 排序后
nums[k-1]即为第 \(k\) 大的元素，前 \(k\) 个元素都 \(\ge nums[k-1]\)，都可以通过减少操作变为该值。 - 本题的时间瓶颈在于排序，整体时间复杂度为 \(O(n \log n)\)。
复杂度分析¶
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | \(O(n \log n)\) | 排序的复杂度，读入和输出均为 \(O(n)\) |
| 空间复杂度 | \(O(n)\) | 存储数组的额外空间 |
拓展思考
如果题目改为"每次操作可以增加或减少 1"，答案会发生什么变化？此时答案将是 \(\lfloor sum / k \rfloor\) 的某种形式， 因为我们可以把多余的值"转移"到不足的元素上。这类问题通常需要更多的贪心分析，值得深入思考。
T2 - CF 977E (Medium) 图论-环检测¶
题意分析¶
题目描述
给定一个 \(n\) 个顶点 \(m\) 条边的 无向图。定义"好"连通分量为：该连通分量中的 每个顶点的度数恰好为 2。 换言之，好连通分量恰好构成一个简单环。求图中"好"连通分量的个数。
数据范围：\(1 \le n \le 2 \times 10^5\)，\(0 \le m \le 2 \times 10^5\)。
输入格式：
第一行两个整数 \(n, m\)；接下来 \(m\) 行，每行两个整数 \(u, v\) 表示一条边。
输出格式：
输出一个整数，表示"好"连通分量的个数。
样例：
核心观察
在无向图中，一个连通分量是简单环的充要条件是：分量中每个顶点的度数都为 2。 这是因为：如果每个点的度数都为 2，则边数 = 点数，且连通，因此必然是一个简单环。
思路推导¶
第一步：统计度数
遍历所有边，统计每个顶点的度数。对于无向图中的一条边 \((u, v)\)，\(u\) 和 \(v\) 的度数各加 1。
第二步：DFS/BFS 找连通分量
用 DFS 或 BFS 遍历整个图，找出所有连通分量。在遍历每个连通分量时，检查其中所有顶点的度数。
第三步：判断条件
对于每个连通分量，遍历其中的所有顶点：
- 如果分量中 每个顶点的度数都为 2，则该分量是一个"好"连通分量（简单环），计数加 1。
- 如果有 任何一个顶点的度数不为 2，则该分量不是简单环。
第四步：实现细节
使用 visited 数组标记已访问的顶点。对于每个未访问的顶点，启动一次 DFS，收集连通分量中的所有顶点，
然后逐一检查度数。
易错点
- 注意是 无向图，建图时边要双向添加。
- 孤立的顶点（度数为 0）不构成环，不要误判。
- 两个顶点之间的多条边会导致度数 \(> 2\)，需要正确处理（本题输入保证无重边，但实际解题时需注意）。
- 使用邻接表存图，避免使用邻接矩阵（空间复杂度不够）。
完整C++代码¶
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector<int> adj[MAXN]; // 邻接表存图
int degree[MAXN]; // 记录每个顶点的度数
bool visited[MAXN]; // DFS访问标记数组
vector<int> component; // 临时存储当前连通分量中的顶点
// DFS遍历连通分量，收集所有属于该分量的顶点
void dfs(int u) {
visited[u] = true;
component.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// 建图，同时统计度数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
degree[u]++;
degree[v]++;
}
int ans = 0;
// 遍历所有顶点，找连通分量
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
// 新的连通分量，用DFS收集所有顶点
component.clear();
dfs(i);
// 检查该连通分量中每个顶点的度数是否都为2
bool isGood = true;
for (int u : component) {
if (degree[u] != 2) {
isGood = false;
break;
}
}
// 如果所有顶点度数都是2，则是"好"连通分量
if (isGood) {
ans++;
}
}
}
cout << ans << "\n";
return 0;
}
代码说明
- 使用
adj邻接表存储无向图，每条边添加两次。 dfs函数遍历连通分量，将所有可达顶点存入component向量。- 遍历完一个连通分量后，检查其中所有顶点的度数是否都为 2。
- 由于图可能不连通，需要对每个未访问的顶点启动新的 DFS。
BFS 替代方案
如果担心递归深度过大导致栈溢出（\(n\) 很大时），可以将 DFS 改为 BFS 实现。BFS 使用队列，不会受到系统栈深度限制：
复杂度分析¶
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | \(O(n + m)\) | 建图 \(O(m)\)，DFS 遍历所有顶点和边共 \(O(n + m)\)，度数检查 \(O(n)\) |
| 空间复杂度 | \(O(n + m)\) | 邻接表存储 \(O(n + m)\)，辅助数组 \(O(n)\) |
注意递归深度
当 \(n\) 较大（如 \(n = 2 \times 10^5\)）且图退化为一条链时，递归 DFS 的深度可能达到 \(O(n)\)，存在栈溢出风险。
竞赛中通常可以通过以下方式解决：
- 使用编译选项 -Wl,--stack,268435456 增大栈空间
- 改用 BFS 或迭代式 DFS
T3 - CF 510C (Medium) 拓扑排序¶
题意分析¶
题目描述
给定 \(n\) 个人名（均由小写英文字母组成，且不含重复字符）。按照字典序对这 \(n\) 个人名进行排序时， 从前到后依次比较相邻两个人名：
- 找到它们第一个不同的字符，该字符在两个人名中的先后关系确定了两个字母的相对顺序。
- 如果一个人名是另一个人名的前缀，则较短的人名排在前面（这是标准字典序规则）。
如果根据给定的人名可以确定所有 26 个小写字母的一个合法排列（即不产生矛盾），输出该排列；
否则输出 "Impossible"。
数据范围：\(1 \le n \le 100\)，人名长度 \(\le 100\)。
输入格式：
第一行一个整数 \(n\)；接下来 \(n\) 行，每行一个字符串表示人名。
输出格式：
如果存在合法的字母排列，输出该排列（一个长度为 26 的字符串，包含所有小写字母）；否则输出 "Impossible"。
样例1（存在合法字母表）：
样例1解释
相邻人名两两比较，提取字母间的约束：
rivest排在shamir之前：第一个不同字符是r与s，得到约束「r 在 s 之前」；shamir排在adleman之前：第一个不同字符是s与a，得到约束「s 在 a 之前」。
约束链 \(r \to s \to a\) 无环，因此存在合法字母表。上面的输出是正文代码的实际运行结果：
其中 r 位于第 8 位、s 位于第 11 位、a 位于第 12 位，满足全部约束。
本题答案不唯一（Special Judge），任何满足「r 在 s 前、s 在 a 前」的 26 字母排列都会被判为正确。
样例2（不存在合法字母表）：
样例2解释
ab 排在 a 之前，但 a 是 ab 的前缀。字典序规定：一个串是另一个串的前缀时，较短的串必须排在前面，
这与任何字母表的选取都无关，因此无解，输出 Impossible。
这对应代码中「没找到不同字符且前串更长」的特判分支。
重要的字典序理解
题目给出的人名是 已经按字典序排列好 的。我们需要从相邻人名的比较中提取字母间的偏序关系， 然后用拓扑排序检验是否存在环（矛盾），并输出一个合法的全序排列。
思路推导¶
第一步：建立字母间的偏序关系
依次比较每一对相邻的人名 \(s_i\) 和 \(s_{i+1}\)：
- 从左到右逐字符比较，找到第一个位置 \(j\) 使得 \(s_i[j] \ne s_{i+1}[j]\)。
- 则有偏序关系：字母 \(s_i[j]\) 在字母表中排在 \(s_{i+1}[j]\) 之前，即 \(s_i[j] \to s_{i+1}[j]\) 是一条有向边。
- 找到后即可停止比较（后续字符不再提供新信息）。
- 如果 \(s_i\) 是 \(s_{i+1}\) 的前缀（\(s_i\) 更短且所有字符相同），则不产生约束，继续。
- 如果 \(s_{i+1}\) 是 \(s_i\) 的前缀，则产生矛盾（较长的串不能排在较短的前面），直接输出
"Impossible"。
第二步：建图
用 26 个顶点（代表 26 个小写字母）构建有向图。每条边 \(c_1 \to c_2\) 表示字母 \(c_1\) 必须排在 \(c_2\) 之前。
第三步：拓扑排序
对有向图进行拓扑排序：
- 计算每个顶点的入度。
- 将入度为 0 的顶点加入队列。
- 每次取出队首顶点，加入结果序列，并将其所有邻居的入度减 1。
- 如果邻居的入度变为 0，加入队列。
- 最终如果结果序列包含所有 26 个字母，则输出该序列。
- 如果结果序列长度 \(< 26\)，说明图中存在环，输出
"Impossible"。
第四步：输出
拓扑排序的结果就是字母的一个合法排列。
算法正确性
拓扑排序能够处理的关键问题： 1. 矛盾检测：如果约束关系构成环（如 \(a < b\) 且 \(b < a\)），拓扑排序无法遍历所有顶点，从而检测到矛盾。 2. 不完全约束：某些字母之间可能没有偏序关系，拓扑排序仍然可以给出一种合法的排列。 3. 多解：拓扑排序的结果可能不唯一（取决于入度为 0 的顶点的出队顺序），任意一种都是合法答案。
完整C++代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> names(n);
for (int i = 0; i < n; i++) {
cin >> names[i];
}
// 建图：26个字母作为顶点
// adj[c] 表示字母c必须排在哪些字母之前
vector<vector<int>> adj(26);
vector<int> indeg(26, 0);
vector<bool> used(26, false); // 标记哪些字母出现在人名中
// 标记所有出现过的字母
for (auto& s : names) {
for (char c : s) {
used[c - 'a'] = true;
}
}
// 从相邻人名中提取偏序关系
for (int i = 0; i < n - 1; i++) {
string& s1 = names[i];
string& s2 = names[i + 1];
int len = min(s1.size(), s2.size());
bool found = false;
for (int j = 0; j < len; j++) {
if (s1[j] != s2[j]) {
// 找到第一个不同的字符
// s1[j] 必须排在 s2[j] 之前
int u = s1[j] - 'a';
int v = s2[j] - 'a';
adj[u].push_back(v);
indeg[v]++;
found = true;
break;
}
}
// 如果s2是s1的前缀且s1更长，则字典序矛盾
if (!found && s1.size() > s2.size()) {
cout << "Impossible\n";
return 0;
}
}
// 拓扑排序
queue<int> q;
// 将所有出现过且入度为0的字母加入队列
for (int i = 0; i < 26; i++) {
if (used[i] && indeg[i] == 0) {
q.push(i);
}
}
string result = "";
while (!q.empty()) {
int u = q.front();
q.pop();
result += (char)('a' + u);
for (int v : adj[u]) {
indeg[v]--;
if (indeg[v] == 0) {
q.push(v);
}
}
}
// 检查是否所有出现过的字母都已加入结果
int totalUsed = 0;
for (int i = 0; i < 26; i++) {
if (used[i]) totalUsed++;
}
if ((int)result.size() != totalUsed) {
// 存在环，矛盾
cout << "Impossible\n";
} else {
// 补充未出现的字母（按任意顺序追加即可）
for (int i = 0; i < 26; i++) {
if (!used[i]) {
result += (char)('a' + i);
}
}
cout << result << "\n";
}
return 0;
}
代码说明
- 使用
used数组记录哪些字母出现在输入中，避免对未出现的字母进行无意义的拓扑排序。 - 比较相邻人名时，找到第一个不同字符即停止，提取偏序关系后添加有向边。
- 特殊情况：如果 \(s_{i+1}\) 是 \(s_i\) 的前缀（\(s_i\) 更长），说明字典序矛盾，直接输出
"Impossible"。 - 拓扑排序结束后，将未出现的字母按任意顺序追加到结果末尾。
- 如果拓扑排序的结果长度不等于出现过的字母总数，说明有环，输出
"Impossible"。
边界情况
- 所有字母都不出现在人名中：此时任何排列都是合法的，直接输出
"abcdefghijklmnopqrstuvwxyz"。 - 所有人名完全相同：不产生任何约束，输出任意排列。
- 人名是另一个的前缀：如
"abc"和"abcd"，短的排前面是合法的，不产生矛盾。 - 人名中可能包含重复字母：如
"aaa"，在提取约束时不影响，因为比较的是相邻人名间的第一个 不同 字符。
复杂度分析¶
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | \(O(n \cdot L + 26)\) | \(n\) 次相邻人名比较，每次最多比较 \(L\) 个字符（\(L\) 为最大人名长度）；拓扑排序 \(O(26 + E)\)，其中 \(E \le 25\)（最多 25 条有意义的边） |
| 空间复杂度 | \(O(n \cdot L + 26^2)\) | 存储人名 \(O(n \cdot L)\)，图的邻接表 \(O(26 + E)\) |
拓展：Kahn 算法与 DFS 拓扑排序
本题使用的是 Kahn 算法（BFS 拓扑排序），其核心思想是反复移除入度为 0 的顶点。 另一种等价的实现方式是 DFS 拓扑排序： - 对每个未访问的顶点执行 DFS - DFS 结束时将当前顶点压入栈 - 最终栈的逆序即为拓扑序 - 如果 DFS 过程中遇到正在访问的顶点，说明存在环
// DFS拓扑排序的框架（供参考）
vector<int> topo_order;
vector<int> state(26, 0); // 0:未访问 1:正在访问 2:已完成
bool has_cycle = false;
void topo_dfs(int u) {
state[u] = 1; // 标记为正在访问
for (int v : adj[u]) {
if (state[v] == 1) { has_cycle = true; return; }
if (state[v] == 0) topo_dfs(v);
}
state[u] = 2; // 标记为已完成
topo_order.push_back(u);
}
两种方法的时间复杂度相同，均为 \(O(V + E)\)。在竞赛中 Kahn 算法更为常用， 因为它能直观地处理入度信息，且更容易检测环（通过判断结果长度）。
T4 - CF 1144F (Medium) 二分图染色与定向¶
题目大意
给定一个 \(n\) 个节点、\(m\) 条边的无向连通图，要求为每条边指定一个方向，使得得到的有向图中不存在长度 \(\geq 2\) 的有向路径。即：从任意节点出发，不存在经过两条或以上边的有向路径。
等价地，需要将图变为一个满足如下性质的有向图：图中不存在形如 \(u \to v \to w\) 的路径（其中 \(u \neq w\)）。
如果可行，输出 YES 并给出每条边的方向；否则输出 NO。
限制：\(2 \leq n \leq 2 \times 10^5\)，\(1 \leq m \leq 2 \times 10^5\)
题意分析¶
问题转化的关键观察
题目要求不存在长度 \(\geq 2\) 的有向路径，这意味着：对于图中任意节点 \(v\)，不能同时存在一条入边和一条出边经过 \(v\)（否则就形成长度为 2 的有向路径）。
也就是说，每个节点在最终的有向图中只能全是入边，或者只能全是出边。
这给了我们一个强烈的提示：如果把"只有出边"的节点集合记为 \(S_0\)，"只有入边"的节点集合记为 \(S_1\)，那么：
- 所有边都必须从 \(S_0\) 中的节点指向 \(S_1\) 中的节点
- \(S_0\) 内部、\(S_1\) 内部不能有边相连
这恰好就是二分图的定义！因此问题等价于：判断给定图是否为二分图。
思路推导¶
第一步：问题等价性分析
若图是二分图，将节点分为颜色 \(0\) 和颜色 \(1\) 两个集合。每条边的两个端点必然分属不同集合。我们可以规定所有边从颜色 \(0\) 的节点指向颜色 \(1\) 的节点，这样每个节点要么全是出边（颜色 \(0\)），要么全是入边（颜色 \(1\)），不会产生长度 \(\geq 2\) 的有向路径。
若图不是二分图，存在奇环，无论如何定向，奇环上必有相邻两条边方向相反（形成 \(u \to v \to w\)），因此无解。
第二步：二分图判定
使用 BFS 对图进行染色。从节点 \(1\) 出发，将其染为颜色 \(0\)，然后 BFS 遍历所有边，将邻居染为相反颜色。如果某条边的两个端点颜色相同，则不是二分图。
第三步：输出方案
如果染色成功，遍历输入的每条边 \((u, v)\)： - 若 \(color[u] = 0\)，则方向为 \(u \to v\) - 若 \(color[u] = 1\)，则方向为 \(v \to u\)（等价于 \(u\) 是入边端点）
注意事项
- 图可能不连通，但题目保证连通，所以从任意节点开始 BFS 即可
- 存储边时需要记录原始输入顺序，以便按顺序输出方向
- 开数组时注意 \(n, m\) 的范围，使用
vector邻接表
完整 C++ 代码¶
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, m;
vector<int> adj[MAXN]; // 邻接表
int color[MAXN]; // 染色数组，0 或 1
int eu[MAXN], ev[MAXN]; // 记录每条边的两个端点（按输入顺序）
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
// 读入边并建图
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
eu[i] = u;
ev[i] = v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// BFS 二分图染色
memset(color, -1, sizeof(color));
queue<int> q;
color[1] = 0;
q.push(1);
bool ok = true;
while (!q.empty() && ok) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
// 未染色，染为相反颜色
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
// 相邻节点颜色相同，不是二分图
ok = false;
break;
}
}
}
if (!ok) {
cout << "NO" << endl;
return 0;
}
// 输出方案：按颜色方向给边定向
cout << "YES" << endl;
for (int i = 0; i < m; i++) {
// 如果 eu[i] 的颜色为 0，方向 eu[i] -> ev[i]，输出 0
// 如果 eu[i] 的颜色为 1，方向 ev[i] -> eu[i]，输出 1
cout << color[eu[i]];
}
cout << endl;
return 0;
}
代码解析
- 染色方案：使用 XOR 运算
color[u] ^ 1翻转颜色（\(0 \to 1\)，\(1 \to 0\)），简洁高效 - 输出编码：对于第 \(i\) 条边 \((eu[i], ev[i])\)，直接输出
color[eu[i]]。若为 \(0\) 表示方向 \(eu[i] \to ev[i]\)，若为 \(1\) 表示方向 \(ev[i] \to eu[i]\) - 为什么这样可行？因为颜色 \(0\) 的节点只出边，颜色 \(1\) 的节点只入边，所以 \(color[eu[i]] = 0\) 时 \(eu[i]\) 是出边端点，\(color[eu[i]] = 1\) 时 \(ev[i]\) 是出边端点
复杂度分析¶
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | \(O(n + m)\) | BFS 遍历所有节点和边各一次 |
| 空间复杂度 | \(O(n + m)\) | 邻接表存储图，另有 \(O(n)\) 的染色数组 |
T5 - AT dp_v (Hard) 树形DP - 换根（Rerooting）¶
题目大意
给定一棵 \(N\) 个节点的树和一个整数 \(M\)。现在要用黑色和白色对树的节点进行染色，满足以下条件：
- 节点 \(1\) 必须染黑色
- 如果节点 \(u\)（非根）被染为黑色，则其父节点必须也被染为黑色
求：对每个节点 \(i\)（\(1 \leq i \leq N\)），有多少种合法的染色方案使得节点 \(i\) 被染为黑色。所有答案对 \(M\) 取模。
限制：\(2 \leq N \leq 10^5\)，\(2 \leq M \leq 10^9\)
题意分析¶
核心理解
条件 2 等价于：黑色节点构成的集合在树中必须是包含根节点的连通子图。
换言之，如果我们把所有黑色节点拿出来，它们必须形成一棵包含节点 \(1\) 的子树（这里的子树不要求是原树的子树，而是一个连通子图）。或者说，从根开始的某条路径上，一旦某个节点是白色，其所有后代都必须是白色。
我们来重新理解条件：如果节点 \(u\) 是黑色，父节点必须也是黑色。这意味着：
- 从根向下，黑色节点构成一个向下封闭的连通块（包含根的连通子图）
- 每个子树中，只有靠近根的部分可以染黑，后面必须全部染白
这是一道经典的换根 DP（Rerooting）题目。
思路推导¶
第一步：定义 DP 状态
以节点 \(u\) 为根，定义：
这里的"合法"指满足题目条件 2（\(u\) 的后代如果染黑，其父节点也必须染黑），但不考虑 \(u\) 本身的父节点约束。
第二步：推导转移方程
对于 \(u\) 的每个子节点 \(v\)，在 \(u\) 染黑的前提下：
- \(v\) 染黑：有 \(dp[v]\) 种方案（\(v\) 子树内部的合法方案）
- \(v\) 染白：只有 \(1\) 种方案（\(v\) 的整个子树全部染白）
因此：
基础情况：叶子节点 \(dp[leaf] = 1\)（只染黑自己）。
第三步：第一次 DFS - 子树 DP
以节点 \(1\) 为根进行 DFS，自底向上计算 \(dp[u]\)。
此时 dp[1] 就是以节点 \(1\) 为根时，整棵树的合法染色方案数（节点 \(1\) 必黑）。
第四步：换根 - 第二次 DFS
现在需要对每个节点 \(i\)，求以 \(i\) 为根（且 \(i\) 必须被染黑）时整棵树的合法方案数，记为 \(ans[i]\)。
关键难点：当把根从 \(u\) 换到其子节点 \(v\) 时，\(v\) 需要将 \(u\) 那一侧（即 \(u\) 去掉 \(v\) 子树后的部分）作为"新的子树"来计算贡献。
设 \(val(v \to u)\) 表示从 \(v\) 的角度看 \(u\) 方向（即 \(u\) 去掉 \(v\) 子树后的部分）对 \(v\) 的贡献因子。则：
其中 \(val(u \to v)\) 的计算：
当 \(u\) 是 \(v\) 的父节点时，\(u\) 方向的贡献等于 \(u\) 除 \(v\) 以外所有邻居方向的贡献之积：
前缀积后缀积优化
直接枚举所有 \(w \neq v\) 会导致单次换根的复杂度为 \(O(\text{degree}(u))\)，总复杂度退化为 \(O(n^2)\)。
优化方法：对 \(u\) 的所有子节点 \(v_1, v_2, \ldots, v_k\)，预先计算前缀积和后缀积：
则去除第 \(i\) 个子节点后的积为 \(pre[i-1] \times suf[i+1]\)，可以在 \(O(1)\) 时间内得到。
总体换根过程的复杂度为 \(O(n)\)。
第五步：算法总结
- 第一次 DFS（后序遍历）：以节点 \(1\) 为根，计算每个节点的子树 DP 值 \(dp[u]\)
- 第二次 DFS（前序遍历）：从根开始向下传递，对每个节点计算所有子节点的前缀积和后缀积，从而 \(O(1)\) 计算换根贡献，得到 \(ans[v]\)
- 输出 \(ans[1], ans[2], \ldots, ans[N]\)
完整 C++ 代码¶
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
long long M; // 取模数（注意可能很大，用 long long）
vector<int> adj[MAXN]; // 邻接表（无向图）
long long dp[MAXN]; // dp[u]: 以1为根时，u子树中u染黑的方案数
long long ans[MAXN]; // ans[u]: 以u为根时整棵树的方案数
// ========== 第一次 DFS：自底向上计算 dp ==========
void dfs1(int u, int parent) {
dp[u] = 1; // 基础值：至少染黑自己
for (int v : adj[u]) {
if (v == parent) continue;
dfs1(v, u);
// 子节点 v 可以染黑(dp[v]种)或染白(1种)
dp[u] = dp[u] * (dp[v] + 1) % M;
}
}
// ========== 第二次 DFS：换根，计算每个节点为根的答案 ==========
void dfs2(int u, int parent, long long parent_contrib) {
// parent_contrib: 从父节点方向传来的贡献值
// 即 u 的父节点在"去除 u 子树后"作为 u 的子树时的方案数
// 收集所有子节点的 dp 值
vector<int> children;
for (int v : adj[u]) {
if (v == parent) continue;
children.push_back(v);
}
int k = children.size();
// 计算前缀积和后缀积
// pre[i]: children[0..i] 的 (dp[child]+1) 的前缀积
// suf[i]: children[i..k-1] 的 (dp[child]+1) 的后缀积
vector<long long> pre(k + 1, 1), suf(k + 1, 1);
for (int i = 0; i < k; i++) {
pre[i + 1] = pre[i] * (dp[children[i]] + 1) % M;
}
for (int i = k - 1; i >= 0; i--) {
suf[i] = suf[i + 1] * (dp[children[i]] + 1) % M;
}
// 当前节点 u 为根的答案
// = 父方向贡献 * 所有子节点贡献
// = (parent_contrib + 1) * pre[k]
// 注意：parent_contrib 对应的是父节点方向，也要 +1 表示"该方向染白"
ans[u] = (parent_contrib + 1) % M * pre[k] % M;
// 向每个子节点 v 传递换根信息
for (int i = 0; i < k; i++) {
int v = children[i];
// 去除 v 之后，u 剩余所有方向的积
// = pre[i] * suf[i+1] * (parent_contrib + 1)
long long val = pre[i] * suf[i + 1] % M;
val = val * (parent_contrib + 1) % M;
// val 就是"从 v 的角度看 u 方向"的 dp 值
dfs2(v, u, val);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> M;
// 读入树的边
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 第一次 DFS：计算子树 DP
dfs1(1, -1);
// 第二次 DFS：换根计算每个节点的答案
// 根节点 1 没有父方向贡献，传入 0
dfs2(1, -1, 0);
// 输出每个节点的答案
for (int i = 1; i <= n; i++) {
cout << ans[i] << "\n";
}
return 0;
}
代码核心逻辑详解
关于 parent_contrib 的含义：
dfs2(u, parent, parent_contrib) 中，parent_contrib 表示：如果把 parent 看作 u 的一个子节点，那么以 parent 为根的"去掉 u 子树后的部分"的合法染色方案数。
- 对于根节点 \(1\)，
parent_contrib = 0（没有父方向） - \(parent\_contrib + 1\) 表示该方向"染白"（贡献为 1）或"染黑"（贡献为 \(parent\_contrib\)）
关于前缀积后缀积：
当需要计算"去除子节点 \(v\) 后剩余子节点的积"时：
但模意义下除法需要逆元，而 \(M\) 不一定是质数（题目中 \(2 \leq M \leq 10^9\)），无法保证逆元存在。因此使用前缀积后缀积避免除法，这是本题的核心技巧。
易错点提醒
- 取模问题：\(M\) 可能不是质数，不能使用逆元，必须用前缀积后缀积
- 数据范围：\(M\) 可能达到 \(10^9\)，两个数相乘可能溢出
int，必须用long long parent_contrib为 0 的含义：根节点传入 0，表示没有父方向，此时 \((0 + 1) = 1\) 不影响乘积- 边是无向的：建图时注意存双向边，DFS 时通过
parent参数避免走回头路
复杂度分析¶
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | \(O(n)\) | 两次 DFS 各 \(O(n)\)，前缀积后缀积的总开销为所有节点度数之和 \(O(n)\) |
| 空间复杂度 | \(O(n)\) | 邻接表 \(O(n)\)，DP 数组 \(O(n)\)，前缀积后缀积为临时数组总和 \(O(n)\) |
换根 DP 总结
换根 DP（Rerooting）是一种在树上高效计算"以每个节点为根时的最优解/方案数"的通用技巧。核心步骤：
- 第一次 DFS：以任意节点为根，自底向上计算每个子树的 DP 值
- 第二次 DFS：自顶向下传递父方向的贡献，利用前缀积后缀积在 \(O(1)\) 时间内完成换根
- 关键约束：当转移中需要排除某个子树的贡献时，若无法使用逆元（如模数非质数），必须使用前缀积后缀积技巧
适用场景：树上距离和、子树大小统计、树上染色方案数等"需要对每个节点分别求根"的问题。
17.2 图论专项训练（ACM Day6-7）¶
模拟赛1 的 T2/T3/T4 集中暴露了图论方向的短板：环检测、拓扑排序、二分图染色都属于"模板熟练度"型考点， 失分往往不是不会，而是写得慢、细节错。本节安排两天图论专项训练：Day6 主攻 BFS/DFS 与最短路， Day7 主攻最小生成树、强连通分量、拓扑排序与图染色。建议先完成 Day6 打牢基础再进入 Day7； 每题限时 40 分钟，超时后看提示补做，并把踩过的坑记入错题本。
ACM Day6：图论基础¶
| # | 平台 | 题号 | 题目名称 | 难度 | 核心算法 |
|---|---|---|---|---|---|
| 1 | CF | 2041D | Drunken Maze | 1700 | BFS、最短路 |
| 2 | CF | 2023B | Skipping | 1700 | 最短路、DP |
| 3 | CF | 1915G | Bicycles | 1800 | Dijkstra |
| 4 | CF | 2014E | Rendez-vous de Marian et Robin | 1800 | Dijkstra、多源最短路 |
| 5 | CF | 1975D | Paint the Tree | 1700 | BFS、树直径 |
| 6 | CF | 2060E | Graph Composition | 1500 | DFS、图遍历 |
| 7 | CF | 2027C | Add Zeros | 1500 | DFS、图建模 |
| 8 | AT | abc384_e | Takahashi is Slime 2 | 1600 | Dijkstra、BFS |
| 9 | AT | arc185_d | Random Walk on Tree | 1900 | DFS、树、期望 |
| 10 | 洛谷 | P1144 | 最短路计数 | 1600 | BFS、最短路计数 |
| 11 | 洛谷 | P9754 | [CSP-S 2023] 消消乐 | 1800 | DFS、搜索、剪枝 |
ACM Day7：图论进阶¶
| # | 平台 | 题号 | 题目名称 | 难度 | 核心算法 |
|---|---|---|---|---|---|
| 1 | CF | 1245D | Shichikuji and Power Grid | 1900 | MST、Kruskal |
| 2 | CF | 427C | Checkposts | 1700 | 强连通分量、Tarjan |
| 3 | CF | 1986F | Non-academic Problem | 1900 | 桥、Tarjan |
| 4 | CF | 770C | Online Courses In BSU | 1700 | 拓扑排序 |
| 5 | CF | 1931F | Chat Screenshots | 1700 | 拓扑排序 |
| 6 | CF | 1991D | Prime XOR Coloring | 1900 | 图染色、二分图 |
| 7 | CF | 1927F | Microcycle | 1900 | DSU、最小环 |
| 8 | AT | abc277_d | Takahashi's Solitaire | 1800 | DSU、连通分量 |
| 9 | AT | arc111_b | Reversible Cards | 1800 | 图论、DSU |
| 10 | AT | abc265_d | Iroha and Haiku | 1800 | 前缀和、二分 |
| 11 | 洛谷 | P2661 | 信息传递 | 1700 | 拓扑排序、DSU、最小环 |
| 12 | 洛谷 | P1347 | 排序 | 1600 | 拓扑排序、环检测 |
重点题提示¶
CF 2041D - Drunken Maze（BFS 状态扩展）
网格最短路，但不允许朝同一方向连续走超过 3 步。考点：BFS 状态设计。 提示：把状态从 \((x, y)\) 扩展为 \((x, y, \text{方向}, \text{连续步数})\)，转移时同方向计数 \(+1\)（超过 3 则禁止）， 换方向计数重置为 1。状态数为 \(O(nm \times 4 \times 3)\)，普通 BFS 即可。
CF 1245D - Shichikuji and Power Grid（虚拟源点 MST）
每个城市可以自建电站（花费 \(c_i\)）或连电线到已通电城市（按距离计费），求全部通电的最小花费。 考点：MST 建模。提示：加一个虚拟节点 0，向每个城市 \(i\) 连一条权为 \(c_i\) 的边（表示自建电站）， 城市之间按曼哈顿距离连边，对整张图跑 Kruskal/Prim 即为答案。
CF 427C - Checkposts（SCC 缩点计数）
有向图中每个强连通分量只需在其中任意一点设检查站即可覆盖整个分量。 考点：Tarjan/Kosaraju 缩点。提示：每个 SCC 的最小花费为分量内点权最小值， 总花费为各分量最小值之和；方案数为各分量中"取到最小值的点的个数"之积（对 \(10^9+7\) 取模）。
CF 1931F - Chat Screenshots（拓扑判矛盾）
每张截图给出一名用户视角下的消息排列（自己排第一，其余顺序为全局顺序）。判断是否存在一致的全局顺序。 考点：拓扑排序判环。提示：每张截图去掉第一个元素后，相邻两元素连一条有向边； 所有截图的边合并后跑拓扑排序，无环则一致（输出 YES），有环则矛盾。
训练建议
- 最短路三件套（BFS / Dijkstra / 0-1 BFS）必须做到 10 分钟内默写无误。
- 图论题的常见失分点是建图而不是算法：虚拟源点、拆点、状态扩展都是"把问题变成模板"的手段。
- 拓扑排序既是排序工具，也是判矛盾（判环）工具，两个用法都要熟。
- 做完后回看 17.1 的 T2（环检测）、T3（拓扑排序）、T4（二分图染色），检验是否能一遍写对。
17.3 模拟赛2（ACM Day8）¶
本节包含五道经典题目，涵盖计数贪心、树上贪心、区间博弈DP、区间合并DP、以及折半搜索等核心算法技巧。建议按顺序完成，逐步提升难度。
T1 - CF 1996D (Medium)¶
题目描述
给定两个正整数 \(n\) 和 \(x\)，统计满足以下条件的有序正整数三元组 \((a, b, c)\) 的个数：
- \(ab + ac + bc \le n\)
- \(a + b + c \le x\)
注意顺序敏感：\((1, 1, 2)\) 与 \((1, 2, 1)\) 视为不同的三元组。
数据范围：\(1 \le t \le 10^4\)，\(1 \le n, x \le 10^6\)； 保证所有测试用例的 \(n\) 之和与 \(x\) 之和均不超过 \(10^6\)。
样例：
第一组中满足条件的三元组为 \((1,1,1)\)、\((1,1,2)\)、\((1,2,1)\)、\((2,1,1)\)，共 4 个。
题意分析¶
直接枚举 \((a, b, c)\) 是 \(O(n^3)\) 级别，显然不可行。突破口在第一个条件：由于 \(ac \ge 1\)、\(bc \ge 1\)，
固定 \(a\) 后，\(b\) 至多取到约 \(n / a\) 个值，因此枚举所有满足 \(ab < n\) 的 \((a, b)\) 的总量为
这正是调和级数枚举。而对固定的 \((a, b)\)，两个条件都化为对 \(c\) 的上界限制，\(c\) 的合法取值是一段从 \(1\) 开始的连续区间，可以 \(O(1)\) 直接计数，完全不需要枚举 \(c\)。
思路推导¶
第一步：把两个条件都改写成对 \(c\) 的限制
固定 \(a, b\) 之后：
- \(ab + ac + bc \le n \iff ab + (a+b)c \le n \iff c \le \dfrac{n - ab}{a + b}\)
- \(a + b + c \le x \iff c \le x - a - b\)
第二步：区间计数
\(c\) 的上界为
下界为 \(1\)。只要 \(c_{\max} \ge 1\)，就恰有 \(c_{\max}\) 个合法的 \(c\)，直接累加到答案。
第三步：收紧枚举范围
为保证 \(c = 1\) 至少可行，枚举 \((a, b)\) 时只需满足：
- \(ab + a + b \le n\)（即 \(c = 1\) 时第一个条件成立，蕴含 \(ab < n\)）；
- \(a + b + 1 \le x\)。
在第一个条件约束下，内层 \(b\) 的枚举上界约为 \(n / a\)，整体枚举量由调和级数控制在 \(O(n \log n)\)。
完整C++代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n, x;
cin >> n >> x;
long long ans = 0;
// 枚举 a 与 b。c >= 1 时两条件分别要求：
// ab + ac + bc <= n => ab + (a+b) <= n
// a + b + c <= x => a + b + 1 <= x
for (long long a = 1; 2 * a + 1 <= n && a + 2 <= x; a++) {
for (long long b = 1; a * b + a + b <= n && a + b + 1 <= x; b++) {
// 由 ab + (a+b)c <= n 得 c <= (n - ab) / (a+b)
long long c1 = (n - a * b) / (a + b);
// 由 a + b + c <= x 得 c <= x - a - b
long long c2 = x - a - b;
ans += min(c1, c2); // 循环条件保证 min(c1, c2) >= 1
}
}
cout << ans << "\n";
}
return 0;
}
易错点
- 答案会爆 int：\(n = 9 \times 10^5\) 时答案已超过 \(1.7 \times 10^9\)，必须用
long long累加。 - 不要枚举 \(c\)：三重循环必然超时，\(c\) 的贡献是一段区间，用 \(\min\) 直接计数。
- 有序三元组不需要乘排列数：枚举的 \((a, b)\) 本身就是有序对，区间计数天然覆盖所有顺序。
- 外层循环的终止条件要同时带上 \(n\) 与 \(x\) 两个约束，否则在 \(x\) 很小、\(n\) 很大时会做大量无效枚举。
复杂度分析¶
- 时间复杂度：单组 \(O(n \log n)\)；由于 \(\sum n \le 10^6\)，全部测试用例总量约 \(O\big((\sum n) \log (\sum n)\big)\)
- 空间复杂度：\(O(1)\)，仅使用常数额外空间
T2 - CF 2063C (Medium)¶
题目描述
Codeforces 2063C - Remove Exactly Two
给定一棵 \(n\) 个节点的树。你必须恰好执行两次下面的操作：
- 选择一个当前仍存在的节点 \(v\)，删除 \(v\) 以及所有与 \(v\) 相连的边。
求两次操作后，剩余图的连通分量个数的最大值。约定 \(0\) 个节点的图有 \(0\) 个连通分量。
数据范围：\(1 \le t \le 10^4\)，\(2 \le n \le 2 \times 10^5\)； 保证所有测试用例的 \(n\) 之和不超过 \(2 \times 10^5\)。
样例：
第三组中删除节点 \(1\) 和 \(5\)，剩余连通分量为 \(\{2,4\}\)、\(\{3\}\)、\(\{6\}\)、\(\{7\}\)，共 4 个。
题意分析¶
先看只删一个点会发生什么：从树中删除度数为 \(d\) 的节点，原来的 1 个连通块会裂成 \(d\) 个。
再删第二个点。设两个被删点在原树中的度数分别为 \(d_u, d_v\)：
- 若 \(u, v\) 不相邻：删 \(v\) 时它所在的连通块裂成 \(d_v\) 块，总分量数为 \(d_u + d_v - 1\)；
- 若 \(u, v\) 相邻：边 \((u, v)\) 已随 \(u\) 一起删除，删 \(v\) 时其实际度数只剩 \(d_v - 1\)，总分量数为 \(d_u + d_v - 2\)。
统一写成一个公式：
于是问题转化为：在树上选两个不同的点，最大化 \(S = d_u + d_v - [u, v \text{ 相邻}]\)，答案为 \(S_{\max} - 1\)。
思路推导¶
第一步：交换论证——第一个点可以取最大度数点
设最大度数为 \(M_1\)。若最优解 \((x, y)\) 中两点度数都小于 \(M_1\)，取任一最大度数点 \(u\) 替换其中度数较小的 \(x\)： 度数至少增加 \(1\)，而相邻标记 \([u, y\ \text{相邻}]\) 最多比原来多 \(1\)，故 \(S\) 不会变差。 因此只需枚举最大度数点作为其中一个被删点。
第二步：按最大度数点的个数分情况
设度数达到 \(M_1\) 的点有 \(cnt\) 个：
- \(cnt \ge 3\)：树中不存在三角形，三个点不可能两两相邻，必有两个互不相邻的最大度数点， 直接得 \(S_{\max} = 2M_1\)。
- \(cnt \le 2\)：逐个枚举最大度数点 \(u\)，求 \(\max_{v \ne u}\big(d_v - [u, v \text{ 相邻}]\big)\)。
设 \(M_2 = \max_{v \ne u} d_v\)：
- 若存在度数为 \(M_2\) 且不与 \(u\) 相邻的点，则该项取 \(M_2\)；
- 否则度数为 \(M_2\) 的点全是 \(u\) 的邻居，而非邻居的度数至多 \(M_2 - 1\)，两种选法都只能取到 \(M_2 - 1\)。
判断方法：比较「度数为 \(M_2\) 的点的总数（去掉 \(u\) 自身）」与「\(u\) 的邻居中度数为 \(M_2\) 的个数」是否有富余。
第三步：汇总
答案为 \(S_{\max} - 1\)。注意 \(n = 2\) 时删两次后图为空，公式给出 \(1 + 1 - 1 - 1 = 0\)，与"空图 \(0\) 个分量"的约定一致，无需特判。
完整C++代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
vector<int> deg(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
// 最大度数 M1 及取到 M1 的顶点集合
int M1 = 0;
for (int i = 1; i <= n; i++) M1 = max(M1, deg[i]);
vector<int> maxV;
for (int i = 1; i <= n; i++)
if (deg[i] == M1) maxV.push_back(i);
long long best; // best = max over pairs (deg u + deg v - [u,v相邻])
if ((int)maxV.size() >= 3) {
// 树中无三角形，>=3 个最大度点必有两个互不相邻
best = 2LL * M1;
} else {
best = 0;
for (int u : maxV) {
// 在 v != u 中找 max(deg v - [v 与 u 相邻])
int M2 = 0;
for (int v = 1; v <= n; v++)
if (v != u) M2 = max(M2, deg[v]);
int total = 0;
for (int v = 1; v <= n; v++)
if (v != u && deg[v] == M2) total++;
int nb = 0;
for (int v : adj[u])
if (deg[v] == M2) nb++;
// 存在度为 M2 的非邻居 => 贡献 M2；否则最优只能是 M2-1
long long S = deg[u] + (total > nb ? M2 : M2 - 1);
best = max(best, S);
}
}
cout << best - 1 << "\n";
}
return 0;
}
注意事项
- 度数一定取原树中的度数，相邻时手动减去 1，不要在删第一个点后重算度数再取最大（那样会丢失"两点同时删"的耦合信息）。
- \(cnt \ge 3\) 时可以直接给出答案，正确性依赖"树中无三角形"这一性质，一般图上不成立。
- 枚举的最大度数点至多 2 个，每次 \(O(n)\) 扫描即可，不需要更复杂的数据结构。
- 多测清空：使用局部
vector或手动清空邻接表与度数数组。
复杂度分析¶
- 时间复杂度：\(O(n)\)，统计度数与至多 2 次全表扫描
- 空间复杂度：\(O(n)\)，邻接表与度数数组
T3 - AT dp_l (Medium)¶
题目描述
给定 \(N\) 个正整数 \(a_1, a_2, \ldots, a_N\) 排成一行。太郎和次郎轮流从序列的两端取数，太郎先手。两人都采取最优策略，目标是最大化自己取到的数之和。求太郎最终取到的数之和。
数据范围：\(1 \le N \le 3000\)，\(1 \le a_i \le 10^9\)
题意分析¶
这是一道经典的区间博弈DP问题。两人轮流从两端取数，都采用最优策略。关键在于：每个玩家在自己的回合选择对自己最有利的方案，即最大化自己的总收益。
注意：由于总和固定，最大化自己的收益等价于最大化（自己的收益 - 对方的收益），即最大化"优势"。
思路推导¶
第一步：定义状态
设 \(dp[l][r]\) 表示在区间 \([l, r]\) 中，当前先手玩家相对于后手玩家的最大优势（即先手得分减去后手得分）。
第二步：状态转移
当区间为 \([l, r]\) 时，当前先手玩家有两个选择：
- 取左端 \(a_l\)：剩余区间为 \([l+1, r]\)，此时对方变成先手，对方的优势为 \(dp[l+1][r]\)。所以当前玩家的净优势为 \(a_l - dp[l+1][r]\)
- 取右端 \(a_r\)：剩余区间为 \([l, r-1]\)，当前玩家的净优势为 \(a_r - dp[l][r-1]\)
转移方程：
第三步：边界条件
当 \(l = r\) 时，\(dp[l][l] = a_l\)（只有一数可取，直接拿走）。
第四步：计算答案
最终太郎的优势为 \(dp[1][N]\)。太郎的得分为：
推导：设太郎得 \(x\)，次郎得 \(y\)，则 \(x + y = S\)，\(x - y = dp[1][N]\)，解得 \(x = (S + dp[1][N]) / 2\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
long long total_sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
total_sum += a[i];
}
// dp[l][r]：区间[l, r]中先手相对于后手的最大优势
// 由于N可达3000，二维数组需要优化空间
// 使用滚动数组：按区间长度递推
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
// 边界：长度为1的区间
for (int i = 1; i <= n; i++) {
dp[i][i] = a[i];
}
// 按区间长度递推，长度从2到n
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
// 取左端：优势为 a[l] - dp[l+1][r]
// 取右端：优势为 a[r] - dp[l][r-1]
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
}
}
// 太郎得分 = (总和 + 优势) / 2
long long ans = (total_sum + dp[1][n]) / 2;
cout << ans << "\n";
return 0;
}
为什么用"优势"而不是直接得分？
直接定义 \(dp[l][r]\) 为先手在区间 \([l,r]\) 中能获得的最大得分是错误的，因为后手的策略会影响先手的得分。用"优势"（先手得分 - 后手得分）来定义，转移方程就变成了 \(\max(a_l - dp[l+1][r], a_r - dp[l][r-1])\)，因为轮到对方时对方也想最大化自己的优势，相当于先手的优势减少。
复杂度分析¶
- 时间复杂度：\(O(n^2)\)，枚举所有区间 \([l, r]\)，共 \(O(n^2)\) 个状态，每个状态 \(O(1)\) 转移
- 空间复杂度：\(O(n^2)\)，存储DP数组。可优化至 \(O(n)\) 使用滚动数组
T4 - AT dp_n (Medium)¶
题目描述
有 \(N\) 堆石子排成一行，第 \(i\) 堆有 \(a_i\) 个石子。每次可以合并相邻的两堆，代价为合并后石子的总数。求将所有石子合并成一堆的最小总代价。
数据范围：\(2 \le N \le 400\)，\(1 \le a_i \le 10^9\)
题意分析¶
这是经典的"合并石子"问题，也叫"矩阵链乘法"的变体。核心难点在于：合并顺序不同，总代价差异巨大。
例如：石子堆为 \([3, 1, 2, 4]\)。若先合并 \((3,1) \to 4\)，再合并 \((2,4) \to 6\)，最后合并 \((4,6) \to 10\)，总代价 \(4 + 6 + 10 = 20\)。不同的合并顺序会有不同的结果。
思路推导¶
第一步：识别子问题
将区间 \([l, r]\) 合并成一堆的最小代价，取决于最后一次合并前，左右两部分分别是什么。设最后一次合并将 \([l, k]\) 和 \([k+1, r]\) 合并，则：
其中 \(\text{sum}(l, r) = a_l + a_{l+1} + \cdots + a_r\)。
第二步：前缀和优化
预处理前缀和 \(s[i] = a_1 + a_2 + \cdots + a_i\)，则 \(\text{sum}(l, r) = s[r] - s[l-1]\)，\(O(1)\) 查询。
第三步：区间DP递推顺序
按区间长度从小到大递推。长度为1的区间代价为0（不需要合并）。长度从2递推到 \(N\)。
第四步：边界条件
\(dp[i][i] = 0\)（一堆石子不需要合并，代价为0）。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
vector<long long> prefix(n + 1, 0); // 前缀和
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
// dp[l][r]：将区间[l, r]合并成一堆的最小代价
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
// 初始化：长度为1的区间代价为0（已经是单堆）
// dp[i][i] = 0，已经初始化
// 按区间长度递推
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
long long sum_lr = prefix[r] - prefix[l - 1]; // 区间总和
dp[l][r] = LLONG_MAX; // 初始化为无穷大
// 枚举分割点k，将[l,r]分成[l,k]和[k+1,r]
for (int k = l; k < r; k++) {
long long cost = dp[l][k] + dp[k + 1][r] + sum_lr;
dp[l][r] = min(dp[l][r], cost);
}
}
}
cout << dp[1][n] << "\n";
return 0;
}
与矩阵链乘法的关系
合并石子问题和矩阵链乘法（Matrix Chain Multiplication）本质上是同一个DP模型。矩阵链乘法中，\(A_1 \times A_2 \times \cdots \times A_n\) 的不同括号化方式对应不同的乘法次数，求最少乘法次数。转移方程结构完全相同，只是"代价"的计算方式不同。
注意溢出
由于 \(a_i\) 可达 \(10^9\)，合并代价可能非常大。\(N = 400\) 时总代价可达 \(400 \times 10^9 = 4 \times 10^{11}\)，需要用 long long 存储。
复杂度分析¶
- 时间复杂度：\(O(n^3)\)，三层循环：枚举长度 \(O(n)\)、枚举左端点 \(O(n)\)、枚举分割点 \(O(n)\)
- 空间复杂度：\(O(n^2)\)，存储DP数组
- 优化提示：利用Knuth优化（平行四边形不等式），可将时间复杂度降至 \(O(n^2)\)。转移条件为 \(dp[l][r] = \min_{opt[l][r-1] \le k \le opt[l+1][r]} \{ dp[l][k] + dp[k+1][r] \} + \text{sum}(l,r)\)
T5 - AT abc184_f (Hard)¶
题目描述
给定 \(N\) 个正整数 \(a_1, a_2, \ldots, a_N\) 和一个上限 \(T\)。从中选出一个子集（可以为空），使得子集元素之和不超过 \(T\)，且尽可能大。求这个最大和。
数据范围：\(1 \le N \le 40\)，\(1 \le T \le 10^9\)，\(1 \le a_i \le 10^9\)
题意分析¶
本题是0-1背包问题的变体。标准的0-1背包DP时间复杂度为 \(O(N \cdot T)\)，但本题中 \(T\) 可达 \(10^9\)，数组无法开这么大。
然而 \(N\) 只有 \(40\)，如果暴力枚举所有 \(2^{40} \approx 10^{12}\) 个子集也超时。但如果能将搜索量降为 \(2^{20} \approx 10^6\)，就可以接受。
这就是折半搜索（Meet in the Middle） 的应用场景。
思路推导¶
第一步：暴力枚举为何不可行
\(N = 40\) 时，所有子集数量为 \(2^{40} \approx 1.1 \times 10^{12}\)，直接枚举超时。
第二步：折半的核心思想
将 \(N\) 个数分成两半： - 左半部分：\(a_1, a_2, \ldots, a_{N/2}\)（约20个数） - 右半部分：\(a_{N/2+1}, a_{N/2+1}, \ldots, a_N\)（约20个数）
分别枚举两半的所有子集和，各得到约 \(2^{20} \approx 10^6\) 个值。
第三步：合并策略
设左半部分的子集和集合为 \(L\)，右半部分的子集和集合为 \(R\)。我们希望找到 \(l \in L\)，\(r \in R\)，使得 \(l + r \le T\) 且 \(l + r\) 最大。
- 将 \(R\) 排序
- 对于每个 \(l \in L\)，在 \(R\) 中二分查找最大的 \(r\) 使得 \(l + r \le T\)，即 \(r \le T - l\)
- 维护全局最大值
第四步：正确性证明
每个子集都可以唯一地分成"左半部分被选中的元素"和"右半部分被选中的元素"。因此枚举两半的所有组合可以覆盖全部 \(2^N\) 个子集，不会遗漏。
第五步：实现细节
- 枚举子集和：用位掩码从 \(0\) 到 \(2^{n/2} - 1\) 遍历
- 排序：对 \(R\) 排序后使用
upper_bound二分查找 - 空子集：和为 \(0\)，是合法的（可以选择不选任何数）
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long T;
cin >> n >> T;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 将数组分成两半
int mid = n / 2;
int left_size = mid; // 左半部分大小
int right_size = n - mid; // 右半部分大小
// ---- 枚举左半部分的所有子集和 ----
vector<long long> left_sums;
left_sums.reserve(1 << left_size);
for (int mask = 0; mask < (1 << left_size); mask++) {
long long sum = 0;
for (int i = 0; i < left_size; i++) {
if (mask & (1 << i)) {
sum += a[i];
}
}
left_sums.push_back(sum);
}
// ---- 枚举右半部分的所有子集和 ----
vector<long long> right_sums;
right_sums.reserve(1 << right_size);
for (int mask = 0; mask < (1 << right_size); mask++) {
long long sum = 0;
for (int i = 0; i < right_size; i++) {
if (mask & (1 << i)) {
sum += a[mid + i];
}
}
right_sums.push_back(sum);
}
// 对右半部分的子集和排序，用于二分查找
sort(right_sums.begin(), right_sums.end());
// ---- 枚举左半部分，二分查找最优的右半部分 ----
long long ans = 0;
for (long long lsum : left_sums) {
// 左半部分选了lsum，右半部分最多选 T - lsum
long long remain = T - lsum;
if (remain < 0) continue; // 左半部分已经超过T，跳过
// 在right_sums中找到 <= remain 的最大值
// upper_bound返回第一个 > remain 的迭代器
auto it = upper_bound(right_sums.begin(), right_sums.end(), remain);
if (it != right_sums.begin()) {
--it; // 退回到 <= remain 的最大元素
long long total = lsum + *it;
ans = max(ans, total);
} else {
// 右半部分不选任何元素（和为0已在left_sums中处理）
// 此时只考虑左半部分本身
if (lsum <= T) {
ans = max(ans, lsum);
}
}
}
cout << ans << "\n";
return 0;
}
折半搜索的核心模板
折半搜索适用于枚举量指数级但可分半的问题。通用模板：
- 将决策变量分成两半（通常各 \(N/2\) 个）
- 分别暴力枚举两半的所有可能状态
- 用排序 + 二分（或双指针、哈希表等）合并两半的结果
- 时间复杂度从 \(O(2^N)\) 降低到 \(O(2^{N/2} \cdot N)\)
常见应用场景： - 子集和问题（本题） - 最大独立集（小规模图） - 集合划分（Meet in the Middle + 双指针） - 搜索问题中的剪枝优化
常见陷阱
- 不要忘记空子集：和为 \(0\) 也是合法的，
mask = 0时和为 \(0\) - 注意 \(T\) 的范围：\(T\) 可达 \(10^9\)，
remain可能为负数，需要特判 - 排序去重：如果右半部分有重复的子集和，不影响正确性（
upper_bound仍然正确），但可以去重减少二分查找的时间 - 整数溢出：\(N = 40\)，\(a_i = 10^9\) 时，子集和最大为 \(40 \times 10^9 = 4 \times 10^{10}\)，需要用
long long
复杂度分析¶
-
时间复杂度：\(O(2^{N/2} \cdot N)\)
- 枚举左半子集和：\(O(2^{N/2} \cdot N/2)\)
- 枚举右半子集和：\(O(2^{N/2} \cdot N/2)\)
- 排序右半：\(O(2^{N/2} \cdot \log(2^{N/2})) = O(2^{N/2} \cdot N/2)\)
- 二分查找合并：\(O(2^{N/2} \cdot \log(2^{N/2})) = O(2^{N/2} \cdot N/2)\)
- 总计：\(O(2^{N/2} \cdot N)\)，当 \(N = 40\) 时约为 \(2^{20} \times 40 \approx 4 \times 10^7\)，可接受
-
空间复杂度：\(O(2^{N/2})\)，存储两半的子集和数组，当 \(N = 40\) 时约 \(2^{20} \approx 10^6\) 个
long long，约 8MB
拓展：Meet in the Middle 的更多应用
- 最短路问题：在大图上，从起点和终点分别 BFS，在中间相遇
- 字符串匹配：将模式串分半，分别匹配后合并
- 数独求解：将搜索空间分半，减少分支因子
- 与双向BFS结合：在搜索问题中，双向搜索的期望复杂度从 \(O(b^d)\) 降低到 \(O(b^{d/2})\)
17.4 复盘与补缺（ACM Day13）¶
经过三场模拟赛的洗礼，队伍对自身的薄弱环节已经有了较为清晰的认知。本节针对模拟赛中暴露的高频失分点，按专题整理了 23 道补充练习题，覆盖贪心、DP、图论、二分、数据结构、字符串、数论、树及搜索九大方向。建议各队员根据自身短板优先攻克对应专题，并在练习中注重模板的熟练度和边界条件的处理。
分类练习总览¶
| 编号 | 来源 | 题号 | 专题 | 题目关键词 |
|---|---|---|---|---|
| 1 | CF | 1204C | 贪心 | 邻接矩阵·路径插入·最短路 |
| 2 | CF | 1921D | 贪心 | 双数组配对·差值最大·双指针 |
| 3 | AT | abc223_c | 贪心 | 导火索·相遇位置·模拟 |
| 4 | CF | 1399C | 贪心 | 体重配对·枚举目标和 |
| 5 | AT | dp_c | DP | 三天活动·相邻限制·线性DP |
| 6 | AT | dp_e | DP | 01背包变体·价值维度 |
| 7 | AT | dp_g | DP | DAG最长路径·拓扑排序 |
| 8 | CF | 455A | DP | 取数游戏·值域DP |
| 9 | AT | dp_h | DP | 网格路径计数·障碍物 |
| 10 | AT | abc361_d | 图论 | 交换空位·BFS状态搜索 |
| 11 | AT | abc204_c | 图论 | 有向图可达·多源BFS |
| 12 | CF | 2000E | 图论 | 网格放置·权值最大·贪心 |
| 13 | AT | abc373_d | 二分 | 约束关系·确定节点值 |
| 14 | CF | 1201C | 二分 | 中位数提升·最少操作 |
| 15 | AT | abc330_d | 数据结构 | 网格标记·行列计数 |
| 16 | CF | 706C | 数据结构 | 字符串翻转·字典序·DP |
| 17 | AT | abc284_e | 字符串 | 简单路径计数·DFS回溯 |
| 18 | CF | 1294D | 字符串 | 在线查询·mex取模 |
| 19 | AT | abc334_d | 数论 | 驯鹿分配·前缀和+二分 |
| 20 | CF | 1542C | 数论 | gcd与lcm·容斥 |
| 21 | AT | abc148_f | 树 | 树上追击·BFS+直径 |
| 22 | AT | abc340_d | 树 | 宝箱选择·Dijkstra |
| 23 | AT | abc184_d | 搜索 | 硬币期望·记忆化搜索 |
贪心 (Greedy)¶
1. CF 1204C - 路径插入最少节点
给定 \(n\) 个节点的邻接矩阵和一条包含 \(m\) 个节点的路径序列，求最少需要插入多少个节点使得路径中相邻节点有边直接相连。考点：Floyd 预处理最短路 + 贪心。解法：先 Floyd 预处理所有点对最短距离，然后贪心判断路径中相邻两点是否可直接到达，累加 \(\text{dist}(a,b)-1\) 即为答案。
2. CF 1921D - 差值之和最大配对
给定数组 \(a\)（长度 \(n\)）和 \(b\)（长度 \(m \ge n\)），从 \(b\) 中选取 \(n\) 个数配对使得差的绝对值之和最大。考点：排序 + 双指针贪心。解法：\(a\)、\(b\) 均升序排列，双指针从两端选取，每次比较 \(|a[i]-b[\text{左}]|\) 与 \(|a[i]-b[\text{右}]|\)，取较大者。
3. AT abc223_c - 导火索相遇
两根导火索长度 \(A\)、\(B\)，燃烧速度 \(a\)、\(b\)，从两端同时点燃，求相遇点距左端距离。考点：物理模拟。解法：计算燃烧时间 \(t_A = A/a,\; t_B = B/b\)，相遇位置在 \(\min(t_A, t_B) \times a\) 处。
4. CF 1399C - 体重配对最多对数
\(n\) 个人两两配对使得所有配对体重之和相等，求最多对数。考点：枚举目标和 + 贪心。解法：枚举目标和 \(s \in [2, 200]\)，统计满足 \(w_i + w_j = s\) 的配对数（每元素最多用一次），取最大值。
动态规划 (DP)¶
5. AT dp_c - 三天活动选择
\(N\) 天每天三种活动，相邻天不能相同，求最大快乐值。考点：线性 DP。解法：\(dp[i][j] = \max_{k \ne j}(dp[i-1][k]) + h[i][j]\)。
6. AT dp_e - 01背包变体（价值维度）
\(N\) 个物品，背包容量 \(W\)，价值总和 \(\le 10^3\)，求最大价值。考点：价值作为状态维度的背包。解法：令 \(dp[j]\) = 达到价值 \(j\) 的最小重量，答案为最大的 \(j\) 满足 \(dp[j] \le W\)。
7. AT dp_g - DAG最长路径
给定 DAG 求最长路径（边数）。考点：拓扑排序 + DAG 上 DP。解法：拓扑排序后按序处理，\(dp[v] = \max(dp[v],\; dp[u]+1)\)。
8. CF 455A - 取数游戏
每次选数 \(x\) 加入总分，选后不可选 \(x\pm 1\)，求最大总分。考点：值域 DP（打家劫舍）。解法：统计每值贡献 \(cnt[v] \times v\)，\(dp[i] = \max(dp[i-1],\; dp[i-2] + cnt[i] \times i)\)。
9. AT dp_h - 网格路径计数（有障碍物）
\(H \times W\) 网格有障碍物，从左上到右下求路径数。考点：二维 DP。解法：障碍处 \(dp=0\)，否则 \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)（取模）。
图论 (Graph)¶
10. AT abc361_d - 交换空位到达目标
初始串和目标串含两个空位，每次交换相邻字符与空位，求最少步数。考点：BFS 状态搜索。解法：序列化整个字符串为状态，BFS 搜索最少步数，哈希集合判重。
11. AT abc204_c - 有向图可达对数
\(N\) 节点 \(M\) 边有向图，计算满足从 \(u\) 可达 \(v\) 的有序点对数。考点：对每个节点 BFS/DFS。解法：对每个节点做 BFS 统计可达数并累加，\(O(N(N+M))\)。
12. CF 2000E - 网格放置方块
\(n \times m\) 网格每格有权值，放 \(k\) 个 \(1\times 1\) 方块使权值和最大。考点：排序 + 贪心。解法：所有格子按权值降序排列，选前 \(k\) 个放置。
二分 (Binary Search)¶
13. AT abc373_d - 约束确定节点值
\(N\) 节点 \(M\) 边的图，每条边给出两节点值之差，求所有节点值。考点：图上 BFS 确定相对值。解法：从已知节点出发 BFS，根据差值关系推导其他节点值，类似带权并查集。
14. CF 1201C - 中位数最大化
数组可做最多 \(k\) 次加1操作，求中位数最大值。考点：二分答案 + 贪心验证。解法：二分目标值 \(m\)，检查后半部分提升到 \(m\) 所需操作数是否 \(\le k\)。
数据结构 (Data Structures)¶
15. AT abc330_d - 网格标记计数
\(N \times N\) 网格中有若干标记（o），求有多少格子满足其所在行和列都至少有一个标记。考点：行列统计。解法：设标记所在行数为 \(R\)、列数为 \(C\)，答案为 \(R \times C\)。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
vector<string> g(n);
vector<bool> hasRow(n, false), hasCol(n, false);
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < n; j++)
if(g[i][j] == 'o'){
hasRow[i] = true; // 标记第i行有'o'
hasCol[j] = true; // 标记第j列有'o'
}
}
// 统计有标记的行数和列数
long long R = 0, C = 0;
for(int i = 0; i < n; i++){
if(hasRow[i]) R++;
if(hasCol[i]) C++;
}
// 每对(有标记行,有标记列)的交叉点都满足条件
cout << R * C << "\n";
return 0;
}
关键洞察
满足条件的格子 \((i,j)\) 等价于「\(i\) 所在行有标记 且 \(j\) 所在列有标记」，无需枚举每个格子，答案为 \(R \times C\)。
16. CF 706C - 字符串翻转最小代价
\(n\) 个字符串每个可翻转（代价 \(c_i\)），要求字典序不递减，求最小总代价。考点：DP + 字符串比较。解法：\(dp[i][0/1]\) 表示第 \(i\) 个字符串不翻转/翻转时的最小代价，转移时检查字典序约束。
字符串 (String)¶
17. AT abc284_e - 简单路径计数
无向图中从节点1出发的不同简单路径数（不超过 \(10^6\) 时输出精确值）。考点：DFS 回溯 + 剪枝。解法：DFS 维护已访问集合，每到新节点答案加1，达 \(10^6\) 时提前终止。
18. CF 1294D - 在线mex查询
每次添加数 \(x\)，查询当前集合的 \(\text{mex}\) 对 \(x\) 取模。考点：mex 维护。解法：维护当前 \(\text{mex}\)，每次添加元素后递增直到找到空位。
数论 (Number Theory)¶
19. AT abc334_d - 驯鹿分配方案
\(Q\) 次查询，每次给定 \(r\)，问前 \(r\) 个驯鹿的最小分配方案数。考点：前缀和 + 二分。解法：驯鹿重量排序后求前缀和，查询时二分找到满足条件的位置。
20. CF 1542C - gcd与lcm之和
求 \(\sum_{i=1}^{n} \gcd(i,\; \text{lcm}(1,2,\ldots,n))\)。考点：数论性质。解法：由于 \(\text{lcm}(1,\ldots,n)\) 是 \(1 \sim n\) 的公倍数，对任意 \(i \le n\) 有 \(i \mid \text{lcm}\)，因此 \(\gcd(i, \text{lcm}) = i\)，答案为 \(\frac{n(n+1)}{2}\)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
int main(){
int t; cin >> t;
while(t--){
ll n; cin >> n;
// 对任意 i <= n：i | lcm(1..n)，故 gcd(i, lcm) = i
// 答案 = 1+2+...+n = n*(n+1)/2 (mod MOD)
ll ans = (n % MOD) * ((n + 1) % MOD) % MOD;
ans = ans * ((MOD + 1) / 2) % MOD; // 乘2的模逆元
cout << ans << "\n";
}
return 0;
}
注意
\(\text{lcm}(1,2,\ldots,n)\) 增长极快，直接计算不可行。关键观察：\(i \le n \Rightarrow i \mid \text{lcm}(1,\ldots,n)\)，从而 \(\gcd(i, \text{lcm}) = i\)，答案即 \(\frac{n(n+1)}{2}\)。
树 (Tree)¶
21. AT abc148_f - 树上追击
树上两人从 \(u,v\) 出发，高桥先走，青木每步追击，求高桥能离青木的最远距离。考点：BFS + 树的性质。解法：从 \(v\) 做 BFS 求每个节点到 \(v\) 的距离 \(d_v\)，高桥走到满足「走的步数 \(< d_v\)」的最远节点，答案为满足条件的最大 \(d_v - 1\)。
22. AT abc340_d - 宝箱选择最短时间
\(N\) 个宝箱，每个可直接获得（耗时 \(A_i\)）或花 \(B_i\) 时间跳到第 \(C_i\) 个宝箱，求最短时间。考点：Dijkstra 建模。解法：宝箱为节点，\(A_i\) 走向 \(i+1\)，\(B_i\) 走向 \(C_i\)，Dijkstra 求 \(1 \to N+1\) 最短路。
搜索 (Search)¶
23. AT abc184_d - 硬币期望操作次数
三枚硬币初值 \(a,b,c\)，每次等概率随机选一枚加1（不超过100），某枚到100时停止，求期望操作次数。考点：记忆化搜索 / 期望 DP。
建议解法：设 \(dp[a][b][c]\) 为当前状态的期望剩余操作次数，边界 \(dp=0\)（任一值为100时），转移为 \(dp[a][b][c] = 1 + \frac{\sum dp[\text{后继}]}{cnt}\)。
#include <bits/stdc++.h>
using namespace std;
double dp[101][101][101]; // dp[a][b][c]: 期望剩余操作次数
bool vis[101][101][101];
double solve(int a, int b, int c){
if(a == 100 || b == 100 || c == 100) return 0.0; // 终止态
if(vis[a][b][c]) return dp[a][b][c];
vis[a][b][c] = true;
double res = 0.0;
int cnt = 0;
if(a < 100){ res += solve(a+1, b, c); cnt++; } // 选第一枚+1
if(b < 100){ res += solve(a, b+1, c); cnt++; } // 选第二枚+1
if(c < 100){ res += solve(a, b, c+1); cnt++; } // 选第三枚+1
dp[a][b][c] = 1.0 + res / cnt; // 当前1步 + 后续期望均值
return dp[a][b][c];
}
int main(){
int a, b, c; cin >> a >> b >> c;
memset(vis, false, sizeof(vis));
cout << fixed << setprecision(10) << solve(a, b, c) << "\n";
return 0;
}
期望DP要点
期望 DP 核心在于逆推：从终止状态向前递推。当前状态期望 = 1（本次操作）+ 后续期望的加权平均。记忆化搜索避免重复计算，总状态数仅 \(100^3\)。
练习建议
- 贪心题重点训练直觉，先想清楚局部最优为何能推出全局最优。
- DP 题注意状态定义的合理性，先确定"选什么"和"怎么转移"。
- 图论与树题需要熟练掌握 BFS/DFS/Dijkstra 等基本算法的模板。
- 数论题注重公式推导能力，多积累常见结论（如本节的 lcm 性质）。
- 建议每道题先独立思考 15 分钟，想不出来再看解法，看完后务必自己手写实现。