先解释一下标题里那个“坠”字——顺手打的就当是“随笔”的笔误吧。这几年AtCoder Beginner Contest简称ABC我基本周周不落从灰名一路打到绿名再稳定在绿到水色之间。有人问我怎么提升最快我的答案一直是同一句话把C题吃透。A和B是手速题拉不开差距真正决定你rating曲线的分水岭就是C题。这篇文章不是去粘贴某一场的题解而是把我这两年复盘了几十场ABC C题后总结出来的一套方法论完整写出来——C题到底在考什么、有哪些高频题型模板、从暴力到正解的思维链路怎么走、代码实现里哪些坑我反复踩过以及具体怎么拿三道典型题完整走一遍流程。不管你是刚能把A、B稳定AC、正准备向C题发起冲击的新手还是卡在茶绿段位很久、想突破瓶颈的老选手这篇文章应该都能给你一些参考。1. C题到底在考你什么为什么它是一道分水岭先说一个很多人没意识到的现实。ABC的A题本质是“读题就会做”B题是“想到枚举/模拟就会做”但到了C题题目突然开始考察你一个叫“想法”的东西。它往往会让数据范围变大到你无法直接暴力枚举的程度逼着你去找规律、找性质、或者套用某个基础算法模型。换句话说A和B考的是你会不会写程序C考的是你会不会思考问题。1.1 C题的难度定位从AtCoder的难度色标来看ABC的C题通常对应Difficulty 200到600这个区间大致是灰色高分到绿色低分的范围。你会发现一个有意思的现象很多rating在800到1200之间的人A、B可能三五分钟就AC了但在C题上能卡到比赛结束。这不是代码能力的问题而是脑子里没有建立起“看到什么样的问题就该往哪个方向想”的反射。我见过太多人做C题的方式是这样读题后觉得“我可以暴力”然后写了一坨复杂度超标的模拟代码交上去TLE接着开始怀疑人生。这不是因为他笨而是因为他在按做B题的思维做C题。C题的一个核心特点就是它通常不会让你直接暴力通过但也不会要求你掌握多么高深的算法。绝大多数C题需要的只是排序、二分、贪心、简单DP、BFS/DFS、前缀和、或者基础数学推导中的某一种工具难的是识别出“该用哪个工具”。1.2 为什么说C题决定你的上限打个比方A和B就像科目一题库你把题背熟了就能过C题则像科目二它考的是你对车辆语言和算法的基本控制能力不同的人在这里开始拉开差距。如果你能稳定在比赛开始后半小时内AC掉C题你的rating一定不会停留在一千以下。反过来如果你每次都是“想到了思路但写挂了”或者“看了题解恍然大悟但比赛时就是想不到”那说明你的问题不在做题量而在思维训练的方式。我自己的经历就是例证。刚开始打ABC的那段时间我的成绩清单是“AACB”或者“AAAC”——是的我第一次C题AC花了快两个月。后来我开始有意识地做一件事不做完整题解只研究C题。我把每场ABC的C题拿出来不看题解、不限时慢慢想想不出来才看答案然后问自己一个问题“为什么我在读完题的那一两分钟里没有往这个方向想”这个习惯直接让我的C题AC率从不到30%涨到了现在的大概80%。2. C题高频题型地图这些模式看到就要条件反射刷了几十场C题之后你会发现C题并不像想象中那么千变万化。虽然每道题的背景故事都在变但底层的数学模型翻来覆去就那么几个。我把它们按出现频率从高到低整理了一下你可以对照自己薄弱的地方针对性训练。2.1 排序贪心C题的常青树这是ABC C题里出现频率最高的一类大概占了三成左右。它们的共同特征是给你一个数组、一些区间、或者若干物品让你求最大收益、最小代价、最多能选几个、最少要分几组之类的问题。核心思路通常是排序之后从左到右依次做决策证明贪心策略的正确性然后实现。识别这种题的关键词最大化、最小化、最多、最少、区间覆盖、背包选物品。遇到这种题先别急着动态规划先想想排序后从头扫一遍能不能解决——很多时候答案就是这么简单。2.2 二分答案把“求最优”变成“验证可行”二分答案在C题里的出现频率排在第二而且近年有越来越多的趋势。这类题的特征非常明显如果题目问的是“某值最小是多少”或者“某值最大是多少”且这个值越大后续的可行条件就越难满足满足单调性那么大概率就是二分答案。很多新手对二分答案总觉得害怕觉得它抽象。其实你只要记住一个心法我不直接求答案我猜一个答案然后写一个check函数验证它行不行。而验证通常比直接求简单得多因为验证往往可以用贪心完成。2.3 数学推导与取模看似编程题实则数学题数学类的C题在ABC中占比也不低。典型的有排列组合求方案数、最大公约数/最小公倍数与循环周期结合、奇偶性分析、取模运算的规律推导。这类题的难点在于把题面里的自然语言条件翻译成数学表达式。我做这种题有一个习惯先在纸上手算小数据找规律。比如N1、N2、N3的情况分别是什么结果写出来之后往往能看出一个递推式或通项公式。这个方法看起来笨但应对C级数学题比空想快得多。2.4 简单图论与网格遍历BFS/DFS的地盘当题面里出现“网格”“连通块”“最短步数”“能否到达”这些词时你该第一时间想到BFS或DFS。C题里的图论基本不会超出建图遍历的范畴但会在细节上设一点小坑比如允许重复访问时的状态设计、网格行列的不同含义、起点或终点被障碍物堵住的情况。2.5 前缀和与差分的巧妙应用前缀和这个玩意儿在C题里很少单独考但它经常作为优化手段出现在混合题中。比如一道题暴力做是O(n²)但只要你先构造一个前缀和数组复杂度就能降成O(n)。所以你要把它当成“思维最后一步的杀手锏”来掌握。我整理了一张表方便按题型快速对号入座题型识别特征常用手段典型复杂度排序贪心最大化/最小化、区间选择sort 扫描O(n log n)二分答案“XX最小/最大”、单调性二分 checkO(n log V)数学推导计数、周期、奇偶性手算小数据找规律O(1)或O(log n)图论遍历网格、连通、最短步数BFS/DFSO(HW)或O(NM)前缀和/差分区间操作、连续和预处理数组O(n)这张表不是让你背而是建议你在做C题前先看一遍当题目特征对应到某个格子时你的尝试范围就从“无边无际”缩小到了“几个候选方向”。3. 从TLE到AC的推导链路一条可复制的思维路径很多人问我“你是怎么从读题到写出正解的”他们以为这是天赋其实不是这是一条可以被总结成固定步骤的思维路径。我把它拆成四步每一步都有明确的判断标准。3.1 第一步看数据范围判断暴力是否可行这一步是分岔路口也是很多人忽略的关键。我在读题后做的第一件事永远是看N的取值范围。如果N ≤ 1000O(n²)的枚举在2秒时限内大概能过如果N ≤ 10⁵O(n log n)几乎是上限如果N ≤ 10⁶甚至更大那你必须找到O(n)甚至O(log n)的解法。举一个实际例子题目给一个长度为N的数组让你求某个条件下满足要求的数对数量。如果N ≤ 2000双重循环判断每个数对完全可行但如果N ≤ 2×10⁵你的第一反应就不该是枚举数对而是想着“怎么用排序双指针或者二分把枚举过程压缩掉”。数据范围是你选择算法的罗盘不看它就直接开写等于蒙着眼睛开车。3.2 第二步用最朴素的方式先让题目跑通哪怕超时这里是我的一个独特习惯可能和很多人的建议相反在分析复杂度前我会先在脑海里把最暴力的做法写出来。不是真的提交而是用来对照。暴力代码能帮你厘清题面到底在做什么避免因为过度优化而写错逻辑。比如一道C题让你求“最少操作多少次能让所有数相等”暴力的做法是枚举最终相等的目标值然后计算每个目标值下的操作次数。虽然它可能是O(n²)甚至更糟但一旦你能写出这个暴力你再看数据范围就能立刻意识到“我其实是在某个值域空间上求最小值”——这就是二分答案或三分搜索的入口。3.3 第三步寻找单调性、排序性质或公式规律这是整个推导过程最核心的一步也是最无法被公式化的一步。但根据我的经验90%的C题突破口都在以下三个方向中的一个单调性答案越大或越小条件越容易或越难满足。如果存在这种关系考虑二分答案。排序性质把数组排个序之后原本复杂的关系会变得井然有序。比如任意两个数的差的最小值一定出现在排序后的相邻元素之间。数学规律把题面的操作翻译成数学表达式看看有没有周期性、对称性、或可抵消的项。我用一个很经典的例子来说明假设有N个区间每个区间有开始时间L和结束时间R你要选择尽可能多的区间要求它们互不重叠。暴力做法是枚举所有子集复杂度O(2^N)N稍微大一点就彻底爆炸。但如果你想到“按结束时间排序然后从左到右贪心选择”——每次选结束最早且与之前选区不冲突的区间——你就能得到正确答案。为什么这个贪心成立因为结束时间越早为后面留下的空间就越多这是整个问题最核心的性质。3.4 第四步根据正解复杂度反推所需算法当你找到了一个方向最后一步是确认复杂度是否匹配数据范围。如果猜测是二分答案那么check函数的复杂度该是O(n)还是O(n log n)如果猜测是贪心那么排序用什么比较器这一步做完你再写代码时就不再是“边写边想”而是“照着设计图施工”出错的概率会小很多。这套四步走法我每次做C题都会在脑子里过一遍基本能在五分钟内确定主攻方向。当然也有判断失误的时候但总比拿到题就瞎试要稳定得多。4. 实现层的地雷阵那些让我WA到怀疑人生的编码细节思路对了但代码写挂是C题最让人崩溃的失败方式。我在这个环节栽过的跟头加起来可以写满一张A4纸。下面挑几个高频雷区详细说每一个都是我用WA换来的教训。4.1 整数溢出和取模数据范围的红线ABC里N的上限经常是10⁵或10⁶级别很多人习惯性用int存中间计算结果结果在求和或乘法处溢出导致输出负数或错误大数。我的习惯是只要题目数值范围超过10⁴就无脑开long long。这个习惯让我少交了起码二十次WA。取模问题是另一个坑。题目说“答案对998244353取模”注意它什么时候取模。加法取模要在每一步都做防止中间结果溢出减法取模要先加模数再取模防止负数乘法的两个long long相乘可能溢出long long本身这时要用__int128或模乘函数。4.2 sort比较器你以为你写了其实你写错了C题里几乎一半的题目要用到排序而排序比较器是我认为WA率最高的代码片段。最常见的错误有两个。第一个比较器不满足严格弱序——比如return a b;会导致排序行为未定义在某些编译器上直接RE。第二个多关键字排序时没有明确第二关键字。举一个例子你要按区间长度降序排序长度相同按左端点升序。正确写法是sort(v.begin(), v.end(), [](const pairint,int a, const pairint,int b){ if (a.second - a.first ! b.second - b.first) return a.second - a.first b.second - b.first; return a.first b.first; });注意比较器返回的是“a是否应该排在b前面”的布尔值而不是“谁大谁小”的差值。返回差值会让你在有些测试点上得到完全随机的结果。4.3 二分模板边界条件是二分题的唯一难点二分的逻辑本身很简单难的是边界到底取l r还是l r、答案是l还是r。我自己踩坑踩到后面总结出了一套不容易出错的写法——半开区间模板long long low 0, high INF; // 答案在 [low, high) 区间内 while (high - low 1) { long long mid (low high) / 2; if (check(mid)) high mid; else low mid; } // 循环结束后 high 是第一个满足 check 的值这套模板尤其适合“求满足条件的最小值”这类问题。你把low初始化为肯定不满足的值high初始化为肯定满足的值然后不断缩小区间。用这个模板之后我二分题的边界错误率大幅下降。4.4 输入输出效率别让I/O拖垮你的正解C题卡常的情况不算多但偶尔会有“输入量大到cin超时”的题目。我的做法是在比赛代码开头永远加上这两行ios::sync_with_stdio(false); cin.tie(nullptr);如果是C语言选手直接用scanf和printf就行。如果你看到N是10⁵甚至更大输入是多行整数这个优化基本是必须的。别小看这一点有的题不加这两行即使你的算法是对的也会TLE在最后一个测试点上那种冤案我经历过不止一次。4.5 一个容易忽视的细节把“正确思路”实现成“错误逻辑”我举一个具体场景题目让你统计网格中每个连通块的大小。思路很清晰BFS每个未访问过的格子统计队列弹出的次数。但在实现时你很容易在标记访问时出错——比如在弹出时才标记vis而不是在入队时标记。这在某些情况下会导致同一个格子被重复入队连通块大小被统计错。记住一条铁律在入队或入栈的那一刻就标记访问而不是在出队时才标记。这不是C题独有的坑但C题的数据范围往往会让这种错误精准地引爆。5. 拿三道典型题完整走一遍流程从读题到AC的全过程光讲方法论不给实例是耍流氓。这一节我选了三个最常出现的模型用“完整推导核心代码”的方式带你把第3节和第4节的东西串起来。这三道题都经过抽象化处理但模型非常典型你能在大量真实ABC C题中找到它们的身影。5.1 区间调度类型的完整剖析题目模型有N个区间每个区间有左端点L和右端点R选择尽可能多的区间使它们两两不重叠。N最大10⁵L和R的范围在int内。推导过程看到“最多能选几个”再加上区间的特征第一反应是贪心。接下来要确定贪心策略。我先想在纸上画了三个区间重叠的情况发现不管前面怎么选留下“结束最早”的区间总不会让后面的选择变得更差。这就是关键性质。于是排序规则确定为按右端点升序然后从左到右扫描当前区间的左端点大于等于上一个选中区间的右端点就选它。核心代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint,int v(n); for (int i 0; i n; i) { cin v[i].first v[i].second; } sort(v.begin(), v.end(), [](pairint,int a, pairint,int b) { return a.second b.second; }); int ans 0, last -1e9; for (auto [l, r] : v) { if (l last) { ans; last r; } } cout ans \n; return 0; }这段代码里注意两点我用了last -1e9而不是INT_MIN防止减法溢出比较器只按右端点排序没加多余条件。这个模型在ABC里出现过至少十次每次换的壳子都不一样但底层的贪心逻辑完全一致。5.2 二分答案型题目的完整剖析题目模型有N个包裹重量分别为W[i]要求按顺序把它们装到K个桶里每个桶的容量为X。问最小需要多大的桶容量才能装下所有包裹。N最大2×10⁵W[i]最大10⁹。推导过程题干出现了“最小容量”而且是典型的“容量越大越容易装完”的单调关系我立刻锁定二分答案。check函数就模拟装桶的过程从头开始扫当前桶还能装就装装不下就换新桶如果用的桶数超过K就说明容量小了。check的复杂度是O(n)二分范围从0到所有重量之和总复杂度O(n log sumW)完全足够。核心代码bool check(long long x, vectorlong long w, int k) { int cnt 1; long long cur 0; for (long long weight : w) { if (cur weight x) { cnt; cur weight; } else { cur weight; } } return cnt k; } int main() { int n, k; cin n k; vectorlong long w(n); long long low 0, high 0; for (int i 0; i n; i) { cin w[i]; high w[i]; } while (high - low 1) { long long mid (low high) / 2; if (check(mid, w, k)) high mid; else low mid; } cout high \n; return 0; }这个题的隐藏坑有两个。第一个是单个包裹重量可能大于你二分的mid如果某个W[i]本身就超过Xcheck会永远失败。第二是low的初始值应该是max(单个包裹最大重量, 总重量/k)而不是0否则二分会多跑好几轮且可能在极端数据下出错。5.3 网格BFS型题目的完整剖析题目模型一个H行W列的网格起点(Sx,Sy)到终点(Gx,Gy)每个格子可能是空地或墙体四方向移动每次移动消耗1点体力问从起点到终点的最短移动步数。H、W最大10³。推导过程看到“最短步数”和网格直接上BFS。BFS天然保证第一次到达某个格子时的步数就是最短步数所以不需要处理松弛更新。状态用二维dist数组表示到达每个格子的最小步数初始化为-1表示未访问。核心代码const int dx[] {1, -1, 0, 0}; const int dy[] {0, 0, 1, -1}; int bfs(vectorstring grid, int sx, int sy) { int h grid.size(), w grid[0].size(); const int INF 1e9; vectorvectorint dist(h, vectorint(w, INF)); queuepairint,int q; dist[sx][sy] 0; q.push({sx, sy}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx h || ny 0 || ny w) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] ! INF) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } //假设终点是 (h-1, w-1) return dist[h-1][w-1] INF ? -1 : dist[h-1][w-1]; }这个模型的易错点在第4节里提过必须在入队时标记dist否则同一个格子会反复入队复杂度退化成指数级。另外注意边界判断的写法写成nx 0 || nx h的顺序逻辑更清晰不容易漏。这三个模型覆盖了C题大约60%的题目类型。不是让你背代码而是让你体会那道“推导链”——看到特征定位模型写出check或贪心逻辑然后小心边界实现。这个过程重复到一定次数你做C题就会从“想破头”变成“按流程走”。6. 赛后复盘的正确姿势如何让每一道C题都变成你的题感最后这部分聊一个被绝大多数人忽略的环节复盘。很多人打完比赛看了题解“哦原来如此”然后就关了页面。这种做法的问题在于你的大脑并没有记住“我为什么没想到”下次遇到同类题时你还是会卡。我自己从对手速和AC率的提升经验来看真正重要的不是“做了多少题”而是“复盘了多少题”。6.1 给复盘定一个固定流程我每次打完ABC不管C题有没有做出来都会花二十分钟做三件事。第一件事重做一遍C题不看任何题解自己重新推导到AC。第二件事看官方题解和排位靠前的选手代码对比思路的差异。第三件事也是最重要的一件写一段“思维日志”回答这几个问题——我一开始往哪个方向想了为什么往那个方向想正确的突破口是什么如果下次再遇到类似特征的题目我应该第一时间往哪里想这段思维日志不需要很长三五句话就行但它会强迫你从“知道答案”变成“理解路径”这个过程才是真正涨rating的时刻。6.2 建立你自己的“题感库”所谓题感其实就是“特征到解法”的映射表。每复盘一道C题就往自己的题感库里添加一条映射。比如“求最小最大值” → 二分答案“区间选最多” → 按右端点贪心“网格最短步数” → BFS“相邻差异最小” → 排序后看相邻对“方案数取模” → 计数DP或组合数学积累到三四十条之后你会发现一个新现象看到新题的那一刻你的直觉会自动把它归类到某几条候选映射中然后你只需要挨个试。这就是“题感”的本质——不是玄学是模式识别的经验积累。6.3 我的一点训练建议C题专场练习如果你想在短期内快速提升C题能力我推荐一个策略从AtCoder的过去比赛中抽出最近十场的C题把它们当作独立的专项训练集。每道题限时四十分钟做完不看别人的代码只看官方题解核对思路。这十道题不要分十天做最好三天内密集完成让大脑在短期内反复接触C题的常见特征和推导链路。我做这个训练时还有一个具体心得如果一道题你卡了二十分钟还没有一个像样的方向直接看题解但看完题解后的当天晚上必须重新独立做一遍。这个“隔夜重做”的效果比连续做两遍好得多因为睡眠会让记忆固化第二天你再做时大脑会主动检索前一天学到的路径。最后聊一个心态问题。C题做不出来很正常尤其你刚开始冲击这个难度时可能连续十场都卡在C题上。但请你注意一个容易被忽略的信号如果你每场C题的暴力版本都能想通只是优化不到正解那说明你的思路基础是好的缺的只是“模式识别”的练习量。这恰恰是最有希望突破的阶段。我自己在这个阶段停留了大概一个月之后突然像开窍了一样C题AC率开始直线上升。多给自己一点耐心把每一次“想不到”都当作一次“建立连接”的机会。慢慢来比较快。