打ABCAtCoder Beginner Contest这几年下来我最大的一个感受是真正决定新手能不能从“会写代码”跨到“会解算法题”的往往是C题。A题和B题基本是语法题只要你会写循环和条件判断慢慢磨总能过可一到C题题面突然变得“有想法”了你不能再靠暴力莽得开始考虑复杂度得开始分析问题结构。我见过太多人卡在C题上rating死活上不去不是不努力而是刷题方式不对一直在舒适区里打转。这篇内容想和大家认真聊聊ABC的C题。我会从题目定位、高频考点、真题拆解、常见坑点四个方向把C题讲透最后给一份从C题向D题进阶的训练思路。不管你现在是刚过B题的小白还是已经在C题边缘疯狂试探的选手这篇都应该能帮你把思路捋顺。整理这段内容时我翻了自己过去几十场ABC的做题记录踩过的坑、调过的错、拍过桌子的瞬间都在里面了希望对你有用。1. ABC与C题为什么C题是竞技入门的第一道分水岭1.1 ABC的题目结构每道题都在筛选什么ABC一共7题A到G最近的比赛是A到Ex难度曲线拉得非常明显。用我自己的体感来分一下A/B题纯语法题。考的是你能不能把题面翻译成代码。哪怕没学过算法也能凭感觉写出来。C题思维题。开始涉及一些基础算法思想但通常不考特别复杂的模板关键是想得到那个“最优策略”。D题综合题。往往需要你在C题的基础上再叠加一层结构比如排序加二分、图上的BFS之类。E题及以上区分度题。从这里开始就是真正的算法硬实力了线段树、动态规划优化、数学构造都会冒出来。这个结构不是随便设计的。AtCoder官方把ABC定位成“让更多人可以参加的入门比赛”所以A、B题要足够友好让零基础选手也有体验感而C题则承担了“筛选”功能——它要测出哪些人能进一步往上走。这也是为什么很多人卡在C题。它正好卡在“你学过基础知识”和“你能灵活运用知识”之间的那个位置上。你背过二分模板不叫会二分你能在C题的题面里看出来这题可以用二分才叫会。1.2 从B题到C题复杂度意识觉醒的关键时刻做B题的时候N的取值范围经常是10^3甚至10^4。这种数据范围意味着——你随便写个O(N^2)的二重循环甚至在Python里都能跑过去。但到了C题N直接跳到2×10^5O(N^2)就是将近400亿次运算在AtCoder的2秒时限下绝对不可能过。我第一次感受到这个差距是在某个ABC的C题一上来写了双重循环样例全部通过心里美滋滋点了提交然后看着那片TLE愣了半天说不出话。从那以后我养成了一个习惯看题第一件事不是读题面而是先看数据范围。这不是技巧这是纪律。C题就是逼你完成这个思维转变的地方从“跑得通”转向“跑得完”。当N2×10^5时你的算法复杂度必须控制在O(N log N)以内也就是说你的思考方向必须是二分、排序、贪心、前缀和、双指针这类线性或近线性的办法。这是C题最难的地方也是它最值钱的地方。你一旦在这个阶段养成了“看到数据范围先估算复杂度”的习惯后面的D题、E题都会走得顺畅很多。1.3 为什么说C题完全值得开一个“题解汇总”专题ABC现在是每周六晚上一场一年下来就是50多场。每场3道C题一年就是150多道。这么高频的内容如果不做整理等于打完就忘完全没有积累。我自己在准备这篇“题解汇总”的时候翻了近20场ABC的C题明显能感觉到出题人的套路有规律考来考去就是那几类题型变着花样出。所以与其每场打完就丢一边不如你自己也建一个“ABC C题笔记”记录每一道题的题面核心、算法标签、易错点。这件事坚持半年你的C题通过率绝对会肉眼可见地上升。这篇博文里的内容就是我这几年笔记精华的一部分把它分享出来想让还在C题挣扎的朋友少走点弯路。2. C题高频考点翻来覆去就考这些套路打多了ABC你会发现C题的出题范围其实非常固定。前面提到的“排序贪心”“二分答案”“前缀和差分”是三大常客另外数学构造、简单图论也时有出现。我把自己近50场ABC的C题考点做了个粗略统计下面这个表格可以说相当有参考价值算法/思想方向出现频率典型特征我给的优先级排序贪心极高题面要求“最大化/最小化某个值”需要你找一种安排顺序★★★★★二分答案高“求最大/最小可能值”且判断可行性比求最优值容易★★★★★前缀和/差分高区间加、区间查询、多次操作后求结果★★★★★组合计数/取模中高求方案数、排列数结果要求对1e97取模★★★★图论基础BFS/DFS中网格、连通块、最短路径棋盘类★★★简单构造中需要你构造一个满足条件的排列或字符串★★★★数论基础GCD、因数中辗转相除、约数个数、互质判断★★★从表里可以看出如果时间有限优先把“排序贪心”“二分答案”“前缀和差分”这三板斧磨好C题就基本拿下一半了。下面逐个拆开细说。2.1 排序贪心C题最常见的出场方式贪心题的核心就一句话在每一步决策中选择当前看起来最优的方案并且这个选择在全局上也是最优的。ABC的C题里贪心特别喜欢考“配对”和“调度”两个变体。配对型贪心的经典模板是有N个物品每个物品有重量和价格要求两两配对使得某类价值最大/最小。它的解法几乎都是“排序后从两端向中间遍历”。之所以能从两端取是因为排序保证了较小值集中在左边、较大值集中在右边最优配对一定不会跨越中间区域。调度型贪心的经典模板则是若干个任务各有开始时间和结束时间问你最多能完成几个任务。这类题的结论是“按结束时间排序然后依次选择最早结束的任务”。这个结论的正确性可以用交换论证来证明如果最优解中的第一个任务不是结束时间最早的换成最早结束的不会让答案变差。分享一个实战经验做贪心题最忌讳“感觉对了就上”。强烈建议在写代码之前先用小规模例子试一试你设计的策略甚至用暴力枚举对拍验证。我在AtCoder上吃过太多次“自以为贪心对实际上反例就在眼前”的亏。2.2 二分答案把“最优值问题”变成“可行性问题”二分答案的适用场景非常明显题目要求你求“最大值的最小可能值”“最小值的最大可能值”或者简单地“能/不能达到目标值”并且你会发现判断一个候选值是否可行比直接求最优值容易太多。举一个ABC特别爱考的例子把N个数分成K组要求每组和的最大值尽量小。如果直接想“每组和的最大值最小是多少”很难下手但如果你反过来问“当每组和的最大值不超过X时最多能分成几组”这就变成一个纯模拟问题——从左到右累加超过X就开一组最后看组数是否≤K。写二分时最关键的坑是边界条件。我常用的模板是bool check(long long x) { // 判断当答案为x时是否可行 return true; // 根据题目实现 } long long l 0, r 1e18; // 下界上界要开够 while (r - l 1) { long long mid (l r) / 2; if (check(mid)) r mid; else l mid; } // 答案就是 r前提是 check 函数满足单调性原子操作先想清楚check函数的单调性再写循环。比如“组数最多不超过K”这件事X越大越容易成立这就是单调。如果题目不满足单调性二分就不能用强行用会WA到怀疑人生。2.3 前缀和与差分区间操作的一把万能钥匙前缀和解决的是“频繁查询区间和”的问题差分解决的是“区间多次加同一个数”的问题它们俩是逆运算组合起来就是C题的一道常见题型。差分模板我直接贴出来vectorlong long diff(N 2, 0); for (int i 0; i Q; i) { int l, r; long long x; cin l r x; diff[l] x; diff[r 1] - x; // 区间 [l, r] 整体加 x } for (int i 1; i N; i) { diff[i] diff[i - 1]; // 前缀还原 // 此时 diff[i] 就是位置 i 最终被加的总值 }这里有个细节值得注意差分还原时每次是diff[i] diff[i - 1]而不是diff[i] diff[i] diff[i-1]代码上没区别但思路一定要清楚——你是在做前缀累加。另外边界下标从1还是0开始一定要全文统一我在差分题上因为数组越界RE过不止一次。3. 精选真题拆解从读题到AC的完整心路这一节我挑两道非常有代表性的C题把整个思考过程完整走一遍而不是直接丢题解。你跟着我的思路走大概率能发现自己的问题出在哪。3.1 真题一给定排列用最少交换变成升序题面大概是给你一个1到N的排列你每次可以交换任意两个位置上的数问最少交换多少次能让整个排列升序。这题的“暴力”想法是每次找最小值放到最前面但这样需要O(N^2)的复杂度N2×10^5的时候扛不住。正确的贪心思路是用一个数组pos记录每个值当前所在的位置。从1到N循环如果位置i上的数不是i就交换pos[i]位置和i位置上的数同时更新pos数组。每次交换都至少让一个数归位最多交换N次所以答案是交换次数。代码长这样#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorint a(N 1), pos(N 1); for (int i 1; i N; i) { cin a[i]; pos[a[i]] i; } vectorpairint, int ans; for (int i 1; i N; i) { if (a[i] ! i) { int j pos[i]; swap(a[i], a[j]); pos[a[i]] i; pos[a[j]] j; ans.push_back({i, j}); } } cout ans.size() \n; for (auto [x, y] : ans) { cout x y \n; } return 0; }这题的“为什么贪心是对的”需要想清楚每次把值i放到它该在的位置i上这一步操作不会破坏已经归位的数因为被换走的那个数即使去了别的位置以后还会再被换回自己的位置。整个过程每个位置最多被操作一次所以步数一定最少。注意这类“交换排序”是ABC的高频考法2023年到2024年至少出现过三次类似的题。建议把上面代码连同思路一起背下来遇到直接套。3.2 真题二区间加之后求每个位置的最终值这道题是个比较典型的差分例题初始所有位置都是0给你Q次操作每次操作让区间[l, r]整体加一个值x问所有操作完成后每个位置的值。很多新手第一反应是直接模拟每次遍历l到r加上x。这在Q和N都比较小的时候没问题但一旦N和Q都是2×10^5模拟就是O(NQ)直接爆炸。用差分解决#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin N Q; vectorlong long diff(N 2, 0); for (int i 0; i Q; i) { int l, r; long long x; cin l r x; diff[l] x; diff[r 1] - x; } for (int i 1; i N; i) { diff[i] diff[i - 1]; cout diff[i] (i N ? \n : ); } return 0; }注意我用的是long long不是int。Q次操作每次加x如果x可以到10^9Q是2×10^5总和最大能到2×10^14int直接溢出。这个坑在ABC里太常见了只要你做过几次“看似简单但WA在溢出”的题就会长记性。3.3 真题三字符串修改最少次数经典贪心变式题面给你一个只含小写字母的字符串你每次可以把任意一个字符改成任意小写字母问最少改几次能让字符串中没有任何相邻的两个字符相同。这题最直观的贪心思路是从左到右扫如果s[i] s[i-1]就把s[i]改成一个和左右都不相同的字母。问题是这个“改”是随意的你要不要真的去改其实不需要。你只需要计数。因为每次把s[i]改成一个和左右都不同的字母后它就不会再影响i1位置的判断了因为已不同所以你甚至不用关心改成什么字母。那么答案就是所有满足s[i] s[i-1]的位置数量——不对这里有个细节如果连续三个字符都相同比如“aaa”你改第二个为b后变成“aba”只需要改1次而不是2次。所以正确做法是int ans 0; for (int i 1; i s.size(); i) { if (s[i] s[i - 1]) { ans; i; // 跳过下一个位置因为改掉 s[i] 后 s[i1] 可以和 s[i-1] 比较了 } }关键在那个i。很多人在这一行上翻车写成不跳过的版本遇到“aaa”就会得到错误的2而不是1。这题的真实考点其实不是字符串而是“你能否发现修改当前字符的全局影响局部化了”。这也是C题最常见的思维陷阱题面花里胡哨核心其实很简单。4. 从WA到ACC题常见的坑与排查方法打多了比赛你会发现C题真正折磨人的往往不是思路而是细节。思路卡住还有迹可循细节出错那就是纯粹的折磨。这一节我把C题最常见的错误类型整理成了一张速查表再逐个展开说说怎么排查。错误类型典型原因排查方法WA答案错误边界条件没处理好或者贪心策略有反例暴力对拍检查最小/最大数据TLE超时复杂度太高通常是O(N^2)先算上限操作数换更优算法RE运行时错误数组越界、空栈操作、除零看报错行号检查下标边界溢出错误用了int但结果超范围全部改成long long答案偏大/偏小取模时机不对、初始值不对手搓小样例验证初始值4.1 WA大方向对了但被细节背刺WA是最常见的。有些WA是思路本身有问题那没办法只能换思路但更多时候思路是对的只是边界细节出错。我有个自创的“三分排查法”先检查循环边界。for (int i 0; i N; i)和for (int i 1; i N; i)在这类题里很容易混尤其在涉及前缀和、差分的时候下标从0还是从1开始直接决定结果。再检查初始值。比如求最小值时初始值设成0答案就会恒为0求最大值时初始值设成太大答案也会不对。最后检查排序规则。compare函数里如果等于的情况返回true会出现未定义行为轻则WA重则RE。4.2 TLE复杂度失控的急救指南TLE的排查相对简单看数据范围算复杂度。如果N2×10^5你就应该知道O(N^2)必挂。但有一种隐蔽的TLE特别容易坑人你觉得自己写的是O(N log N)但实际上由于常数太大照样会超时。比如用set的insert和erase频繁操作复杂度是O(log N)没错但常数非常大如果N是2×10^5再配合大量操作在2秒时限内很可能就跪了。这种时候我通常换成vector加排序或者用手写的priority_queue速度会快很多。另外说到cin/cout如果你用了它但没关同步ios::sync_with_stdio(false); cin.tie(nullptr);这两行在N比较小的时候无所谓但N到2×10^5之后不关同步的cin/cout和scanf/printf的差距是数量级的。我见过太多TLE其实只是因为没关同步。4.3 溢出最隐蔽的白给方式我特意把溢出单独拎出来说因为它真的太常见了而且错误信息极不明显。你会觉得“我算法没问题啊怎么WA了”。其实只是因为你用了int而中间结果已经超过了2^31-1。一个非常经典的场景求数组的和或乘积做判断。就算最终结果在int范围内中间累加的过程也可能溢出。我的建议是新高题一律用long longusing ll long long;然后容器类型也直接写vectorll不要省。虽然这会稍微占一点内存但在现代AtCoder的内存限制下几乎不会有问题。4.4 一个屡试不爽的万能排查法小样例暴力对拍如果你刷题刷到一定量我强烈建议你学会“对拍”。这是我在准备这篇题解汇总时每道题都用过的方法也是救我最多次的办法。对拍的核心是写一个保证正确的暴力程序哪怕很慢和一个你怀疑TLE或WA的优化程序然后用随机小数据跑比对结果是否一致。# 生成随机小数据 python3 gen.py input.txt # 暴力程序跑一遍 ./brute input.txt out_brute.txt # 优化程序跑一遍 ./fast input.txt out_fast.txt # 比对 diff out_brute.txt out_fast.txt只要随机数据够多就能很快暴露出你的优化程序在哪些边界条件下出错。这个方法的效率比对着代码干瞪眼高太多了。我每次比赛前都会准备好这三个模板gen.py、brute.cpp、fast.cpp已经成为我刷题的标准配置。5. 刷题方法论怎么练C题才能稳定提升5.1 每周训练节奏以ABC为锚点的安排C题的训练不是“比赛打得多就行”而是要有针对性的刻意练习。我自己的习惯是每周三条线并行周六晚上完整打一场ABC体验真实比赛节奏。如果C题没过赛后必须补题。周日白天把这一场的C题和D题如果D题不是太难的话认真复盘写出题解笔记。周中从AtCoder题库里按“C题”标签随机抽2-3道旧题练手限定30分钟一道。这样一周下来大概能稳定做5道左右的C题一个月就是20道。坚持三个月C题基本就是稳定发挥的分数项了。值得注意的是随机抽旧题的时候建议选不同年代的AGC/ABC。早期ABC的C题难度波动很大有的讲真就是现在的D题难度遇到这种题做不出来别太沮丧直接看题解然后背思路就行。5.2 从C到D下一个瓶颈怎么破能在30分钟内稳定输出C题之后下一个目标就是D题。D题相比C题最大的区别在于它往往是“C题的算法外壳 一个更隐蔽的模型抽象”。它可能在跑完BFS之后还要再叠一层DP或者在二分答案之后还要处理一个数学公式。但D题的很多基础恰恰是C题练出来的二分、前缀和、排序贪心这些基本功不扎实D题看都看不懂。所以我的建议是不要急着越级刷题先把C题的正确率稳定在“10场里能AC掉8场”再开始碰D题。我自己是C题卡了大概三到四个月期间做了上百道C题量变引起质变突然有一天就发现自己看D题也有思路了。这个过程急不来但是方向一定不能错——基本功永远是第一位。6. 一些零零碎碎的实战心得最后这些想法可能不系统但都是我踩坑踩出来的想到哪说到哪。第一C题的题面通常不长但信息密度极高。逐字逐句读题是必须的尤其注意“最多”“最少”“不超过”“至少”这些词。很多时候WA不是算法错是题读错了。第二代码别急着写。我的习惯是先在草稿纸上用中文把思路写一遍哪怕只有三行。写完再看一眼数据范围心里估算复杂度然后才动手。这个习惯看起来慢实际效率非常高。第三关于“看题解”这件事。我的原则是比赛结束当天一定要看题解但看题解前至少独立思考30分钟。看完题解之后不要直接复制代码必须自己关掉题解重新写一遍。如果能把这道题的思路用一句话概括出来写进笔记这道题才算真正属于你。第四善用AtCoder的“Virtual Contest”功能。你可以自己组一套“ABC C题专场”找一个小时连续做5道模拟比赛压力。这个训练比松散地刷题要有效得多因为它逼你在紧张状态下调用知识。坦白说C题的难度并不高它考的不是天才般的灵感而是熟练度。只要你刷够量把常见套路熟到肌肉记忆的程度C题根本拦不住你。希望这篇整理能成为你刷题路上的一份顺手工具也希望你在ABC这条路上一场比一场顺畅。