ABC442这场我是在线打完的整体感觉是“难度适中但非常考验识别题型的速度”。A题基本属于送分B题如果你能在一分钟内反应过来是前缀和同余配对后面会顺很多C题是典型的单调栈贡献法一眼看穿的话代码量不大D题则是把状态压缩和BFS结合到了一起。如果你的目标是把rating稳定在1600附近这场最划算的策略就是前四题求稳塞下D题之后再回头打磨实现细节。下面这份题解按本场常见的ABC四题模型整理A、B、C、D都有完整的思路推导和可直接抄的代码后半部分还会聊聊我在赛场上踩过的坑和复盘建议。如果某个题干的细节描述和我写的模型不完全一致只要考点对得上代码框架可以直接照搬。1. 赛前准备与整体策略1.1 本场的题目结构与考点判断AtCoder Beginner Contest的难度曲线通常很稳定前两题是给新手送信心第三题开始进入套路题第四题才开始真正拉开差距。ABC442也延续了这个节奏至少从知识点分布来看没有出现偏怪题型。题号考点类型大致难度建议用时A题分支逻辑/集合补集灰题2-3分钟B题前缀和同余计数茶题8-12分钟C题单调栈贡献法绿题20-30分钟D题状态压缩BFS/Dijkstra水色题30-45分钟我打比赛有一个习惯拿到题面先不急着写而是花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() { vectorint 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数组上一组数据留下的标记会污染下一组结果。解决方式是每次循环都重新定义vectorint vis(3, 0)不要图省事在主函数开头只定义一次。第三个是读入顺序。题目说“依次输入三个整数”你就老老实实按顺序读别自作主张做排序。一旦排序原本“缺失哪个数字”的题意就会被改变。3. B题解析前缀和与同余计数3.1 从暴力到优化B题我按一个非常经典的同余模型来讲解给定长度为N的数组A统计有多少个子数组连续子序列的和能被K整除。这里的N通常可以达到10^5甚至2×10^5K可以到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; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; maplong 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那用vectorlong 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; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; vectorint L(n), R(n); stackint 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]的最大值和。三个贡献相加91414正好是答案。4.4 复杂度分析与易错点单调栈每个元素最多进栈一次、出栈一次所以整体复杂度是O(N)非常高效。这也是ABC的C题里最常见的复杂度形态一眼看着像是“区间枚举”的题目其实只需要O(N)。易错点主要有三个。第一个是相等元素的去重。很多人左侧用“大于”而不是“大于等于”右侧也用“大于”结果遇到重复元素时同一个子数组被多个相同元素反复计算。按照上面代码里的写法左侧取“大于等于”右侧取“大于”就能保证重复元素只被最左边那个统计一次。第二个是越界处理。L[i]为-1R[i]为n这两个边界值必须处理正确否则计算i - L[i]和R[i] - i时很容易变成负数或超范围。第三个是取模。题目如果要求答案对10^97取模每步都要取模尤其是a[i] * ways可能非常大不取模会直接爆掉long long。5. D题解析状态压缩与最短路问题5.1 什么时候想到状压D题我按一个常见的“经过所有特殊点”模型来讲解给一张N个点M条边的无向图边权为1起点是1终点是N另外给定K个关键点要求从起点出发经过所有关键点至少一次最终到达终点求最短路径长度。数据范围通常满足K 15或K 20。看到“全部经过”“每个点都至少一次”这种描述很多人的第一反应是搜索但直接DFS会面临状态爆炸。关键点有K个光是排列顺序就有K!种可能K15的时候完全不可行。这时候“状态压缩”就该登场了。所谓状态压缩就是用一个整数的二进制位表示“哪些关键点已经被访问过”。比如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; vectorvectorint 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); } vectorint keyId(n 1, -1); vectorint 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]); vectorvectorll dist(n 1, vectorll(1 K, INF)); using State tuplell, int, int; // 距离当前点已访问集合 priority_queueState, vectorState, greaterState 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个关键点”的最短距离。转移时枚举下一个关键点jint full (1 K) - 1; vectorvectorll dp(full 1, vectorll(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)K20时大约是4亿次运算有点吃紧但优化后勉强可过K15时非常轻松。它的好处是把图和状态分开了先求全源最短路再做DP代码结构更清晰。这块内容虽然取决于题目具体要求但“关键点数量很小”这个特征几乎是状压D题的标志性信号。以后只要看到K 20就要本能地想到二进制枚举。6. 完整代码汇总与性能优化6.1 C17代码汇总为了避免大家从上面几节零散代码里拼凑我把A到D题的核心代码按“可提交”的标准整理成一个文件。当然实际比赛时每道题是单独提交的这里只是展示统一风格。// A #include bits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vectorint vis(3, 0); for(int i0;i3;i){ int x; cinx; vis[x]1; } for(int i0;i3;i) if(!vis[i]){ if(i0) coutZero\n; else if(i1) coutOne\n; else coutTwo\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; mapll, ll cnt; cnt[0] 1; ll cur 0, ans 0; for(int i0;in;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; vectorll a(n); for(auto x : a) cin x; vectorint L(n), R(n); stackint st; for(int i0;in;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 in-1;i0;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 i0;in;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; vectorvectorint g(n1); for(int i0;im;i){ int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } vectorint keyId(n1, -1); for(int i0;iK;i){ int x; cin x; keyId[x] i; } int startMask 0; if(keyId[1] ! -1) startMask | (1 keyId[1]); vectorvectorll dist(n1, vectorll(1K, INF)); using Node tuplell,int,int; priority_queueNode, vectorNode, greaterNode 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({d1, v, nmask}); } } } int full (1 K) - 1; ll ans INF; for(int mask0; mask(1K); 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原因速查表题号常见错误原因排查方向A输出字符串和数字搞混没看样例先看样例再写输出A多组数据时vis数组未清空初始化位置错误每组数据重新定义B答案偏少漏了pre[0]检查cnt[0]是否初始化为1B负数元素导致余数错误没有处理负数取模取模后判断是否需要加KC答案重复相等元素去重没做对左侧取右侧取或反过来C越界导致乘法变负数L或R边界出错检查L和R的初始值D答案永远差一个关键点起点是关键点但未初始化mask检查startMaskD内存超限dist开成[n][1K]但K偏大检查K的范围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分钟还没ACD题肯定没有足够时间这时候硬冲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”自己都说不清某个条件为什么那样写但重构一遍之后才能把那些含糊的地方全部理清。下次再遇到同类题你就不会只依赖模糊的记忆而是真的知道每一步在做什么。