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; vector<Task> tasks(n+1); // 1-indexed for(int i=1; i<=n; ++i) cin >> tasks[i].s >> tasks[i].e >> tasks[i].v; sort(tasks.begin()+1, tasks.end(), cmp); vector<long long> dp(n+1, 0); vector<long long> end_times(n+1); for(int i=1; i<=n; ++i) end_times[i] = tasks[i].e; for(int i=1; i<=n; ++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进制数后,各位数字的乘积。求∑_{a=0}^{k} ∑_{b=0}^{k} [F(a) + F(b) = F(a+b)]的值,其中[条件]是艾弗森括号,条件成立为1,否则为0。结果对某个大质数取模。
核心难点解析: 此题初看可能让人无从下手,直接枚举a和b是O(k^2),不可行。关键在于理解p进制下数字乘积F(n)的性质,以及等式F(a) + F(b) = F(a+b)在什么情况下成立。
解题脉络重建:
- 分析F(n)的性质:在p进制下,每个数位d满足 0 <= d < p。
F(n)是各数位d的乘积。特别注意,如果任何一位是0,那么F(n)=0。 - 转化等式条件:
F(a) + F(b) = F(a+b)。- 情况一:如果
F(a+b) = 0,那么要求F(a) + F(b) = 0。由于F(x)非负,这意味着必须F(a) = 0且F(b) = 0。 - 情况二:如果
F(a+b) > 0,那么等式要求一个正整数等于另外两个非负整数的和。这看起来更复杂,但结合p进制加法的性质,我们可以发现更深刻的规律。
- 情况一:如果
- 深入探究非零情况:
F(a+b) > 0意味着a+b在p进制下的每一位都不为0。现在考虑p进制加法,它可能产生进位。关键观察是:在没有进位发生的加法中,每一位是独立的,且F(a) + F(b) = F(a+b)几乎不可能成立,除非很多位为1。更严格的分析需要用到Kummer定理的一个相关思想:a+b在p进制下某一位为0,当且仅当该位加法中a和b的对应位之和为p(产生了进位且下一位得到0)。但这指向的是F(a+b)=0的情况。- 实际上,经过更细致的推导(这是补题时需要自己动手做的),可以发现,当
F(a+b) > 0时,要使F(a) + F(b) = F(a+b)成立,条件极为苛刻,可能只存在于a或b非常小(例如0或1)的情况下。我们可以通过暴力枚举小数据来验证这个猜想。
- 实际上,经过更细致的推导(这是补题时需要自己动手做的),可以发现,当
- 问题简化:基于以上分析,我们可以猜测,满足等式的(a, b)对,绝大多数都落在
F(a)=0或F(b)=0或F(a+b)=0的情况里。而F(x)=0当且仅当x在p进制下至少有一位是0。 - 计数方法:
- 总对数:总共有
(k+1)^2对 (a, b)。 - 不满足等式的对数:我们转而计算不满足等式的对数,然后用总数减去。不满足等式,即
F(a) + F(b) != F(a+b)。 - 通过小范围暴力打表,观察规律,可能会发现不满足等式的对数有某种规律,或者满足条件的对数非常少,可以直接枚举所有
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或(a+b)∉S,则F(a),F(b),F(a+b)中至少有一个为0。此时等式F(a)+F(b)=F(a+b)成立的条件非常严格(即三个数中两个为0且第三个也为0,或者类似),我们可以单独分类讨论计数。 - 最复杂的情况是
a∈S,b∈S, 且(a+b)∈S。此时三个F值都非零。这样的三元组 (a, b, a+b) 非常少!我们可以直接枚举S中的a和b,检查a+b <= k且(a+b)∈S,并验证等式是否成立。由于|S|很小,这个枚举是可行的。
- 预处理出所有 0 <= x <= k 且
- 具体计算:
- 令
A0 = {x | 0<=x<=k, F(x)=0},A1 = S = {x | 0<=x<=k, F(x)!=0}。 - 计数满足等式的 (a, b):
- 情况1:
a∈A0且b∈A0。此时F(a)=F(b)=0。等式成立要求F(a+b)=0。这等价于(a+b)∈A0。因此,需要计算有多少对 (a,b) 满足 a,b,a+b 都在A0中。A0是“p进制表示中含有0”的数,这个集合的计数可以通过数位DP来解决:计算 [0, k] 范围内,p进制表示中不含0的数的个数,然后用总数减去得到|A0|。但计算三元组 (a,b,a+b) 都在A0中的数量较为复杂,可能需要再次利用到A0的性质(a+b在A0中概率很高)进行近似或进一步DP。 - 情况2:
a∈A0,b∈A1。等式0 + F(b) = F(a+b)。由于F(b) > 0,这要求F(a+b) = F(b)且F(a+b) > 0。这意味着加法过程不能改变非零数位的乘积,这几乎不可能,除非a=0。所以可能只有a=0时成立。同理a∈A1, b∈A0对称。 - 情况3:
a∈A1, b∈A1。这就是上面提到的,直接枚举S中的元素进行验证。
- 情况1:
- 通过这种分类,我们将问题化简为对几个较小子集的枚举和计算。
- 令
注意:这道题是典型的“分析性质简化问题”+“小范围暴力枚举”的组合。补题时,最大的收获不是最后的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 },其中需要满足条件:第j+1到i这一段的和(记为sum(j+1, i)) >= 上一段(即以j结尾的那段)的和last_sum[j]。
解题脉络重建:
- 朴素DP及瓶颈:直接DP需要O(n^2)的时间,对于n很大(如1e5)的情况会超时。瓶颈在于对于每个i,需要枚举所有可能的j。
- 优化思路:我们需要快速找到,对于当前的i,哪些j是“合法”的(满足
sum(j+1, i) >= last_sum[j]),并在这些合法的j中找到最大的dp[j]。将条件改写:sum(j+1, 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]就是第(k+1)...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的每个元素
x:cur_sum += x。- 如果
cur_sum >= last_sum:segments++。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)。
- 最终方案(二分答案+贪心验证):这是一个更清晰的思路。我们二分答案“段数”K。问题转化为:能否将数组分成K段,使得每段和单调非减。验证时,我们贪心地让前面段的和尽可能小,这样给后面段留出更多空间。具体验证函数
// 虚拟代码框架:二分答案+贪心验证 bool check(int k, vector<long 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,说明还有剩余元素,它们自动成为第k+1段,但我们需要恰好k段。 // 因此,当segments_formed==k时,必须要求start > n,即i>n,没有剩余元素。 return (start > n); } } // 循环结束,数组用完了,但段数没到k return false; } int main() { int n; cin >> n; vector<long long> a(n+1), pref(n+1, 0); for(int i=1; i<=n; ++i) { cin >> a[i]; pref[i] = pref[i-1] + a[i]; } // 二分最大段数 int l = 1, r = n, ans = 1; while(l <= r) { int mid = (l+r)/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或贪心)。
- 知识链接:这道题用到了哪些你已经学过但没想到的算法/数据结构?哪些是新的?把它和你已有的知识体系连接起来。
- 推导过程:题解中的公式、不等式、性质是如何一步步推导出来的?自己动手在草稿纸上跟着推一遍。
- 代码细节:边界条件(循环起止、数组下标)、特殊判断(n=0, n=1)、数据结构初始化等,这些往往是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杯”的这场补题如此,之后的每一场比赛、每一道难题亦是如此。这个过程没有捷径,唯手熟尔,唯思考尔。