算法竞赛补题实战：从赛后复盘到知识体系构建

1. 从“补题”说起算法竞赛的赛后复盘价值每次算法竞赛结束看着榜单上那些没来得及做或者没做出来的题目心里总有点不甘。这种不甘恰恰是算法能力提升最宝贵的燃料。所谓的“补题”远不止是把题目答案抄一遍那么简单。它是一次深度的、主动的、系统性的赛后复盘是把赛场上的压力、混乱和灵感缺失转化为冷静分析、知识巩固和思维拓展的过程。对于参加“MINIEYE杯”这类高水平赛事的大学生来说补题的质量往往决定了你从这场比赛中能带走多少真正的“干货”而不是仅仅一个排名。算法竞赛尤其是像中国大学生算法设计超级联赛这样的系列赛题目设计往往紧扣前沿的算法思想与巧妙的数学模型。赛场上时间紧迫、心态波动很多题目可能只来得及想个大概或者卡在某个关键的优化步骤上。赛后补题就是给你一个机会在没有时间压力的情况下重新审视题目拆解出题人的意图梳理出清晰的解题链路并最终用代码实现。这个过程是对你知识漏洞的一次精准扫描也是将新学到的“奇技淫巧”内化为自身武器库的关键一步。2. 2021赛季第二场典型赛题分析与解题脉络重建由于无法获取2021年“MINIEYE杯”第二场比赛的原题我们将基于此类赛事如ICPC、CCPC区域赛的常见出题风格和难度分布构建几道具有代表性的虚拟赛题并深入剖析其解题思路。这不仅能模拟补题过程更能提炼出通用的解题方法论。2.1 虚拟赛题A基于图论与数据结构的综合应用题目描述虚拟给定一个n个节点、m条边的无向连通图每个节点有一个权值。定义一条路径的“价值”为路径上所有节点权值的异或和。进行q次操作操作分两种1. 修改某个节点的权值2. 询问从节点u到节点v的所有简单路径中路径价值的最大值。核心难点解析 这道题融合了图论路径查询、位运算异或和、以及动态维护点修改等多个知识点。最朴素的想法是枚举所有路径但显然不可行。突破口在于对“异或”性质的深度利用。在树上任意两点间的路径异或和可以通过预处理根节点到每个节点的前缀异或和然后利用xor(u, v) prefix_xor[u] ^ prefix_xor[v] ^ value[lca(u, v)]的性质其中lca为最近公共祖先快速求得。但这里是任意图且要求“所有简单路径”的最大值。解题脉络重建问题转化首先注意到对于连通无向图我们可以先求出其任意一棵生成树如DFS树。那么任意两点间的路径都可以看作是树上路径再异或上若干个“非树边”对应的环的权值。因为任何一条简单路径加上一条非树边就会形成一个环。这个性质是关键。线性基引入如何高效处理“异或上若干个环”来求最大值这引入了算法竞赛中的一个利器——线性基。我们可以将所有“环”的异或值即非树边对应的环的权值异或和插入一个线性基中。线性基可以维护一个集合使得从该集合中选取若干元素进行异或操作能得到原集合所有可能异或结果中的最大值在给定维度下。动态维护挑战题目带修改。修改一个点的权值会影响所有包含该点的环的权值。如果每次修改都重新计算所有环并重建线性基复杂度无法承受。这里需要更精巧的设计。一种思路离线/分治考虑操作分块莫队思想在树上的变种或时间分治线段树。将操作序列分块对于每个块内的查询静态处理块外所有修改的影响视为初始状态然后处理块内操作。但这在图上实现较为复杂。另一种思路利用特殊性质如果题目保证图是仙人掌图每条边最多属于一个简单环或树则问题可以简化。对于树没有环问题退化为静态树路径异或最大值可使用可持久化Trie树解决。对于仙人掌图环是独立的修改一个点权值只影响其所属的环最多一个可以暴力更新该环对应的线性基元素。最终算法框架假设为一般图采用离线分治预处理图的DFS生成树得到树边和非树边。预处理所有非树边对应的环的异或值构建初始线性基。将操作序列分块。对于每一块将本块内涉及修改的节点标记为“关键点”。重新计算只包含“关键点”和其相关边的小子图的环信息更新线性基中受影响的环对应的值。由于关键点数量少分块大小B这个子图也很小更新代价可接受。对于本块内的每个查询操作使用当前最新的线性基并结合树上路径异或和需用数据结构如树链剖分或倍增维护带修改的点权查询最大异或值。复杂度大约为 O((q/B) * (n m) q * B * logW)其中W是权值位数如60需要精心调整块大小B。注意这道虚拟题体现了算法竞赛中常见的“知识组合”与“问题转化”思维。看到“异或最大值”要条件反射想到线性基看到“图上路径问题”要想到生成树和环的关系。补题时不仅要写出代码更要理清这条“为什么想到用这个算法”的逻辑链。2.2 虚拟赛题B贪心策略证明与细节实现题目描述虚拟有n个任务每个任务有一个开始时间s_i和结束时间e_i以及一个收益v_i。你有一台机器同一时间只能做一个任务。任务可以做任意次但每次必须从开始时间做到结束时间并获得收益。此外存在一个“冷却时间”c即做完一个任务后机器需要空闲c单位时间才能开始下一个任务即使下一个任务的实际开始时间还没到。求能获得的最大总收益。核心难点解析 这是一个带冷却时间的区间调度问题。如果没有冷却时间c这就是一个经典的加权区间调度问题可以通过动态规划DP解决按结束时间排序dp[i] max(dp[i-1], v_i dp[p(i)])其中p(i)是最后一个在任务i开始前就结束的任务下标。加入冷却时间c后状态转移发生了变化因为“上一个任务”的结束时间到“当前任务”的开始时间必须至少间隔c。解题脉络重建状态定义仍然定义dp[i]为考虑前i个任务按结束时间排序后能获得的最大收益。转移方程修正对于任务i有两种选择不选则dp[i] dp[i-1]选则我们需要找到最后一个结束时间 s_i - c的任务j。注意这里不是找开始时间早于s_i - c的任务因为冷却时间是在上一个任务结束后开始计算的。因此p(i)的定义需要修改为最大的下标 j满足e_j s_i - c。高效查找p(i)由于任务已按结束时间排序我们可以通过二分查找在O(log n)时间内找到这个p(i)。因此转移方程为dp[i] max(dp[i-1], v_i dp[p(i)])。边界与初始化dp[0] 0。按此DP即可。贪心策略的思考有同学可能会想是否可以用贪心例如每次选结束时间最早且收益不错的任务。对于不带权值的普通区间调度最大化任务数量贪心选结束时间最早的是正确的。但对于带权值的情况贪心通常不正确。例如一个收益很高但时间很长的任务和一个收益稍低但时间很短且能做好几个的任务贪心无法做出全局最优判断。因此此题必须使用动态规划。实现细节排序按结束时间e_i升序排序。预处理为了快速二分查找p(i)可以额外维护一个数组end_times存储所有任务的结束时间。二分查找使用upper_bound找到第一个结束时间 s_i - c的位置然后减一即可得到p(i)。// 虚拟代码框架 (C) struct Task { long long s, e, v; }; bool cmp(const Task a, const Task b) { return a.e b.e; } int main() { int n; long long c; cin n c; vectorTask tasks(n1); // 1-indexed for(int i1; in; i) cin tasks[i].s tasks[i].e tasks[i].v; sort(tasks.begin()1, tasks.end(), cmp); vectorlong long dp(n1, 0); vectorlong long end_times(n1); for(int i1; in; i) end_times[i] tasks[i].e; for(int i1; in; i) { dp[i] dp[i-1]; // 不选当前任务 long long limit tasks[i].s - c; // 找到最后一个结束时间 limit 的任务下标 int j upper_bound(end_times.begin()1, end_times.begin()i, limit) - end_times.begin() - 1; if(j 0) { // 注意j可能为0 dp[i] max(dp[i], dp[j] tasks[i].v); } else { // 如果没有这样的任务那么当前任务可以单独选 dp[i] max(dp[i], tasks[i].v); } } cout dp[n] endl; return 0; }注意这类区间DP问题排序依据按开始时间还是结束时间和状态定义至关重要。补题时要自己尝试证明贪心为什么不行举反例并理解二分查找在此处优化的本质——利用单调性将O(n)的查找降至O(log n)。2.3 虚拟赛题C数论与组合数学的巧妙结合题目描述虚拟给定一个素数p和一个整数k。定义F(n)为将n写成p进制数后各位数字的乘积。求∑_{a0}^{k} ∑_{b0}^{k} [F(a) F(b) F(ab)]的值其中[条件]是艾弗森括号条件成立为1否则为0。结果对某个大质数取模。核心难点解析 此题初看可能让人无从下手直接枚举a和b是O(k^2)不可行。关键在于理解p进制下数字乘积F(n)的性质以及等式F(a) F(b) F(ab)在什么情况下成立。解题脉络重建分析F(n)的性质在p进制下每个数位d满足 0 d p。F(n)是各数位d的乘积。特别注意如果任何一位是0那么F(n)0。转化等式条件F(a) F(b) F(ab)。情况一如果F(ab) 0那么要求F(a) F(b) 0。由于F(x)非负这意味着必须F(a) 0且F(b) 0。情况二如果F(ab) 0那么等式要求一个正整数等于另外两个非负整数的和。这看起来更复杂但结合p进制加法的性质我们可以发现更深刻的规律。深入探究非零情况F(ab) 0意味着ab在p进制下的每一位都不为0。现在考虑p进制加法它可能产生进位。关键观察是在没有进位发生的加法中每一位是独立的且F(a) F(b) F(ab)几乎不可能成立除非很多位为1。更严格的分析需要用到Kummer定理的一个相关思想ab在p进制下某一位为0当且仅当该位加法中a和b的对应位之和为p产生了进位且下一位得到0。但这指向的是F(ab)0的情况。实际上经过更细致的推导这是补题时需要自己动手做的可以发现当F(ab) 0时要使F(a) F(b) F(ab)成立条件极为苛刻可能只存在于a或b非常小例如0或1的情况下。我们可以通过暴力枚举小数据来验证这个猜想。问题简化基于以上分析我们可以猜测满足等式的(a, b)对绝大多数都落在F(a)0或F(b)0或F(ab)0的情况里。而F(x)0当且仅当x在p进制下至少有一位是0。计数方法总对数总共有(k1)^2对 (a, b)。不满足等式的对数我们转而计算不满足等式的对数然后用总数减去。不满足等式即F(a) F(b) ! F(ab)。通过小范围暴力打表观察规律可能会发现不满足等式的对数有某种规律或者满足条件的对数非常少可以直接枚举所有F(x) ! 0的x这样的x数量级远小于k然后在这些x中检查等式。因为F(x) ! 0意味着x在p进制下的每一位都是1到p-1这样的数被称为p进制下的无零数其数量增长比k慢得多。最终策略预处理出所有 0 x k 且F(x) ! 0的x记为集合S。|S| 大约为 O((p-1)^{log_p k})在k很大时仍然远小于k。对于 (a, b)如果a∉S或b∉S或(ab)∉S则F(a),F(b),F(ab)中至少有一个为0。此时等式F(a)F(b)F(ab)成立的条件非常严格即三个数中两个为0且第三个也为0或者类似我们可以单独分类讨论计数。最复杂的情况是a∈S,b∈S, 且(ab)∈S。此时三个F值都非零。这样的三元组 (a, b, ab) 非常少我们可以直接枚举S中的a和b检查ab k且(ab)∈S并验证等式是否成立。由于|S|很小这个枚举是可行的。具体计算令A0 {x | 0xk, F(x)0}A1 S {x | 0xk, F(x)!0}。计数满足等式的 (a, b)情况1a∈A0且b∈A0。此时F(a)F(b)0。等式成立要求F(ab)0。这等价于(ab)∈A0。因此需要计算有多少对 (a,b) 满足 a,b,ab 都在A0中。A0是“p进制表示中含有0”的数这个集合的计数可以通过数位DP来解决计算 [0, k] 范围内p进制表示中不含0的数的个数然后用总数减去得到|A0|。但计算三元组 (a,b,ab) 都在A0中的数量较为复杂可能需要再次利用到A0的性质ab在A0中概率很高进行近似或进一步DP。情况2a∈A0,b∈A1。等式0 F(b) F(ab)。由于F(b) 0这要求F(ab) F(b)且F(ab) 0。这意味着加法过程不能改变非零数位的乘积这几乎不可能除非a0。所以可能只有a0时成立。同理a∈A1, b∈A0对称。情况3a∈A1, b∈A1。这就是上面提到的直接枚举S中的元素进行验证。通过这种分类我们将问题化简为对几个较小子集的枚举和计算。注意这道题是典型的“分析性质简化问题”“小范围暴力枚举”的组合。补题时最大的收获不是最后的AC代码而是学会如何从恐怖的数学等式中通过分析函数定义、进制特性找到问题的特殊结构和突破口将不可计算的大问题拆解成可处理的几个小情况。2.4 虚拟赛题D动态规划优化与模型转换题目描述虚拟有一个长度为n的数组a。你可以进行若干次操作每次选择两个相邻的元素将它们合并为一个元素其值为原两个元素的和。每次操作后数组长度减1。最终希望得到一个非递减的数组即b[1] b[2] ... b[m]。求最少操作次数。核心难点解析 这是一个数组划分问题目标是划分成若干段每段合并成一个数使得这些数非递减并且要求段数最多即操作次数最少因为操作次数 n - 段数。令dp[i]表示考虑前i个元素最后一段以i结尾时能得到的最多段数或最少操作次数。那么转移方程是dp[i] max_{j i} { dp[j] 1 }其中需要满足条件第j1到i这一段的和记为sum(j1, i) 上一段即以j结尾的那段的和last_sum[j]。解题脉络重建朴素DP及瓶颈直接DP需要O(n^2)的时间对于n很大如1e5的情况会超时。瓶颈在于对于每个i需要枚举所有可能的j。优化思路我们需要快速找到对于当前的i哪些j是“合法”的满足sum(j1, i) last_sum[j]并在这些合法的j中找到最大的dp[j]。将条件改写sum(j1, i) prefix[i] - prefix[j] last_sum[j]即prefix[i] prefix[j] last_sum[j]。其中prefix[i]是前缀和。重新定义状态我们发现转移条件只和prefix[j] last_sum[j]有关。但last_sum[j]就是第(k1)...j段的和其中k是使得dp[j]取得最大值的前一个分割点。这似乎陷入了循环。经典模型转化这个问题有一个经典的贪心解法但其正确性需要证明。我们可以考虑一个等价问题从左到右扫描尽可能让当前段的和更小但同时要满足非递减。这引导我们想到一个算法维护当前段的和cur_sum和上一个段的和last_sum。从第一个元素开始不断将元素加入当前段直到当前段的和cur_sum last_sum。此时我们就把当前段切分出来作为新的一段然后last_sum cur_sum并开始新的当前段。如果扫描完所有元素后最后一段的和也满足 last_sum那么就成功了。操作的次数就是n - 段数。贪心正确性证明补题关键可行性这样得到的序列显然满足非递减。最优性段数最多采用反证法。假设存在一个最优解其第一段结束位置比我们贪心算法找到的位置更靠后即段更大。那么最优解的第一段和S_opt必然大于等于我们贪心算法的第一段和S_greedy因为贪心算法在cur_sum last_sum时就立刻切分了而最优解可能继续吞并了后面的元素。考虑第二段贪心算法会从一个更小的起点开始并且要求第二段和 S_greedy。最优解的第二段需要 S_opt而S_opt S_greedy因此最优解对第二段的要求更严格。这会导致从第二个段开始最优解每一个段的和的下界都比贪心解的下界大从而可能更早地耗尽数组元素导致总段数不会比贪心解更多。因此贪心解不会比最优解差。算法实现初始化last_sum 0,cur_sum 0,segments 0。遍历数组a的每个元素xcur_sum x。如果cur_sum last_sumsegments。last_sum cur_sum。cur_sum 0。遍历结束后如果cur_sum 0最后一段未满足条件就被数组末尾截断说明贪心失败不我们需要检查。实际上如果最后cur_sum 0且cur_sum last_sum那么无法形成非递减序列因为最后一段太小。但题目保证有解至少可以合并到只剩一个元素。我们的算法在最后一步即使cur_sum last_sum也会因为遍历结束而被迫将最后一段切出此时序列可能不满足条件。因此我们需要一个修正当发现cur_sum last_sum但数组已用完时说明我们当前段的起点可能太早了应该回退将当前段与上一段合并。这增加了实现复杂度。更稳健的DP优化贪心思路虽然优美但边界处理麻烦。我们回到DP优化。定义dp[i]为前i个元素能划分的最大段数。我们需要dp[i] max{ dp[j] 1 }其中j满足prefix[i] - prefix[j] last_sum[j]。我们维护一个数据结构例如单调队列或平衡树其中按prefix[j] last_sum[j]排序。对于当前的prefix[i]我们只需要查询数据结构中所有key prefix[i]的项中dp[j]的最大值。而last_sum[j]就是prefix[j] - prefix[prev[j]]其中prev[j]是使得dp[j]最大的前一个分割点。这仍然有后效性。最终方案二分答案贪心验证这是一个更清晰的思路。我们二分答案“段数”K。问题转化为能否将数组分成K段使得每段和单调非减。验证时我们贪心地让前面段的和尽可能小这样给后面段留出更多空间。具体验证函数check(K)设每段和的下界为lower_bound初始为0。从数组开头开始尽可能少地取元素直到当前段和 lower_bound且在满足此条件下当前段尽可能短。这就确定了第一段。将第一段的和设为新的lower_bound重复过程。如果能在数组用完前恰好或提前形成K段并且最后一段和 lower_bound则返回true。如果还没到K段数组就用完了或者某一段无法满足 lower_bound即使取完剩余所有元素也不够则返回false。二分K的范围是1到n。时间复杂度 O(n log n)。// 虚拟代码框架二分答案贪心验证 bool check(int k, vectorlong long pref) { int n pref.size() - 1; long long last_sum 0; int start 1; // 当前段的起始位置1-indexed int segments_formed 0; for (int i 1; i n; ) { // 找到最小的end使得 sum(start, end) last_sum // sum(start, end) pref[end] - pref[start-1] long long target last_sum pref[start-1]; // 二分查找第一个 pref[end] target 的位置 int end lower_bound(pref.begin()i, pref.end(), target) - pref.begin(); if (end n) { // 即使把剩下的全用了也不够说明无法满足 return false; } // 成功找到一段 segments_formed; last_sum pref[end] - pref[start-1]; start end 1; i start; // 更新i到下一段的开始 if (segments_formed k) { // 已经分了k段检查剩余元素是否能作为最后一段其实上面循环已经保证了最后一段的和last_sum // 更准确的检查如果start n说明还有剩余元素它们自动成为第k1段但我们需要恰好k段。 // 因此当segments_formedk时必须要求start n即in没有剩余元素。 return (start n); } } // 循环结束数组用完了但段数没到k return false; } int main() { int n; cin n; vectorlong long a(n1), pref(n1, 0); for(int i1; in; i) { cin a[i]; pref[i] pref[i-1] a[i]; } // 二分最大段数 int l 1, r n, ans 1; while(l r) { int mid (lr)/2; if(check(mid, pref)) { ans mid; l mid 1; // 尝试更多的段数 } else { r mid - 1; } } cout n - ans endl; // 最少操作次数 n - 最多段数 return 0; }注意这道题体现了算法竞赛中常见的“二分答案”技巧。当直接求解最优值困难但给定一个值后判断是否可行相对容易时就可以考虑二分。补题时要掌握将“最小化操作次数”转化为“最大化段数”的思维以及如何设计check函数。贪心验证函数的设计是核心需要仔细思考其正确性。3. 补题实战方法论从看懂题解到真正掌握补题如果只是看懂别人的代码然后提交收获会大打折扣。一套高效的补题流程能让你把一道题的营养吸收殆尽。3.1 第一步独立复现与深度理解看完题目后先不要急着看题解。自己尽最大努力思考哪怕只有一点思路也尝试写一写伪代码明确自己卡在了哪里。然后阅读题解时重点关注突破口题解第一个关键观察是什么为什么能想到那里例如看到“异或最大值”想到线性基看到“区间合并”想到DP或贪心。知识链接这道题用到了哪些你已经学过但没想到的算法/数据结构哪些是新的把它和你已有的知识体系连接起来。推导过程题解中的公式、不等式、性质是如何一步步推导出来的自己动手在草稿纸上跟着推一遍。代码细节边界条件循环起止、数组下标、特殊判断n0, n1、数据结构初始化等这些往往是WA错误答案的根源。3.2 第二步抛开题解从头实现这是最关键的一步。关掉题解页面打开你的代码编辑器从零开始实现这道题。过程中你会遇到各种问题“那个状态转移方程的具体下标是什么来着”“二分查找的边界条件到底怎么写”“这个数据结构的具体API怎么用”这时不要直接回去抄题解。而是根据你对思路的理解自己尝试解决。这个过程会强迫你真正理解算法的每一个环节。如果实在想不起来可以快速回看题解的某个局部但看完后要继续独立完成。实现完成后用题解提供的样例和自己构造的边界样例进行测试。3.3 第三步对比分析与优化你的代码AC通过后对比一下你的代码和主流题解或者榜上其他选手的简洁代码有什么区别。代码风格变量命名、函数封装、代码结构是否清晰效率时间复杂度和空间复杂度是否一致有没有可以优化的常数例如用数组代替vector用scanf/printf代替cin/cout处理大量数据。简洁性有没有更优雅的实现方式比如用更少的变量、更巧妙的循环泛化能力这道题的解法能否推广到一类问题例如今天学的“带冷却时间的区间调度DP”其思想是否可以应用到其他带约束的调度问题上3.4 第四步归纳总结与拓展为这道题建立一个简单的笔记记录以下内容题目大意用一句话概括。核心算法/思想例如“线性基处理异或最大值”、“二分答案贪心验证”、“数位DP计数”。关键点/突破口哪一步是最难想到的例如“意识到可以将图上路径问题转化为生成树加非树边环处理”。易错点自己写代码时踩过的坑或者看别人代码时发现的常见错误。类似题目联想之前做过的、或者搜索到的类似题目比较它们的异同。例如做完虚拟赛题D分段非递减可以联想 LeetCode 上的 “分割数组为连续子序列” 等问题。4. 构建个人算法知识体系超越单题补题补题的意义最终要落到构建和巩固你自己的算法知识体系上。一场比赛就像一次体检暴露的是你知识网络中的薄弱环节。专题化整理不要孤立地补题。将类似的题目归类到一起。例如把涉及“线段树优化DP”的题目放在一个文件夹里对比它们状态设计的异同、转移方程的差异、线段树维护的信息有何不同。模板化代码对于非常通用且调试复杂的算法如后缀自动机、动态树Link-Cut Tree、网络流Dinic算法准备一份经过自己大量测试、注释清晰的模板代码。补题时如果用到这些算法直接调用模板把精力集中在问题建模上而不是反复调试模板。思维导图以大的算法分类动态规划、图论、数论、数据结构、字符串、计算几何等为枝干不断填充你遇到过的经典模型、变形和技巧。例如在动态规划下可以有“区间DP”、“树形DP”、“状压DP”、“数位DP”、“概率DP”、“优化单调队列、斜率优化、四边形不等式”等分支。每补一道题就在相应的位置做个标记。定期回顾根据艾宾浩斯遗忘曲线定期回顾你补过的题目和整理的笔记。可以每周抽时间快速浏览一下上周的补题笔记每月对某个专题进行集中复习。你会发现第二次、第三次看同一道题往往会有新的理解。补题是算法竞赛学习中最艰苦也最有效的环节。它逼迫你走出舒适区去直面自己的思维盲区和知识漏洞。把每一次“不会做”都视为一次系统升级的机会把每一篇题解都当成一位高手面对面的指点。坚持下去你会发现那些曾经令你望而生畏的“神题”渐渐变成了你知识体系里一块块坚实的砖瓦。2021“MINIEYE杯”的这场补题如此之后的每一场比赛、每一道难题亦是如此。这个过程没有捷径唯手熟尔唯思考尔。