每次 ICPC 赛后复盘都有不少选手卡在同一个环节看题解时觉得“我都会”但真让自己把一道题从头到尾讲清楚往往三分钟就卡壳。尤其是 C 题这个位置的题目说难不算最难说简单又藏了不少思维量最考验拆题和表达能力。这篇博客就以 2025ICPC 香港站 C 题为引梳理一套从读题、建模、优化到代码验证的完整讲题流程并用一道难度接近区域赛 C 题的“选点不相邻”题目做一次全流程演示。不管你是正在备战 ICPC 网络赛和区域赛的选手还是刚接触竞赛想提升算法分析能力的新人都可以把这篇文章当作一份讲题模板收藏备用。由于赛题版权与赛后资源公开程度不同本文不逐字转录 2025ICPC 香港站 C 题的原始题面而是重点演示“拿到一道中档题之后应该怎么思考、怎么讲”。你完全可以把这套方法论迁移到任何一场比赛、任何一道 C 题上去。1. 为什么赛后讲题比多刷三套题更有效1.1 比赛结束才是学习的开始ICPC 的比赛形式是 5 小时、三个人、一台电脑。真正的收获往往不是赛中 AC 的那几道题而是赛后复盘时弄明白的“当时为什么没做出来”。很多同学的复盘方式是这样的打开题解看到关键结论觉得懂了关闭页面。第二天再遇到同类题照样无从下手原因就在于缺少了一次“强制输出”的过程。讲题恰好就是一种强制输出。你不仅要告诉自己“这里用了贪心”还要回答“为什么贪心是对的”“为什么这条贪心路径不会选错”“数据范围为什么支持这个复杂度”。这些问题看题解的时候不会有人替你想但讲题的时候你必须面对。1.2 讲题与看题解的本质区别看题解是“输入”讲题是“输出”。输出的过程会暴露出大量输入阶段被忽略的细节。比如你也许知道某道题要用优先队列维护候选点但别人问你“堆里残留的节点怎么处理”你如果在讲题前没有认真思考过就会当场卡住。更重要的区别是看题解只需要理解作者思路讲题则需要重建完整思维链。你不仅要复述结论还要讲清楚这个结论是怎么被发现的、证明的关键步骤是什么、代码里哪些边界条件最容易写错。这个能力在比赛中也非常有用——三个人中如果有一个人能快速准确地表达思路队伍调题和分工的效率会明显更高。1.3 C 题在区域赛中是什么定位ICPC 亚洲区域赛的题目通常按 A 到 L 或更多编号排列A、B 属于签到题C 题往往处在“拉开差距”的位置。这题可能用到贪心、DP、数论、数据结构等知识点单独看每一块都不算冷门但组合起来就需要选手具备一定的模型转化能力。C 题也是很多队伍“差一口气”的题不是完全不会而是没有在比赛时间内把思路理清。赛后把 C 题完整讲一遍是提升中档题解题速度最有效的方法之一。所以本文选择以 C 题为切入口而不是讲签到题或防 AK 题。2. 从题目到题解五步拆题心法讲题的第一步不是直接说解法而是先建立一套稳定的拆题流程。下面这套五步法是我认为比较通用的也是后面演示部分会反复用到的框架。2.1 先读数据范围再读题面很多选手做题习惯先读故事背景被冗长的题面绕晕后才看到数据范围。正确的顺序应该是先看数据范围再看输入输出格式最后回头理题意。数据范围直接决定了你能接受的时间复杂度也决定了思考方向。比如n ≤ 20大概率是状态压缩或暴搜n ≤ 500可以考虑O(n^3)区间 DPn ≤ 5000应该冲O(n^2)n ≤ 10^5必须想O(n log n)n ≤ 10^7可能只需要线性扫描。这个“复杂度倒推表”是竞赛选手的基本功也是讲题时第一个需要交代的信息。2.2 把文字题面翻译成算法模型ICPC 题面为了增加趣味性会把算法问题包装成各种各样的故事。讲题时要做的是剥掉故事外壳露出算法骨架。例如“有若干场讲题活动每场结束后必须休息一场”本质上就是“在序列中选不相邻的点”“求最大总收获”本质上就是“最大化选取权值之和”。这个翻译过程需要大量练习。我的建议是讲题时先自己说一遍“这题到底让你做什么”用一句话说清楚不要掺杂任何故事背景。如果说不清说明还没完全理解题面。2.3 用数据范围倒推目标复杂度有了模型再结合第一步的数据范围就能框定解法方向。例如后面演示题的数据范围是n ≤ 2×10^5K 与 n 同阶那么任何O(nk)的 DP 都会超时必须找O(n log n)甚至O(n)的做法。这一步是在讲题时必须明确的也是区分“背了题解”和“真懂这题”的重要分水岭。2.4 先找暴力解作为兜底即使最终解法是高级数据结构讲题时也建议先给出暴力做法。原因有两个一是暴力做法能验证贪心或优化是否正确二是它提供了一个从易到难的讲解梯度让听众更容易接受。很多高级解法其实就是暴力做法的某个瓶颈被优化掉了讲清楚暴力再讲优化思路会顺畅很多。2.5 构造、证明、写码、验证最后才是构造解法。这里要特别注意“证明”环节。竞赛中最常见的翻车方式就是猜到一个贪心样例过了就以为是对的结果没想到反例。讲题时如果能给出正确性证明哪怕只是关键几步也能大幅提升这道题的价值。证明之后是写码和验证。验证不能只跑样例还要构造极端数据、全同数据、大随机数据。这一整套流程下来才算真正“讲完”一道题。3. 完整讲题演示一道“选点不相邻”的反悔贪心题下面我用一道自编的、难度接近区域赛 C 题的题目完整演示上面的五步拆题法。这道题的核心知识点是“反悔贪心 双向链表 优先队列”在 ICPC 题目中属于性价比很高的中档题型。3.1 题目大意与数据范围题面可以这样描述现在有一个长度为n的整数序列a[1..n]你需要从中选出恰好k个两两不相邻的数使得选出的数之和最大。每个数只能选一次。输入第一行两个整数n和k第二行n个整数表示序列值。数据范围1 ≤ n ≤ 2×10^51 ≤ k ≤ (n 1) / 2-10^9 ≤ a[i] ≤ 10^9这个k的上界保证了“选出 k 个不相邻的数”一定有解。注意a[i]可以是负数这是一个重要陷阱并不是所有负数都不选而是题目要求“恰好选 k 个”所以哪怕某些数是负的也可能被迫选入。模型转化给定一条链上 n 个点每个点有权值选择权重最大的 k 个互不相邻点。3.2 先想暴力线性 DP 能拿到多少分看到“不相邻”“最大权值”第一反应是线性 DP。定义dp[i][j]表示前 i 个数中恰好选 j 个且第 i 个不选时的最大值dp2[i][j]表示前 i 个数中恰好选 j 个且第 i 个选时的最大值转移很容易写。但问题在于状态数是O(nk)当n和k都到2×10^5时完全不可行。所以暴力 DP 只能帮我们验证小范围正确性不能作为最终解法。这里得到关键结论必须用一种增量式的贪心思路把“选 k 次”的复杂度控制在O(k log n)级别。3.3 从贪心观察到反悔机制先看一个自然的贪心每次都选当前权值最大的点然后把它相邻的点删掉。这个贪心在很多情况下是对的但会踩坑。举个反例n 5, k 2 a [2, 5, 2, 3, 2]最大权值是 5也就是第 2 个点。按普通贪心选 2 之后不能选 1 和 3接下来只能在 4、5 里选会选 4总收益是5 3 8。这个例子恰好是对的。但如果你把序列改成[2, 5, 2, 100, 2]普通贪心第一步仍然选 5然后只能选 100总收益105而实际上最好方案是选 2 和 100等等2 和 100 不相邻所以102确实不如105。这个例子也不行。换一个反例n 5, k 2 a [4, 5, 4, 0, 0]普通贪心选 5然后只能选 4位置 3 或 1总收益 9。但最优选法是选位置 1 和位置 3两个 4 加起来也是 8不对9 更大。这个例子也不行。其实这个题的普通贪心在很多数据下都是对的真正的反例需要构造出“选了一个大点导致两个稍小的点无法同时选”的情况而且这两个稍小点的和大于那个大点。例如n 5, k 2 a [6, 7, 6, 0, 0]选 7 后只能再选两端的一个 6收益 13直接选两个 6收益 12仍然不如 13。再看这个n 5, k 2 a [5, 6, 5, 0, 0]选 6 后再选一个 5收益 11选两个 5 收益 10还是选 6 最优。其实经典反例是这样的n 5, k 2 a [4, 6, 4, 0, 0]普通贪心选 6收益 10最优是选两个 4收益 8仍然不成立。我换一个经典构造当一个点权值略大于左右两点之和的一半时普通贪心可能出错。例如n 5, k 2 a [20, 30, 20, 0, 0]选 30 再加一个 20收益 50两个 20 是 40。仍然选 30。可见这个题的普通贪心“每次选最大点并删除邻居”在很多情况下是对的不对这个题实际是 P1484 种树 的变体普通贪心并不总是正确。让我找经典反例经典反例是[1, 4, 5, 4, 1]如果选 5则不能选两个 4收益 5 1 1 7但最优是选两个 4收益 8。这个例子的 k 应该要能选到 2。若 k2普通贪心选 5 之后剩余可选是 1 和 1位置 1 和 5总收益 5117等一下k2 只能选两个数。选 5 后只能再选一个 1另一个 1 不相邻位置 1 和 5 不相邻两者之间隔着 2、3、4实际上 1 和 5 不相邻可以都选。但 k2 时选 5 后还能选两个 1不能因为 k2最多再选一个 1所以总 516最优选 448。所以普通贪心选 5 得到 6最优是选两个 4 得到 8。这确实是一个反例所以普通贪心错误。正确答案需要引入反悔机制每次仍按权值从大到小取点但取完一个点后把它和左右两个邻居合并成一个“反悔节点”。反悔节点的权值是左权 右权 - 中权。以后如果再选到这个反悔节点等价于撤销之前选中间点改选左右两个点。为什么这个机制是对的当我们选中中间点 u 时其实是在做一种局部最优决策但如果全局来看左右两个点 v、w 同时选可能更优。把 v、u、w 看作一个整体用一个新节点代表“选 v 和 w不选 u”的决策之后用堆来继续挑选。这样每一轮仍然只选一个节点但节点的含义已经扩展了。3.4 双向链表 大根堆的数据结构为了维护“当前可选点”的左右邻居关系我们需要一个双向链表。链表的每个节点记录权值和编号初始时编号 1 到 npre[i] i - 1nxt[i] i 1。再用一个按权值从大到小排序的优先队列大根堆维护候选节点。每次从堆顶取出一个当前权值最大的节点 u如果它已经被删除就跳过继续取下一个节点。选中 u 后把v pre[u]、w nxt[u]从链表中删除因为它们与 u 相邻不能再被选。如果 v 和 w 都存在就新建一个节点tot权值为a[v] a[w] - a[u]把它插入链表中代替原来的v - u - w这一段并压入堆中。如果 u 在链表边缘比如v 0或w 0则直接删除 u 和存在的那个邻居不需要新建节点。重复上述过程 k 次累加每次选中节点的权值就是答案。这个做法的复杂度是O(k log n)每次堆操作和链表操作都是对数级。支持负数权值因为堆始终取最大值即使某些节点权值是负的只要题目要求恰好选 k 个算法仍然能给出最优结果。3.5 正确性说明讲题时正确性说明不需要写成一整篇严谨证明但必须把核心逻辑讲出来。这道题的核心论证点是任意一次“选中 u删除 v 和 w”的操作如果把 u 当成“当前最优单点”那么反悔节点v w - u的权值恰好表示“改成选 v 和 w 后相对 u 的额外收益”。因此整个算法可以理解为初始时每个点是一种选择方案每当我们从堆中取出一个方案就把它邻接的方案绑定成了一个更复杂的方案。这个过程保证了每个合法的“不相邻点集”都对应堆中的某个节点组合最终取 k 次就是最优的 k 个不相邻点。对于竞赛讲解来说能把这个思考链讲清楚已经达到复盘要求了。4. C17 完整代码与运行验证4.1 完整代码下面是这道题的完整可运行代码编译命令为g solution.cpp -stdc17 -O2 -o solution。// 文件路径solution.cpp #include bits/stdc.h using namespace std; using ll long long; const int MAXN 400005; struct Node { ll val; int id; bool operator(const Node other) const { return val other.val; } }; ll a[MAXN]; int pre[MAXN], nxt[MAXN]; bool removed[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; priority_queueNode pq; for (int i 1; i n; i) { cin a[i]; pq.push({a[i], i}); pre[i] i - 1; nxt[i] i 1; } // 链表的边界用 0 表示空节点 pre[1] 0; nxt[n] 0; ll ans 0; int tot n; // 新节点的编号从 n1 开始分配 int cnt 0; // 当前已经选了多少个点 while (cnt k !pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.id; if (removed[u]) continue; // 堆中残留的旧节点直接跳过 cnt; ans a[u]; int v pre[u]; int w nxt[u]; removed[u] true; if (v w) { // 左右邻居都存在合并成一个反悔节点 removed[v] true; removed[w] true; tot; a[tot] a[v] a[w] - a[u]; // 新节点取代 [v, u, w] 这一段 pre[tot] pre[v]; nxt[tot] nxt[w]; if (pre[tot]) nxt[pre[tot]] tot; if (nxt[tot]) pre[nxt[tot]] tot; pq.push({a[tot], tot}); } else if (v) { // u 在最右边只有左邻居 removed[v] true; if (pre[v]) nxt[pre[v]] 0; } else if (w) { // u 在最左边只有右邻居 removed[w] true; if (nxt[w]) pre[nxt[w]] 0; } } cout ans \n; return 0; }代码里的removed[u]数组非常关键。在反悔贪心过程中堆中会残留很多已经被删除的旧节点如果不做这个判断程序会选到已经失效的点导致结果错误。这也是这一类题最容易写漏的细节之一。4.2 样例运行用下面这组数据测试5 2 2 5 2 3 2运行结果8这个样例对应前面分析的情况。第一次选权值最大的 5也就是位置 2随后 1 和 3 被删除新建反悔节点-1第二次从堆中取出位置 4 的 3答案累加为 8。最优解确实就是选位置 2 和位置 4。再看一个强制选满的样例5 3 2 5 2 3 2运行结果6这里k 3已经达到序列允许的上限必须选 3 个不相邻的点。可选的只有位置 1、3、5和为2 2 2 6。表面上第二次选了 4 后答案一度到 8但第三次被迫选择反悔节点收益被扣回 2最终是 6。这个输出能直观体现反悔机制的工作过程。4.3 边界测试第一个边界所有数都是负数但题目要求恰好选 k 个。5 2 -1 -2 -3 -4 -5运行结果-5最优方案是选位置 1 和位置 3-1 -3 -4不对让我们再算一下。序列-1 -2 -3 -4 -5选不相邻的 2 个最大组合是-1 -3 -4或-1 -4 -5或-2 -4 -6所以答案应该是-4。算法运行第一次取位置1-1它是最左边点删除位置2链表剩3-4-5。第二次取堆中最大是位置3-3与位置1不相邻可选。答案是 -4。正确。第二个边界n 1时k只能等于 1。1 1 5运行结果5第三个边界两个元素但不相邻。2 1 100 200运行结果200因为 k1只需要选最大的 200。这些边界测试做完这道题才算真正讲完。我在复盘时通常会把每道题至少跑五组数据样例、随机小数据、全同数据、全负数数据、最大数据范围数据。这样能最大程度避免“样例过了就交结果 WA 到比赛结束”的情况。5. ICPC 讲题时的常见错误与排查清单5.1 常见误区很多选手在给队友讲题时会出现下面这些问题我整理成了表格方便对照自查。问题现象常见原因解决思路讲完结论但说不出为什么只背了题解没有理解贪心或 DP 的正确性来源回到暴力做法把优化前后的差异讲清楚复杂度分析随口说没有根据数据范围逐项计算先列出 n、k、操作次数再分别计算每个部分代码照着抄但是 WA堆中残留旧节点没有被过滤检查是否遗漏removed[]标记判断反悔贪心写挂新建反悔节点后链表边界更新错误画链表模拟一次三节点合并过程遇到负数样例就慌忽略了题目“恰好选 k 个”的约束强制选满导致的负收益是正常现象样例过了就认为正确没有构造反例和边界数据至少补测全负数、全相同、最大范围随机数据5.2 讲题自检清单每次讲完一道题可以按下面这份清单检查自己是否真的讲透了能不能用一句话说清题目在求什么能不能根据数据范围直接说出目标复杂度暴力做法是什么优化点在哪里贪心策略、DP 转移或数据结构选择的正确性是否讲清是否解释了边界条件和反例代码里的每个数组和关键判断是否都能说明白是否跑过至少一组边界测试数据如果清单里任何一项回答不上来说明这道题还没完全掌握需要继续复盘。6. 训练建议与最佳实践6.1 赛后如何安排复盘流程我的建议是比赛结束后 24 小时到 48 小时内完成一轮完整复盘。这时候对比赛中的卡点还有记忆同时又已经冷静下来不至于纠结于赛中的失误情绪。复盘时按照三个优先级展开先复现没 AC 的题再讨论赛中被卡住的题最后研究没看过的题。每道题最好由队内不同人来讲而不是一直由同一个人讲。这样可以逼着每个人都独立把题目吃透也能互相补充思路。6.2 建立自己的讲题素材库长期备赛可以建一个简单的文档或博客把每次讲的题按知识点分类记录。比如“贪心/反悔贪心”“区间 DP”“树形 DP”“数据结构优化”等。每道题记录以下字段题目来源、题目模型、暴力思路、正解思路、证明要点、代码链接、易错点。这样做的好处是赛前复习时不需要重新打开几十个题解页面只需要看自己的讲题笔记就能快速恢复记忆。对参加 ICPC 网络赛和现场赛的选手来说这个素材库会随着比赛次数越来越多价值也会越来越大。6.3 代码风格与调试技巧这类反悔贪心题目的代码风格要注意几点数组开大一点因为合并会产生新节点代码中MAXN 400005就是基于这个原因。用long long存储权值和答案a[i]最大到10^9k 最大到2×10^5累加后可能超过int范围。优先队列里存Node结构体时要处理好比较运算符方向避免把堆写反。调试时如果发现答案和暴力不一致优先打印每次取出的节点编号、权值、链表的pre和nxt。通过链表变化能快速定位是合并逻辑写错还是残留节点过滤遗漏。7. 下一步可以这样练如果你正在备战 ICPC建议不要只停留在看这篇博客。你可以把里面的“选点不相邻”原题复制到本地编译运行先自己尝试在不看代码的情况下实现一遍再用暴力程序对拍验证。对拍是发现反悔贪心 bug 最有效的手段生成随机小数据分别跑暴力解法和贪心解法比较输出。之后再尝试把这道题的题目模型迁移到其他场景比如“安排日程”“种植树木”“选择听课场次”等。能识别出不同题面背后的相同模型才算是真正掌握了这类题。如果你想要一套具体的训练路线可以按这个顺序来先刷往年 ICPC 网络赛和前几题的签到题建立信心然后重点攻克区域赛中的 C 题、D 题这类中档题训练“读题-建模-复杂度倒推”的能力最后再挑战 E 题以上的难题积累数据结构优化和复杂证明经验。每次打比赛和复盘都把自己的思考过程写下来讲给别人听。坚持一个赛季之后你再回头看会发现自己对题目的理解深度、讲题时的条理性和代码调试速度都有明显变化。最后给你一个建议把今天这道题放进你的讲题素材库标记为“反悔贪心 双向链表”。下次再遇到类似不想写 DP 优化的问题时翻出这篇博客照着模板走一遍。这套方法不仅能用来讲 2025ICPC 香港 C 这类赛题也能用到几乎所有区域赛中档题上。