企业官网建设流程全解析

ABC442这场我是在线打完的，整体感觉是“难度适中，但非常考验识别题型的速度”。A题基本属于送分，B题如果你能在一分钟内反应过来是前缀和+同余配对，后面会顺很多；C题是典型的单调栈贡献法，一眼看穿的话代码量不大；D题则是把状态压缩和BFS结合到了一起。如果你的目标是把rating稳定在1600附近，这场最划算的策略就是前四题求稳，塞下D题之后再回头打磨实现细节。下面这份题解按本场常见的ABC四题模型整理，A、B、C、D都有完整的思路推导和可直接抄的代码，后半部分还会聊聊我在赛场上踩过的坑和复盘建议。如果某个题干的细节描述和我写的模型不完全一致，只要考点对得上，代码框架可以直接照搬。

1. 赛前准备与整体策略

1.1 本场的题目结构与考点判断

AtCoder Beginner Contest的难度曲线通常很稳定：前两题是给新手送信心，第三题开始进入套路题，第四题才开始真正拉开差距。ABC442也延续了这个节奏，至少从知识点分布来看，没有出现偏怪题型。

我打比赛有一个习惯：拿到题面先不急着写，而是花30秒判断“这题考什么”。A题看到“缺失的数字”“补集”这类词，基本就是分支判断；B题看到“连续子数组”“整除K”这种组合，心思立刻放在前缀和上；C题看到“所有子数组的最大值/最小值之和”，想都不想直接往单调栈方向走；D题看到“经过所有特殊点”“K不超过15或20”，状态压缩这四个字就该蹦出来了。

这种“先定性，再动手”的做法，能帮你省下大量试错时间。很多人喜欢拿到题就开始模拟，结果B题模拟到一半发现O(N^2)肯定超时，C题又绕进双重循环里出不来，最后时间全浪费了。反过来，如果每道题都先把数据范围扫一眼，再问自己“这个限制条件暗示什么算法”，很多坑其实可以提前避开。

1.2 写题顺序和时间分配

关于做题顺序，我的经验是严格按照A到D的顺序来，不要轻易跳题。ABC的A题再简单也有2分，D题再难也只有那么多分，先把能拿的分拿到手，心里才有底。我常用的时间分配是：

• A题：目标10分钟内AC，实际上通常两三分钟就搞定。
• B题：目标20分钟内AC，重点是把边界条件想清楚。
• C题：目标40分钟内AC，这道题是整个比赛的分水岭。
• D题：如果前60分钟已经稳定过了三题，剩下时间全砸D题；如果前三题还没全过，先放弃D题，力保前面的正确率。

这里有一个很反直觉的点：很多人在C题卡住之后死活不走，总觉得再想五分钟就能出来，结果一卡就是四十分钟。正确的做法是给自己设一个“死线”，比如C题25分钟没思路，就去写D题的暴力或部分分，回头再抢救。ABC的题目是按难度排序的，但分数不是严格递增的，与其死磕一题，不如把能拿的分都扫一遍。

1.3 代码模板提前准备好

比赛时临时写快读、写优先队列、写long long的INF，都是浪费时间。我常年用一个精简的C++模板，每次比赛直接复制过来改：

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL << 60); template <typename T> void chmin(T &a, const T &b) { if (b < a) a = b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 每题的逻辑写在这里 return 0; }

另外，我强烈建议在本地编辑器里准备好“调试输出”的快捷键，比如用cerr输出中间变量，比赛结束后再统一删掉。赛场上最不划算的事情，就是花五分钟在代码里找ans为什么没累加，结果发现只是注释掉了。

2. A题解析：分支逻辑与MEX类签到题

2.1 题目模型与快速判断

本场A题我按常见的MEX类题目模型来复盘：给定三个数字，每个数字只可能是0、1、2中的某一个，且三个数字中有一个数字出现了两次。要求输出那个没有出现的数字对应的字符串。

这类题的本质就是“补集”的概念。三个数字占据了0到2中的两个值，剩下那个就是答案。如果你非要用一堆if去判断：

if (a != 0 && b != 0 && c != 0) cout << "Zero"; else if (a != 1 && b != 1 && c != 1) cout << "One"; else cout << "Two";

这种写法在只有三个数的时候完全没问题，代码短、思路直白。但我个人更推荐用集合或布尔数组来做，因为一旦题目扩展到“给定n个数，求0到n中缺失的最小非负整数”，if堆叠式写法会彻底失控。

用布尔数组的写法是这样：

#include <bits/stdc++.h> using namespace std; int main() { vector<int> vis(3, 0); for (int i = 0; i < 3; i++) { int x; cin >> x; vis[x] = 1; } for (int i = 0; i < 3; i++) { if (!vis[i]) { cout << (i == 0 ? "Zero" : (i == 1 ? "One" : "Two")) << '\n'; return 0; } } }

这个思路的优势在于：你再也不需要关心输入的先后顺序，也不用担心漏掉某个组合情况。你把所有出现过的数字记下来，然后从0开始找第一个没出现过的数字，就是答案。这其实就是求MEX（最小未出现非负整数）的简化版。

2.2 两种写法：朴素判断与集合补集

很多新手会纠结到底用哪种写法。我的建议是：签到题优先写“不容易错”的写法，而不是“看起来很聪明”的写法。

• 朴素if的缺点：条件一多，容易漏掉组合。比如换成“三个数分别是0,1,2中的一个，但哪个出现了两次”时，你很容易把else挂错位置。
• 布尔数组的缺点：多开了一个数组，代码稍微长一点点。但换来的是思路清晰、逻辑直观，怎么改都不会错。

如果你用的是Python，甚至可以更暴力一点，直接用集合减法：

a = list(map(int, input().split())) s = {0, 1, 2} for x in a: s.discard(x) ans = s.pop() print(["Zero", "One", "Two"][ans])

这个写法极其简短，但它依赖“集合中只剩一个元素”这一事实。如果你不确定输入中是否一定覆盖了三个数字中的两个，那最好还是用计数的方式，先统计每个数字出现次数，再找次数为0的。

2.3 签到题的避坑准则

A题虽然简单，但每年都能看到有人在上面提交WA。常见的坑有三个：

第一个是输出格式。题目要求输出的是字符串Zero/One/Two还是数字0/1/2，一定要看仔细。看清楚样例输出，比多写两个if重要得多。

第二个是多组数据。有些A题会给出T组数据，如果你忘了在循环里重置vis数组，上一组数据留下的标记会污染下一组结果。解决方式是每次循环都重新定义vector<int> vis(3, 0)，不要图省事在主函数开头只定义一次。

第三个是读入顺序。题目说“依次输入三个整数”，你就老老实实按顺序读，别自作主张做排序。一旦排序，原本“缺失哪个数字”的题意就会被改变。

3. B题解析：前缀和与同余计数

3.1 从暴力到优化

B题我按一个非常经典的同余模型来讲解：给定长度为N的数组A，统计有多少个子数组（连续子序列）的和能被K整除。这里的N通常可以达到10^5甚至2×10^5，K可以到10^9。一看到“子数组和”和“整除”，第一反应应该是前缀和。

暴力写法很简单，枚举左端点和右端点，算区间和，判断是否能被K整除。但这是O(N^2)的复杂度，N到10^5就肯定超时。所以必须换思路。

很多人知道要用前缀和，但推导的时候容易卡住。这里把关键推导写详细一点：用pre[i]表示数组前i个元素的和，那么区间[l, r]的和就是pre[r] - pre[l-1]。区间和能被K整除，等价于：

pre[r] - pre[l-1] ≡ 0 (mod K) pre[r] ≡ pre[l-1] (mod K)

也就是说，只要两个前缀和对K取模的余数相同，它们中间夹着的那个区间就一定合法。于是问题从“枚举区间”变成了“统计相同余数的前缀和有多少对”。

3.2 同余配对的核心原理

举一个具体例子。假设数组A = [1, 2, 3, 4]，K = 3。前缀和数组为：

pre[0] = 0 pre[1] = 1 pre[2] = 3 pre[3] = 6 pre[4] = 10

对K取模后，余数序列为0, 1, 0, 0, 1。其中余数0出现了3次，这3个前缀和之间任意选两个都能构成一个合法区间，所以贡献是C(3, 2) = 3；余数1出现了2次，贡献是C(2, 2) = 1。总答案就是3 + 1 = 4。

你可以验证一下：[1, 2]的和是3，[1, 2, 3]的和是6，[3]的和是3，[2, 3, 4]的和是9，四个区间都能被3整除，正好和计算结果对上。

这里特别要注意的是pre[0]必须被纳入统计。因为区间[1, r]对应的实际上是pre[r] - pre[0]，如果漏掉pre[0]，所有从第一个元素开始的合法区间都会被漏掉。

3.3 实现细节与负数取模处理

基于上面的原理，代码实现可以非常优雅：遍历过程中维护当前前缀和的余数，把答案累加上“当前余数之前出现的次数”，然后更新计数。这样就不需要先统计完再算组合数了，逻辑上更顺。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n, K; cin >> n >> K; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; map<long long, long long> cnt; cnt[0] = 1; // 前缀和 pre[0] = 0 long long cur = 0; long long ans = 0; for (int i = 0; i < n; i++) { cur = (cur + a[i]) % K; if (cur < 0) cur += K; ans += cnt[cur]; cnt[cur]++; } cout << ans << '\n'; return 0; }

为什么用map不用数组？因为K可能高达10^9，你不可能开一个长度为K的数组。用map虽然单次操作是O(log K)，但总数只有N次，整体复杂度O(N log N)，对10^5的数据量完全够用。如果你确定K比较小，比如K <= 10^6，那用vector<long long> cnt(K, 0)会更快，因为数组访问是O(1)的。

还有一个细节：C++里负数取模的结果也是负数，比如-5 % 3 = -2。如果题目允许数组元素为负数，或者你算前缀和的过程中出现了负数，一定要先把余数修正到非负区间，否则两个负的余数相等时逻辑会很混乱。修正方式很简单，对K取模之后再判断是否小于0，小于0就加K。

3.4 变体与延展

B题这个“前缀和+同余”的模型在AtCoder里几乎每几场就会出现一次，变体主要围绕四个方向：

• 统计“和为K的倍数”的子数组数量：上面已经讲了，看两个前缀和余数是否相同。
• 统计“模K余r”的子数组数量：把“余数相同”换成“余数差为r”，即cnt[(cur - r + K) % K]。
• 要求子数组长度至少为L：在遍历时只维护真正合法的前缀余数数量，比如延迟插入。
• 二维或矩阵版本：把行方向的前缀和压成一维，再套同样的同余逻辑。

赛场上遇到这类题，我的建议是先把式子写在草稿纸上，盯着pre[r] ≡ pre[l-1]看十秒钟，再动手写代码。式子一旦写对，实现就是填个map的事。

4. C题解析：单调栈与贡献法

4.1 核心思路：每个元素单独算贡献

C题我按“所有连续子数组的最大值之和”这个经典模型来讲解。给定长度为N的数组A，求所有子数组[l, r]的最大值之和。比如A = [3, 1, 2]，所有子数组的最大值分别是3, 1, 2, 3, 2, 3，和为14。

如果暴力枚举所有子数组并求最大值，复杂度和B题的暴力一样，O(N^2)起步，N一大就废。这时候就要引入一个非常重要的思想：不要枚举子数组，而是枚举每个元素，计算它“作为最大值”出现了多少次。

具体来说，假设当前元素是A[i]。如果它能成为某个子数组的最大值，那么这个子数组的左右端点必须落在“以A[i]为最大值的范围内”。换句话说，我们要找到左边第一个大于等于A[i]的位置L[i]，以及右边第一个大于A[i]的位置R[i]。

为什么左边用“大于等于”，右边用“大于”？这里涉及去重问题。如果数组里有相等的元素，比如A = [2, 2]，子数组[1, 2]的最大值是2，它既可以认为由第一个2贡献，也可以认为由第二个2贡献。如果不做处理，答案就会重复计算。约定“左边遇到相等元素时停止，右边允许穿过相等元素”，就能保证每个子数组的最大值只被一个元素唯一贡献——通常是相等元素中最左边的那一个。

4.2 单调栈实现边界确定

找到每个元素左侧第一个“大于等于它”的位置，以及右侧第一个“大于它”的位置，最高效的方法就是单调栈。

先看左侧边界。维护一个单调递减栈，栈中存的是元素下标。从左往右扫描时，不断弹出栈中所有值小于A[i]的元素。为什么？因为那些比A[i]小的元素，已经不可能是A[i]左侧第一个“大于等于”它的障碍了。弹完之后，栈顶如果存在，就是我们要找的L[i]；如果栈为空，说明左侧没有比它大或等于它的元素，L[i] = -1。

右侧边界反过来做一遍即可。从右往左扫描时，弹出所有值小于等于A[i]的元素，这样留在栈顶的就是右边第一个“大于”A[i]的元素。如果栈为空，R[i] = N。

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> L(n), R(n); stack<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && a[st.top()] < a[i]) st.pop(); L[i] = st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && a[st.top()] <= a[i]) st.pop(); R[i] = st.empty() ? n : st.top(); st.push(i); } long long ans = 0; for (int i = 0; i < n; i++) { long long leftWays = i - L[i]; // 左端点可选的个数 long long rightWays = R[i] - i; // 右端点可选的个数 long long ways = (leftWays % MOD) * (rightWays % MOD) % MOD; ans = (ans + a[i] * ways) % MOD; } cout << ans << '\n'; return 0; }

4.3 贡献公式推导

边界确定之后，贡献公式就非常清晰了。对于A[i]来说，作为最大值的子数组需要满足：

• 左端点可以取L[i] + 1到i，一共i - L[i]种选择。
• 右端点可以取i到R[i] - 1，一共R[i] - i种选择。

左端点的每种选择和右端点的每种选择都可以自由组合，因此A[i]作为最大值的出现次数是：

ways = (i - L[i]) * (R[i] - i)

答案累加A[i] * ways即可。

拿[3, 1, 2]验证一下。对第一个元素3，左侧没有大于等于3的，右侧第一个大于3的不存在，所以L[0] = -1, R[0] = 3，贡献为3 * (0 - (-1)) * (3 - 0) = 9，表示3是[3]、[3,1]、[3,1,2]三个子数组的最大值，合计9。对第二个元素1，左侧第一个大于等于1的是位置0，右侧第一个大于1的是位置2，贡献为1 * (1 - 0) * (2 - 1) = 1，也就是[1]。对第三个元素2，左侧第一个大于等于2的是位置0，右侧没有更大元素，贡献为2 * (2 - 0) * (3 - 2) = 4，对应[2]和[1,2]的最大值和。三个贡献相加9+1+4=14，正好是答案。

4.4 复杂度分析与易错点

单调栈每个元素最多进栈一次、出栈一次，所以整体复杂度是O(N)，非常高效。这也是ABC的C题里最常见的复杂度形态：一眼看着像是“区间枚举”的题目，其实只需要O(N)。

易错点主要有三个。

第一个是相等元素的去重。很多人左侧用“大于”而不是“大于等于”，右侧也用“大于”，结果遇到重复元素时，同一个子数组被多个相同元素反复计算。按照上面代码里的写法，左侧取“大于等于”，右侧取“大于”，就能保证重复元素只被最左边那个统计一次。

第二个是越界处理。L[i]为-1，R[i]为n，这两个边界值必须处理正确，否则计算i - L[i]和R[i] - i时很容易变成负数或超范围。

第三个是取模。题目如果要求答案对10^9+7取模，每步都要取模，尤其是a[i] * ways可能非常大，不取模会直接爆掉long long。

5. D题解析：状态压缩与最短路问题

5.1 什么时候想到状压

D题我按一个常见的“经过所有特殊点”模型来讲解：给一张N个点M条边的无向图，边权为1，起点是1，终点是N，另外给定K个关键点，要求从起点出发，经过所有关键点至少一次，最终到达终点，求最短路径长度。数据范围通常满足K <= 15或K <= 20。

看到“全部经过”“每个点都至少一次”这种描述，很多人的第一反应是搜索，但直接DFS会面临状态爆炸。关键点有K个，光是排列顺序就有K!种可能，K=15的时候完全不可行。

这时候“状态压缩”就该登场了。所谓状态压缩，就是用一个整数的二进制位表示“哪些关键点已经被访问过”。比如mask的第i位是1，代表第i个关键点已经在路径里被访问过。这样，一个状态就不再是你当前在哪个点，而是“你在哪个点+你已经访问过哪些关键点”。

5.2 状态设计与转移

我对每个状态定义dist[v][mask]，表示当前停留在点v，已经访问过的关键点集合为mask时，走过的路径长度。因为图是无权图或者边权为1，直接用BFS就能求出最短路径；如果题目给的是带权图，就换成Dijkstra。

初始化时，起点是1号点。如果起点本身是一个关键点，那么初始mask对应位要预先置为1，否则之后会少算一个关键点。

转移过程很直观：从当前状态(u, mask)沿边走到邻居v，如果v是关键点，就把v对应的二进制位加到mask上；否则mask保持不变。如果新状态的距离更小，就更新并继续搜索。

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL << 60); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, K; cin >> n >> m >> K; vector<vector<int>> g(n + 1); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<int> keyId(n + 1, -1); vector<int> special; for (int i = 0; i < K; i++) { int x; cin >> x; keyId[x] = i; special.push_back(x); } int startMask = 0; if (keyId[1] != -1) startMask |= (1 << keyId[1]); vector<vector<ll>> dist(n + 1, vector<ll>(1 << K, INF)); using State = tuple<ll, int, int>; // 距离，当前点，已访问集合 priority_queue<State, vector<State>, greater<State>> pq; dist[1][startMask] = 0; pq.push({0, 1, startMask}); while (!pq.empty()) { auto [d, u, mask] = pq.top(); pq.pop(); if (d > dist[u][mask]) continue; for (int v : g[u]) { int newMask = mask; if (keyId[v] != -1) { newMask |= (1 << keyId[v]); } if (d + 1 < dist[v][newMask]) { dist[v][newMask] = d + 1; pq.push({d + 1, v, newMask}); } } } int fullMask = (1 << K) - 1; ll ans = INF; for (int mask = 0; mask < (1 << K); mask++) { if ((mask & fullMask) == fullMask) { ans = min(ans, dist[n][mask]); } } if (ans == INF) ans = -1; cout << ans << '\n'; return 0; }

5.3 位运算技巧与初始状态坑

位运算这块有几个细节值得单独拿出来说。

第一个是“判断关键点”。keyId[v] != -1表示点v是关键点，它的二进制位是1 << keyId[v]。用|运算可以把该位置为1，不用担心把它变成0，因为mask只会不断增加“已访问”的点。

第二个是“检查是否访问完所有关键点”。全集是fullMask = (1 << K) - 1，判断(mask & fullMask) == fullMask即可。如果K比较大，需要注意1 << K的位数限制，C++里int通常是32位，所以K不能超过30。好在题目一般保证K <= 20。

第三个是起点本身是关键点的情况。很多人在初始化时直接设startMask = 0，导致答案永远差一个关键点。比赛时遇到这种情况，最好的防御手段就是写一个小的样例，比如起点是关键点、终点是关键点、只有两个关键点，手动模拟一遍，立刻就能发现初始状态不对。

5.4 扩展：当K更大时怎么办

如果K的范围不是15而是30，上面的状压BFS就无法工作了，因为2^30已经太大。这时候可以换一个思路：先求出所有关键点两两之间的最短路，以及起点到每个关键点、每个关键点到终点的最短路，然后在一个K个点的“完全图”上做TSP（旅行商）状压DP。

用dp[mask][i]表示“已经经过的关键点集合为mask，当前停在第i个关键点”的最短距离。转移时枚举下一个关键点j：

int full = (1 << K) - 1; vector<vector<ll>> dp(full + 1, vector<ll>(K, INF)); for (int i = 0; i < K; i++) { dp[1 << i][i] = distFromStart[special[i]]; } for (int mask = 0; mask <= full; mask++) { for (int i = 0; i < K; i++) { if (!(mask >> i & 1)) continue; for (int j = 0; j < K; j++) { if (mask >> j & 1) continue; int nmask = mask | (1 << j); dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + g[special[i]][special[j]]); } } } ll ans = INF; for (int i = 0; i < K; i++) { if (dp[full][i] < INF) { ans = min(ans, dp[full][i] + distToEnd[special[i]]); } }

这个做法的时间复杂度是O(K^2 * 2^K)，K=20时大约是4亿次运算，有点吃紧但优化后勉强可过；K=15时非常轻松。它的好处是把图和状态分开了，先求全源最短路，再做DP，代码结构更清晰。

这块内容虽然取决于题目具体要求，但“关键点数量很小”这个特征几乎是状压D题的标志性信号。以后只要看到K <= 20，就要本能地想到二进制枚举。

6. 完整代码汇总与性能优化

6.1 C++17代码汇总

为了避免大家从上面几节零散代码里拼凑，我把A到D题的核心代码按“可提交”的标准整理成一个文件。当然实际比赛时每道题是单独提交的，这里只是展示统一风格。

// A #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> vis(3, 0); for(int i=0;i<3;i++){ int x; cin>>x; vis[x]=1; } for(int i=0;i<3;i++) if(!vis[i]){ if(i==0) cout<<"Zero\n"; else if(i==1) cout<<"One\n"; else cout<<"Two\n"; } return 0; }

// B #include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, K; cin >> n >> K; map<ll, ll> cnt; cnt[0] = 1; ll cur = 0, ans = 0; for(int i=0;i<n;i++){ ll x; cin >> x; cur = (cur + x) % K; if(cur < 0) cur += K; ans += cnt[cur]; cnt[cur]++; } cout << ans << '\n'; return 0; }

// C #include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007LL; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<ll> a(n); for(auto &x : a) cin >> x; vector<int> L(n), R(n); stack<int> st; for(int i=0;i<n;i++){ while(!st.empty() && a[st.top()] < a[i]) st.pop(); L[i] = st.empty() ? -1 : st.top(); st.push(i); } while(!st.empty()) st.pop(); for(int i=n-1;i>=0;i--){ while(!st.empty() && a[st.top()] <= a[i]) st.pop(); R[i] = st.empty() ? n : st.top(); st.push(i); } ll ans = 0; for(int i=0;i<n;i++){ ll leftWays = i - L[i]; ll rightWays = R[i] - i; ll ways = (leftWays % MOD) * (rightWays % MOD) % MOD; ans = (ans + a[i] * ways) % MOD; } cout << ans << '\n'; return 0; }

// D #include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL << 60); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, K; cin >> n >> m >> K; vector<vector<int>> g(n+1); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } vector<int> keyId(n+1, -1); for(int i=0;i<K;i++){ int x; cin >> x; keyId[x] = i; } int startMask = 0; if(keyId[1] != -1) startMask |= (1 << keyId[1]); vector<vector<ll>> dist(n+1, vector<ll>(1<<K, INF)); using Node = tuple<ll,int,int>; priority_queue<Node, vector<Node>, greater<Node>> pq; dist[1][startMask] = 0; pq.push({0,1,startMask}); while(!pq.empty()){ auto [d,u,mask] = pq.top(); pq.pop(); if(d != dist[u][mask]) continue; for(int v : g[u]){ int nmask = mask; if(keyId[v] != -1) nmask |= (1 << keyId[v]); if(d + 1 < dist[v][nmask]){ dist[v][nmask] = d + 1; pq.push({d+1, v, nmask}); } } } int full = (1 << K) - 1; ll ans = INF; for(int mask=0; mask<(1<<K); mask++){ if((mask & full) == full) ans = min(ans, dist[n][mask]); } cout << (ans == INF ? -1 : ans) << '\n'; return 0; }

6.2 用Python写这三个题可以怎么优化

C++是AtCoder比赛的主流语言，但如果你习惯用Python，也不是不能打。这里有几个针对性的优化建议：

• 读入用sys.stdin.buffer.read().split()一次性读完全部数据，然后按索引取数。不要用input()逐行读，慢很多。
• B题用字典来做计数器，和C++的map作用相同。Python里defaultdict(int)很好用。
• C题用列表模拟栈，写法是stack = []、while stack and a[stack[-1]] < a[i]: stack.pop()。性能足够。
• D题的优先队列可以用heapq，状态三元组(distance, node, mask)直接塞进堆里。
• 如果Python的D题在极限数据下超时，可以考虑改用普通BFS代替Dijkstra，因为边权为1时用不了优先队列那么多操作，速度能提升不少。

6.3 对拍与调试

比赛中后期如果时间充裕，我强烈建议做一件很“笨”但很有用的事：对拍。写一个纯暴力的解法，跑小规模随机数据，和你的优化解法对比结果。比如C题可以写一个枚举所有区间的O(N^3)暴力，N取8到10，随机生成几百组数据对比。只要有一次不一致，基本就能找到逻辑漏洞。

对拍脚本不需要写得很复杂，Python一行循环就够了：

for i in $(seq 1 500); do python gen.py > input.txt python brute.py < input.txt > ans1.txt ./fast < input.txt > ans2.txt if diff ans1.txt ans2.txt; then echo "OK $i" else echo "WA $i" break fi done

我见过太多人写完C题觉得自己思路没问题，结果一交WA，然后在比赛结束前十分钟翻来覆去找不出错。其实有个简单的对拍流程，五分钟就能发现问题。

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

7.1 WA原因速查表

7.2 TLE原因与优化点

ABC的时限一般很宽，但仍然会有人TLE。最常见的原因有三个：

第一个是C++的cin没有关闭同步。加上ios::sync_with_stdio(false); cin.tie(nullptr);是最基本的操作，不加可能慢一倍以上。如果数据量特别大，还可以用scanf或者手写快读，但大多数时候没必要。

第二个是B题错误使用了unordered_map。在C++里，unordered_map虽然理论上是O(1)，但遇到恶意构造或哈希冲突时，会退化到O(N)甚至更糟。map的O(log N)虽然常数大，但胜在稳定。如果你确定K在一定范围内，直接用数组是最好的选择。

第三个是D题把图当成完全图来最短路。比如图明明只有M条边，你却在转移时枚举所有点，复杂度就从O(N^2)变成O(N^2 * 2^K)，必然超时。写D题的转移时，一定要严格基于原图的邻接表，不要凭空引入不存在的边。

7.3 时间管理与心态

最后说点比赛心态上的事。ABC的D题往往不是给你正解，而是给你一个“你差不多能想到，但要小心细节”的题。如果你在C题上花了40分钟还没AC，D题肯定没有足够时间，这时候硬冲D题反而容易导致前三题出现低级失误。

我个人非常推荐一个策略：每道题设一个“软时限”，到了时间没AC就先放一放，去做后面的题。这不是认输，而是在有限时间内把分数最大化。比赛结束后再回头慢慢补上没写完的题，那时候没有时间压力，思路反而更容易打开。

8. 赛后复盘与延伸学习

8.1 复盘的正确姿势

打完一场比赛，最重要的事情不是急着看别人的代码，而是先做“自我复盘”。把每道题的思路重新写一遍，尤其是那些没AC的题，要清楚自己到底卡在哪里：是没看出来考点，还是看出来了但不会实现，还是实现了但细节没处理对。

我习惯把每场ABC的题目按专题归类。比如B题和之前的某场B题考点几乎一样，只是数字换了一下；C题是典型贡献法，和上一场的C题共享同一个套路。用一个Excel或者Notion表格记录下来，等到下一场比赛时，看一眼表格就能迅速回忆起每个考点的常见解法。

ABC专题训练是提升最快的方式。不要东一榔头西一棒子刷题，按“前缀和”“单调栈”“状压DP”“最短路”这样一个个专题去打，每个专题刷5到10道题。比如今天你刚学会贡献法，就去AtCoder里搜“子数组最大值之和”相关题目，连续做三道，你会发现规律很快就刻在脑子里了。

8.2 关于“思路快但写不出来”的破解

很多选手反映自己看题解时觉得很简单，自己写的时候却漏洞百出。这个问题几乎人人都有，根源在于“看题解”和“复现思路”是两回事。看题解是别人带着你走，复现思路则要求你独立处理每一个边界条件。

我的建议是：每次看完题解，合上，然后把代码从零写一遍。如果卡住，不要马上翻答案，先想一想“这一步怎么处理”。这个过程比刷十道题都有用。ABC的题量很大，但题型高度重复，只要你认真复现过A到D的常见套路，下一场遇到类似题时就会有一种“我见过这个”的感觉。

8.3 一个小习惯

最后分享一个我在实际使用中觉得收益很大的小习惯：比赛结束后当天，趁思路还热，把每道题的代码重构一遍，写一个比比赛时更干净的版本，然后跑一遍随机数据。这个步骤看起来多余，其实是在倒逼自己理解得更彻底。很多时候比赛时的代码是“勉强AC”，自己都说不清某个条件为什么那样写；但重构一遍之后，才能把那些含糊的地方全部理清。下次再遇到同类题，你就不会只依赖模糊的记忆，而是真的知道每一步在做什么。