刚刷完又一场AtCoder Beginner Contest趁着题目还热乎赶紧把这一期“ABC杂题选讲”整理出来。先说清楚这里的ABC是AtCoder Beginner Contest不是Mac上那个删不掉的ABC输入法也不是数码管里叫a、b、c的那几段。不过第三题我确实会拿七段数码管当素材讲到“段”和“位”的时候你大概率能理解为什么有些东西叫“位运算”比叫“状态压缩”更直观。这期选的三道题难度大致落在ABC的B到D题之间覆盖了前缀和与差分、排序贪心、位运算枚举三个高频考点。不管你是在备战下周的ABC还是刷题卡在某类题上一直WA都可以直接对着文里的代码和思路走一遍。我会把推导过程、代码实现、以及我踩过的坑全部摊开讲保证你读完能复现而不是只记住一个“好像要用差分”的模糊印象。1. 选讲思路为什么这三类题最值得练1.1 ABC的出题规律与杂题选讲的价值AtCoder Beginner Contest的题目虽然叫“Beginner”但近几年的难度曲线已经不像早期那么平缓了。A题和B题基本是语法题和简单模拟C题开始进入“需要想一下”的范畴D题就经常要求你掌握一个明确的算法套路或者数据结构。换句话说ABC是区分“会写代码”和“会做算法题”的分水岭。这期选的三道题正好对应三个非常典型的分水岭场景。第一题是区间修改加单点查询考察差分的理解第二题是带截止时间的任务调度考察排序加贪心的配合第三题是七段数码管的状态枚举考察位运算和子集遍历。三道题没有一道需要高深的数据结构线段树、平衡树、树状数组全都不用但它们恰好覆盖了ABC里出现频率最高的三类思考方式把区间操作改成端点操作、把无序问题变成有序问题、把组合状态变成二进制枚举。杂题选讲的价值就在这里。按知识点刷题很容易陷入“知道这题用差分所以AC”的假象真正比赛时没人告诉你这题该用什么算法。选讲的意义是让你看到一个看起来复杂的题目是怎么一步步被拆成你熟悉的基本操作的。1.2 本期三道题的难度定位与知识点地图三道题的定位我按“代码量从小到大、思考量从浅到深”排了个序。第一题只涉及一个差分数组核心代码不超过15行但它能帮你把“区间加”这个操作从脑内模拟变成条件反射。第二题需要对贪心的正确性做一次完整的逻辑闭环代码量也不大但“为什么这样排序、为什么这样替换”才是这道题真正的考点。第三题是位运算入门题但如果你对二进制掩码不熟很容易在编码和判断上卡半小时代码写出来倒是不长。如果你准备打本周的ABC我建议你把这三题当成一个“热身套餐”先写差分题找手感再写贪心题练证明最后写位运算题强化对状态的敏感度。三道题全部独立完成之后再对答案效果比一次性刷三十道相同类型的题要好得多。我给每道题都配了C代码第二题和第三题额外给了Python版本的参考思路方便不同语言习惯的读者对照。代码部分我尽量保持ABC赛场上的写法不封装类、不搞花哨语法核心逻辑一目了然。2. 第一题区间修改与单点查询前缀和与差分2.1 题面还原与入手分析第一题的题面是这个样子的数轴上有N个格子初始值全为0一共有Q次操作每次操作给出l、r、v要求把第l个格子到第r个格子之间的所有格子都加上v。所有操作结束后输出每个格子的最终值。数据范围是N和Q都到2e5v可能是负数。如果你第一次看到这道题最直接的想法肯定是写个双层循环外层枚举Q次操作内层从l走到r挨个加v。这个写法在N和Q都只有100的时候完全没问题但一旦数据到2e5最坏情况下要做4e10次加法肯定超时。这就是典型的“暴力算法能过样例但过不了大数据”的场景。所以我们需要一个办法把“区间内每个位置都加v”这个看起来很庞大的操作变成只修改两三个位置最后再做一次统一处理。差分数组就是干这个用的。2.2 从暴力到差分的完整推导差分数组的定义很朴素对于一个数组a我们记它的差分数组为d其中d[i] a[i] - a[i-1]并约定a[0] 0。换句话说差分数组存的是原数组相邻两个位置的差值。这个定义看起来平淡无奇但它有一个非常巧妙的性质对原数组a的某个区间[l, r]加上v等价于对差分数组d做两个单点修改d[l]加上vd[r1]减去v。为什么因为区间[l, r]内部相邻元素的差值没有变化唯一变化的位置就是区间左端点比前一个元素多了v和区间右端点的下一个位置比区间内最后一个元素少了v。等所有操作都做完之后我们只需要对差分数组d求一次前缀和就能还原出最终的a数组a[i] a[i-1] d[i]。整个过程的时间复杂度是O(NQ)比暴力的O(NQ)快了不止一个量级。我刚开始学差分的时候一直绕不过弯总觉得“只改两个端点怎么能代表整个区间呢”。后来我想了一个生活化的类比你有一排计分牌现在要给第3到第7个牌子都加1分。笨办法是走过去挨个翻牌子差分数组的做法是在第3个牌子下面放一个“从这里开始加1”的标签在第8个牌子下面放一个“到这里停止”的标签。最后统计的时候从头走到尾看到“开始”标签就累计加1看到“停止”标签就累计减1每个牌子经过的地方自然就带上了正确的加分。理解了这个类比差分就再也不会忘了。2.3 C实现与细节提示#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 v; cin l r v; diff[l] v; diff[r 1] - v; } vectorlong long a(N 1, 0); for (int i 1; i N; i) { a[i] a[i - 1] diff[i]; cout a[i] (i N ? \n : ); } return 0; }这里有几个细节值得单独说。第一diff数组要开N2不是N1。因为区间右端点如果恰好是N那么r1就是N1这一格必须存在否则会数组越界。第二v的类型要开long long。如果v本身是2e5级别的数操作次数也是2e5那么单个位置累计的最终值可能达到4e10超过int的范围。我在第一次写这类题时就在这上面吃过亏样例全过提交全WA找半天才发现是类型爆了。第三如果你问“什么时候该用差分什么时候该用线段树”我的经验是如果操作全部给完最后只查询一次差分是首选如果操作过程中需要随时查询某个位置的值那就得用树状数组或线段树。差分本质上是离线处理它只适合“先改完再问”的场景这一点一定要分清。3. 第二题排序后贪心证明比代码更重要3.1 题面还原任务调度与收益最大化第二题的场景很经典你有N个任务每个任务完成需要1个单位时间第i个任务有一个截止时间D[i]和一个收益P[i]。你在任意时刻只能做一个任务并且任务必须在其截止时间之前或恰好截止时间完成问最多能获得多少总收益。这道题第一次见很容易懵因为每个任务耗时都是1但截止时间各不相同你需要在“做哪些任务”和“按什么顺序做”之间做决定。直觉上截止时间早的任务应该优先做但这又不完全对因为一个截止时间晚、收益极高的任务可能更应该被做。我举个例子你就明白了。现在有两个任务任务A截止时间是1收益是10任务B截止时间是2收益是100。如果按截止时间从早到晚做先做A再做B总收益是110正好都能完成。但如果是三个任务A截止时间1收益10B截止时间1收益50C截止时间2收益100先做A再做B就不行了因为A和B都卡在时间1上只能二选一这时候应该放弃收益低的A保留B和C。所以这题的难点不在“排序后按顺序做”而在于“当时间冲突时怎么决定放弃谁”。3.2 贪心策略的正确性论证这题公认的高效解法是先把所有任务按截止时间从小到大排序然后遍历任务用一个最小堆维护当前已选任务的收益。遍历到第i个任务时先把任务放进堆里然后检查堆的大小是否超过了当前任务的截止时间D[i]。如果堆的大小大于D[i]说明在截止时间D[i]之前已经安排了太多个任务时间不够了必须踢掉一个收益最低的任务。由于堆是最小堆堆顶就是当前已选任务中收益最小的那个直接把它弹出即可。为什么这个策略是对的关键在于“堆的大小不超过截止时间”这个约束。因为每个任务耗时1个单位时间如果你在某个截止时间为D的时刻已经选了超过D个任务那么无论如何排列都不可能让这些任务全部在各自截止时间内完成。所以每当堆的大小越界就必须移除一个任务。为了最大化总收益移除收益最小的那个一定是最优的。这里有一个常见的误区有人会把任务按收益从大到小排序然后尝试把每个任务塞进最近的空闲时间。这种“按收益贪心”的做法需要一个额外的数据结构来维护空闲时间代码量会多一些。而“按截止时间排序最小堆”的写法每一步的决策都有清晰的约束条件证明起来也干净。我更喜欢后者。3.3 代码实现与常见误区#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorpairint, long long tasks(N); for (int i 0; i N; i) { cin tasks[i].first tasks[i].second; // D, P } sort(tasks.begin(), tasks.end()); priority_queuelong long, vectorlong long, greaterlong long pq; long long ans 0; for (auto [d, p] : tasks) { pq.push(p); ans p; if ((int)pq.size() d) { ans - pq.top(); pq.pop(); } } cout ans \n; return 0; }Python版本的核心逻辑一样用heapq即可排序后逐任务push收益同时累加总和如果堆长度超过截止时间就弹出最小值并扣掉相应收益。写这题时最容易犯的错误有两个。第一个是排序方向搞反按截止时间从大到小排序导致整个贪心链条崩掉。第二个是没有理解“堆大小超过截止时间”这一条件有人会用“当前时间”来比较而不是用“堆大小”这两个概念在任务耗时全为1的前提下是等价的但直接用堆大小更贴近约束的本质也更好写。还有一个容易被忽略的点ans要在每次push时先加上收益如果后面被弹出再减掉。如果你先判断再决定是否push逻辑上不会错但写起来容易漏掉“入堆又出堆”的情况。先加后减看起来多一步操作实际上是最不容易出错的写法。4. 第三题用位运算枚举解决“段码”类状态题4.1 题面还原7段状态与约束条件第三题我选了七段数码管作为背景。这题和热搜词里“7段码分abc”意外地搭上了边因为七段数码管的每一段确实都有名字通常用a到g标记。这里的“a、b、c”是物理上的段名和AtCoder Beginner Contest缩写里的ABC只是碰巧同名但用来作题面素材反而很顺手。题面是这样设计的有一块七段数码管初始时某些段已经亮了你可以在剩余的段中再点亮任意多段。问有多少种点亮方案使得最终亮着的段恰好能拼成一个数字0到9中的某一个注意初始已经亮的段不能被熄灭你可以选择不点任何新段。数据范围非常小总共7段但正因为小很多人反而会绕进一个思维陷阱想把所有可能的点亮方案人工分类数来数去就乱了。正确答案是让计算机枚举所有可能性而位运算就是做这件事最自然的方式。4.2 子集枚举与位运算技巧七段数码管的7段恰好对应一个7位二进制数的7个bit。我们给每段分配一个位a段对应第0位b段对应第1位c段对应第2位d段对应第3位e段对应第4位f段对应第5位g段对应第6位。这样一来任意一个“亮段集合”都可以用一个0到127之间的整数表示比如第0、1、2位为1就表示a、b、c三段亮。数字0到9各自对应的段集合是这道题的“字典”必须提前写对。我给出的参考映射是0a, b, c, d, e, f不含g1b, c2a, b, d, e, g3a, b, c, d, g4b, c, f, g5a, c, d, f, g6a, c, d, e, f, g7a, b, c8a, b, c, d, e, f, g9a, b, c, d, f, g有了这个字典剩下的事情就变成枚举了。我们枚举所有可能的“新增点亮段”集合addadd取值范围是0到2^7 - 1的任意整数。对于每个add最终状态finalMask init | add。然后我们检查finalMask是否等于数字0到9中某一个的段集合。如果等于说明这个方案合法计数加一。这里用到的位运算就两个按位或|用来合并初始亮段和新增亮段按位与可以用来检查某个段是否在集合中。你不需要任何高级技巧只需要习惯“集合即整数”的思维方式。4.3 实现细节与Debug经验#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int digitMask[10]; digitMask[0] (10)|(11)|(12)|(13)|(14)|(15); digitMask[1] (11)|(12); digitMask[2] (10)|(11)|(13)|(14)|(16); digitMask[3] (10)|(11)|(12)|(13)|(16); digitMask[4] (11)|(12)|(15)|(16); digitMask[5] (10)|(12)|(13)|(15)|(16); digitMask[6] (10)|(12)|(13)|(14)|(15)|(16); digitMask[7] (10)|(11)|(12); digitMask[8] (10)|(11)|(12)|(13)|(14)|(15)|(16); digitMask[9] (10)|(11)|(12)|(13)|(15)|(16); string s; cin s; int init 0; for (char c : s) { init | 1 (c - a); } int ans 0; for (int add 0; add (1 7); add) { int finalMask init | add; bool ok false; for (int i 0; i 10; i) { if (finalMask digitMask[i]) { ok true; break; } } if (ok) ans; } cout ans \n; return 0; }这段代码我在写的时候也踩了两个坑。第一个坑是段码映射写错尤其是数字2和数字3很容易把g段和e段搞混。写完字典之后建议单独写个循环把所有数字的mask输出一遍肉眼核对一下比在完整代码里找错要快得多。第二个坑是位运算优先级init | 1 (c - a)这一行里的优先级高于|所以没问题但如果你写出finalMask init | add这种表达式就会先算init | add再判断相等虽然这里恰好符合直觉但在更复杂的表达式里很容易踩坑。我的建议是涉及到和位运算混用的地方一律加括号不要省。如果你想把这道题扩展一下还有一个变体很值得做不预设初始亮段而是问“有多少种子集能拼出一个数字”。那答案就变成统计所有digitMask中不同的mask去重后的数量。这种扩展可以帮你把“集合计数”和“去重”的思维一起练起来。5. 实战丢分点与排查技巧实录5.1 我踩过的几个WA陷阱我在初学阶段被WA吞掉的分数比很多人的AC总数还多。整理几个最典型的希望你避开。第一个是差分数组的类型问题。前面已经提过int会被大范围区间加爆掉必须用long long。判断依据很简单如果N、Q、v三者相乘可能超过2e9就不要用int。第二个是贪心题排序键的选择。有些题的排序键是截止时间有些是截止时间加某个次要条件还有极少数的题是“最早截止时间优先但不完全等价于按截止时间排序”。如果你在排序之后发现答案在某些边界数据上不对先别怀疑算法把排序结果打印出来手动模拟一遍前几个任务基本就能看出排序逻辑有没有偏离题意。第三个是位运算枚举时漏掉了finalMask必须包含init这一约束。有人会直接枚举所有可能的finalMask统计它们是否等于某个数字mask但忘了初始段是不能熄灭的。也就是说你枚举的finalMask必须满足(finalMask init) init否则这个状态根本不可能从初始状态得到。我在4.2节里用init | add来生成finalMask天然保证了这一点如果你换成直接枚举finalMask的写法就一定要补上这个判断。5.2 TLE排查与复杂度估算法ABC的时间限制通常是2秒Python和C的常数差异很大但复杂度估算的方法是一样的。一个很实用的经验公式如果数据范围是2e5那O(N log N)的算法在C里完全可以过O(N^2)基本没戏如果数据范围是10^7O(N)也得很小心常数O(N log N)基本会超。判断一道题该用什么算法先看N的数量级再反推允许的复杂度这比硬背算法模板有效得多。如果你在本地测试大数据时发现运行时间接近时限优先检查这几类问题是不是用了endl而不是\nendl会强制刷新缓冲区慢很多是不是在循环里重复计算了不变量是不是vector扩容导致内存反复拷贝。多数情况下把输入输出缓冲关掉、把endl换成换行符速度就能提升一大截。5.3 适合新手的调试三件套我调试题目的三板斧是局部打印、assert断言、最小样例手动模拟。局部打印很好理解在关键计算节点把中间变量打出来和小数据的手算结果对一下。assert断言适合检查那些“你觉得不可能发生”的情况比如差分数组的下标越界、贪心堆弹出时堆为空一旦断言失败立刻就能定位到问题。最小样例手动模拟则是解决“代码逻辑绕不明白”的终极手段拿一支笔在纸上把每一步状态写出来和程序输出比对。这三招加起来超过90%的WA和RE都能在十分钟内定位。尤其是assert很多人觉得它多此一举但它在竞赛现场的价值是帮你把“模糊的恐慌”变成“精确的崩溃点”大幅缩短排查时间。6. 怎样把ABC题目真正转化为能力6.1 补题比刷题重要我的复盘流程做完整场ABC之后我的习惯不是立刻刷新题而是花一小时把没做出的题补完。补题不是看完官方题解抄一遍代码就完事而是要做三件事第一用自己的话把题解的思路重新讲一遍讲不清楚的地方就是理解漏洞第二把官方解法和你赛时的思路对比找出“卡住的那个点”到底在哪一步第三不看代码独立再过一遍确保下次遇到类似的题能想起来。这三步看起来简单但只要你坚持做二十场ABC之后会明显感觉到差距。我见过很多人刷题量很大但同一类题反复错就是因为少了“对比和理解”这一步只停留在“看懂了题解”的舒适区。6.2 从ABC走向更高难度的路径ABC的D题和E题之间有一段明显的台阶。如果你D题稳定能做出来我建议你开始接触AtCoder Regular Contest的A题和B题以及一些经典的中等难度模板题比如最短路径、动态规划、并查集这些。到那个阶段你会发现前期的差分、贪心、位运算这些基础工具会像积木一样被重新组合成更复杂的解法。但这期讲的三道题仍然是底座。差分是很多数据结构题的起步贪心是思维题的一半位运算是状态压缩动态规划的敲门砖。把这三样练熟你的ABC分数不会差更重要的是你后续学任何高级算法都会顺很多。最后再分享一个我实际打比赛时的习惯每次赛后不管成绩如何都会把这三类题基础数据结构、贪心、位运算各挑一道写进周复盘笔记记录当时的思考卡点和最终理解。几个月后再回头看你会明显感觉到自己的思维速度在变快。这大概就是杂题选讲这个系列存在的意义吧。