1. 一场校赛到底在考什么1.1 从赛题分布看能力考察维度先说说这场校赛的整体印象。第一届程序设计竞赛出题组明显是奔着“摸底选拔”两个目的去的。整场比赛的题目难度梯度拉得很开签到题大概有2到3道属于学完基础语法就能写的水平中间层有4到5道需要一定算法思维和数据结构基础的题最后压轴的1到2道涉及图论、动态规划或者数学推导区分度主要靠这几道题来体现。从知识点覆盖来看大致可以分成这么几类基础模拟与枚举考察代码实现能力不涉及复杂算法但细节容易出错贪心与排序需要发现贪心策略的正确性往往配合排序预处理动态规划线性DP、区间DP或者背包问题的变种图论最短路、最小生成树或者拓扑排序数论与组合数学取模运算、快速幂、组合数计算字符串处理模拟题为主偶尔涉及简单的字符串匹配这种分布其实非常典型。校赛的出题逻辑和区域赛、省赛不一样它首先要保证大部分参赛者能做出题来不能一上来就劝退同时又要让头部选手有足够的发挥空间所以压轴题的质量往往决定了整场比赛的水平上限。1.2 为什么“回顾补题”比比赛本身更重要很多人打完比赛就扔了觉得过了就过了没过的看看题解就完事。这种心态其实浪费了比赛最大的价值。比赛时你是在时间压力下做题思路容易变形很多题即使做出来了解法也未必是最优的。而赛后补题是一个完全没有时间压力的环境你可以慢慢想、反复试、对比不同解法这个过程中学到的东西比比赛那几个小时多得多。我自己的习惯是比赛结束后一周内把没做出来的题全部重新做一遍不看题解先自己想想不出来再去看别人的思路然后自己独立实现一遍。如果实现过程中又卡住了说明这个知识点你其实没真正掌握需要回去补基础。这个流程走下来一道题的价值才能被榨干。2. 补题前的准备工作2.1 环境搭建与模板整理补题之前先把你的代码环境整理好。我见过太多人补题的时候花半小时配环境真正思考的时间反而没多少。建议提前准备好以下几样东西第一一套自己熟悉的代码模板。包括快速输入输出、常用头文件、宏定义、常用算法函数比如快速幂、并查集、gcd等。模板不需要多花哨关键是你要对每一行都熟悉比赛时能直接敲出来不出错。第二一个稳定的本地调试环境。我一般用g配合VS Code配置好调试任务能打断点、能看变量。有些题目逻辑比较复杂光靠打印中间变量效率太低断点调试能省很多时间。第三一个题目归档系统。把每次比赛的题目按知识点分类存好标注难度和掌握程度。下次复习的时候直接按标签筛选效率很高。我用的是简单的Markdown文件加文件夹分类不需要什么高级工具关键是坚持记录。2.2 如何高效阅读题解看题解也是有方法的。很多人看题解就是扫一眼代码看懂了就觉得自己会了然后关掉页面。过两天再遇到类似的题还是不会。正确的做法是先看思路描述不看代码。理解解题的核心思想比如“这道题的关键是把问题转化为二分答案”自己尝试实现。根据思路自己写代码遇到卡住的地方再回去看题解的细节对比代码风格。看题解的代码和自己的实现有什么不同哪些地方更简洁、更高效总结可复用的模式。这道题用到的技巧能不能迁移到其他题目上注意看题解不是抄代码。抄一遍代码除了让你手指累之外没有任何作用。关键是理解思路然后用自己的方式实现。3. 典型题目类型与解题思路拆解3.1 模拟题细节决定成败模拟题是校赛里最常见的题型也是很多人最容易翻车的题型。因为模拟题不涉及复杂算法大家觉得自己都会但真正写起来各种边界条件、特殊情况能把人逼疯。拿一道典型的模拟题来说比如“日期计算”类的题目给定两个日期计算它们之间相差多少天。看起来很简单对吧但你需要考虑闰年的判断规则能被4整除但不能被100整除或者能被400整除每个月的天数不同跨年、跨月的情况输入格式是否规范我补这类题的时候习惯先把所有特殊情况列出来写成一个检查清单然后逐条验证。比如上面这道日期题我会构造这些测试用例测试场景输入示例预期输出考察点同年同月2023-01-01 到 2023-01-1514基本计算跨月不跨年2023-01-15 到 2023-03-1054月份天数跨年2022-12-25 到 2023-01-0511跨年处理闰年2月2020-02-28 到 2020-03-012闰年判断整年2022-01-01 到 2023-01-01365非闰年这样列出来之后写代码的时候心里就有底了每写完一个逻辑分支就对照测试用例验证一下。3.2 贪心算法证明比实现更重要贪心题的特点是代码通常很短但想清楚为什么这样贪心是对的往往需要花很长时间。校赛里的贪心题一般不会特别难常见的套路有排序后贪心比如区间调度问题按结束时间排序优先队列贪心比如合并果子问题每次取最小的两个相邻交换贪心通过分析相邻元素的交换对结果的影响来确定排序规则我印象比较深的一道题是“排队接水”的变种有n个人排队接水每个人接水时间不同如何安排顺序使所有人的平均等待时间最小。标准解法是按接水时间从小到大排序这个结论大家都知道但为什么是对的简单证明一下假设有两个人A和B接水时间分别为a和b且a b。如果A排在B前面总等待时间为a (ab) 2ab如果B排在A前面总等待时间为b (ab) a2b。因为a b所以2ab a2b即A排在前面更优。这个结论可以推广到n个人所以按时间从小到大排序是最优的。补题的时候每道贪心题我都会尝试写出证明过程。如果证不出来说明我对这道题的理解还不够深需要再想想。3.3 动态规划从状态定义开始DP是校赛区分度最高的题型之一。很多人在补DP题的时候直接看题解的状态转移方程然后照着写一遍就完事了。但下次遇到新题还是不会定义状态。问题出在哪里出在你没有理解“为什么这样定义状态”。DP的核心是状态定义和状态转移。状态定义决定了你能不能用最优子结构来求解状态转移决定了你的时间复杂度。我补DP题的时候会按这个顺序来思考这道题要求什么是求方案数、最大值、最小值还是可行性影响答案的因素有哪些这些因素就是状态的维度当前状态可以由哪些更小的状态推导出来这就是状态转移边界条件是什么最小规模的问题答案是什么计算顺序是什么是从小到大递推还是用记忆化搜索举个例子经典的01背包问题n个物品每个物品有重量w和价值v背包容量为W求能装下的最大价值。状态定义是dp[i][j]表示前i个物品在容量j下的最大价值。为什么这样定义因为“前i个物品”和“容量j”是影响答案的两个因素。状态转移是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])分别对应不选第i个物品和选第i个物品两种情况。补题的时候我会把每道DP题的思考过程写下来包括状态定义的理由、转移方程的推导、边界条件的确定。这样积累下来遇到新题的时候就有章可循了。3.4 图论建图是第一步图论题在校赛中一般出现在中高难度位置。很多图论题的难点不在算法本身而在如何把问题转化为图论模型。比如“判断是否有环”可以转化为拓扑排序“最短路径”可以转化为Dijkstra或Bellman-Ford“连通性”可以转化为并查集或DFS。补图论题的时候我习惯先画图。把题目中的关系用节点和边表示出来然后看这个图有什么性质是有向图还是无向图有没有负权边有没有环根据这些性质选择合适的算法。图的性质适用算法时间复杂度无权图最短路BFSO(VE)非负权最短路DijkstraO((VE)logV)含负权最短路Bellman-FordO(VE)多源最短路FloydO(V^3)最小生成树Kruskal/PrimO(ElogE) / O(V^2)连通分量并查集/DFSO(VE)这张表不是让你背的而是让你在补题的时候对照着看这道题属于哪种情况我选的算法对不对有没有更优的选择4. 补题实战从零到AC的完整过程4.1 题目分析与建模假设我们拿到这样一道题给定一个n个点m条边的无向图每条边有一个权值求从1号点到n号点的所有路径中路径上最大边权的最小值。首先分析题目要求不是求最短路而是求“最大边权的最小值”。这个表述有点绕换个说法找一条从1到n的路径使得这条路径上权值最大的那条边的权值尽可能小。这种问题有一个经典的解法二分答案并查集。二分枚举最大边权的值然后判断只保留权值不超过该值的边1和n是否连通。如果连通说明这个答案可行尝试更小的值如果不连通说明答案需要更大。为什么可以用二分因为如果最大边权为x时可行那么最大边权大于x时也一定可行边更多了连通性不会变差。这就是单调性是二分的前提。4.2 代码实现与调试#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN]; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ! ry) parent[rx] ry; } struct Edge { int u, v, w; }; int main() { int n, m; cin n m; vectorEdge edges(m); int maxW 0; for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; maxW max(maxW, edges[i].w); } int lo 0, hi maxW, ans maxW; while (lo hi) { int mid (lo hi) / 2; // 初始化并查集 for (int i 1; i n; i) parent[i] i; // 只加入权值不超过mid的边 for (auto e : edges) { if (e.w mid) unite(e.u, e.v); } if (find(1) find(n)) { ans mid; hi mid - 1; } else { lo mid 1; } } cout ans endl; return 0; }这段代码的逻辑很清晰二分答案每次用并查集判断连通性。时间复杂度是O((nm)log(maxW))对于n和m在10^5级别的数据完全够用。调试的时候我遇到了两个问题一是并查集的初始化必须在每次二分之前做不能只在最开始做一次二是二分的边界条件lo和hi的初始值以及更新方式需要仔细确认。这两个问题都是写代码时容易忽略的细节但在补题的时候正好可以慢慢调试加深印象。4.3 复杂度分析与优化空间上面这个解法的时间复杂度是O((nm)log(maxW))。如果maxW特别大比如10^9二分的次数大约是30次每次需要O(nm)的时间来建并查集总时间大约是30*(nm)对于10^5的数据量来说是可以接受的。有没有更优的解法其实这道题还可以用最小生成树来做。因为最小生成树有一个性质任意两点之间的路径上最大边权是所有路径中最小的。所以只需要求最小生成树然后找1到n路径上的最大边权即可。这个解法的时间复杂度是O(m log m)比二分并查集更优。补题的时候我会把两种解法都实现一遍对比它们的优缺点。这样不仅加深了对题目的理解也复习了最小生成树的性质。5. 常见问题与排查技巧实录5.1 补题过程中最容易踩的坑补题的时候我踩过不少坑这里整理几个最常见的第一个坑只看题解不自己写。这个前面说过了看懂了和写出来是两回事。很多时候你以为自己懂了一写代码就发现各种问题。第二个坑不重视边界条件。比如数组越界、整数溢出、特殊情况n0或n1没有处理。这些在比赛时可能因为时间压力被忽略但补题的时候一定要补上。第三个坑不分析复杂度。有些题目的暴力解法在小数据下能过但大数据下会超时。补题的时候要养成分析时间复杂度的习惯确保自己的解法在题目给定的数据范围内是可行的。第四个坑不总结。补完一道题就扔了没有记录解题思路和关键点。过一段时间再遇到类似的题还是不会。建议每道题补完之后写一个简短的总结记录核心思路、易错点和可复用的技巧。5.2 调试技巧速查表问题类型排查方法常用工具答案错误构造小数据手动模拟打印中间变量超时分析时间复杂度计时函数运行时错误检查数组越界、除零调试器断点死循环检查循环条件和更新逻辑打印循环变量精度问题检查浮点数比较方式eps容差比较提示构造测试数据的时候优先构造边界数据最小值、最大值、特殊值这些数据最容易暴露问题。5.3 从补题到举一反三补题的最终目的不是会做这一道题而是掌握一类题的解法。每补完一道题我会问自己三个问题这道题的核心技巧是什么能不能用一句话概括这个技巧还能用在哪些类似的题目上如果题目条件变一下解法需要怎么调整比如上面那道“最大边权最小值”的题核心技巧是“二分答案连通性判断”。这个技巧还可以用在很多地方比如“最小化最大值”类问题、“最大化最小值”类问题。掌握了这个模式遇到类似的题目就能快速找到思路。6. 赛后复盘与长期提升6.1 建立自己的知识体系补题不是孤立的每道题都是一个知识点网络中的节点。我习惯用思维导图把知识点串起来比如数据结构数组、链表、栈、队列、树、图、并查集、线段树算法排序、二分、贪心、DP、图论、数论、字符串技巧前缀和、差分、双指针、滑动窗口、位运算每补一道题就在对应的知识点下面记录这道题的解题思路和关键点。时间长了这个知识体系会越来越完善遇到新题的时候就能快速定位到相关的知识点。6.2 定期复习与模拟训练补过的题如果不复习过一段时间就会忘。我的做法是每隔一个月左右把之前补过的题重新做一遍。不需要全部重做挑那些当时觉得有难度的、或者解法比较巧妙的题。如果还能独立做出来说明确实掌握了如果做不出来说明需要再补一遍。另外定期参加一些模拟赛也很重要。模拟赛能帮你保持比赛状态训练时间分配和心态调整。我一般每周会打一场模拟赛赛后同样进行补题和总结。6.3 从校赛到更高层次的准备校赛只是一个起点。如果你在校赛中表现不错接下来可以准备省赛、区域赛甚至更高层次的比赛。这些比赛的题目难度会明显提升涉及的知识点也更广。但核心的补题方法和学习思路是一样的做题、补题、总结、复习循环往复。我自己的经验是从校赛水平到省赛水平大概需要补100到200道高质量的题目。这些题目不需要多难但一定要覆盖各个知识点并且每道题都要真正理解透彻。从省赛到区域赛可能需要再补200到300道题并且开始接触一些高级数据结构和算法。这个过程没有捷径但每一步的积累都是实实在在的。你在补题上花的每一分钟都会在未来的比赛中体现出来。最后分享一个小技巧补题的时候可以找一个水平差不多的队友一起补。两个人互相讲题、互相出测试数据、互相检查代码效率会比一个人高很多。而且讲题的过程本身就是在加深理解很多时候你以为自己懂了一讲出来才发现逻辑有漏洞。找到一个靠谱的补题搭档比什么学习方法都管用。
1. 一场校赛到底在考什么1.1 从赛题分布看能力考察维度先说说这场校赛的整体印象。第一届程序设计竞赛出题组明显是奔着“摸底选拔”两个目的去的。整场比赛的题目难度梯度拉得很开签到题大概有2到3道属于学完基础语法就能写的水平中间层有4到5道需要一定算法思维和数据结构基础的题最后压轴的1到2道涉及图论、动态规划或者数学推导区分度主要靠这几道题来体现。从知识点覆盖来看大致可以分成这么几类基础模拟与枚举考察代码实现能力不涉及复杂算法但细节容易出错贪心与排序需要发现贪心策略的正确性往往配合排序预处理动态规划线性DP、区间DP或者背包问题的变种图论最短路、最小生成树或者拓扑排序数论与组合数学取模运算、快速幂、组合数计算字符串处理模拟题为主偶尔涉及简单的字符串匹配这种分布其实非常典型。校赛的出题逻辑和区域赛、省赛不一样它首先要保证大部分参赛者能做出题来不能一上来就劝退同时又要让头部选手有足够的发挥空间所以压轴题的质量往往决定了整场比赛的水平上限。1.2 为什么“回顾补题”比比赛本身更重要很多人打完比赛就扔了觉得过了就过了没过的看看题解就完事。这种心态其实浪费了比赛最大的价值。比赛时你是在时间压力下做题思路容易变形很多题即使做出来了解法也未必是最优的。而赛后补题是一个完全没有时间压力的环境你可以慢慢想、反复试、对比不同解法这个过程中学到的东西比比赛那几个小时多得多。我自己的习惯是比赛结束后一周内把没做出来的题全部重新做一遍不看题解先自己想想不出来再去看别人的思路然后自己独立实现一遍。如果实现过程中又卡住了说明这个知识点你其实没真正掌握需要回去补基础。这个流程走下来一道题的价值才能被榨干。2. 补题前的准备工作2.1 环境搭建与模板整理补题之前先把你的代码环境整理好。我见过太多人补题的时候花半小时配环境真正思考的时间反而没多少。建议提前准备好以下几样东西第一一套自己熟悉的代码模板。包括快速输入输出、常用头文件、宏定义、常用算法函数比如快速幂、并查集、gcd等。模板不需要多花哨关键是你要对每一行都熟悉比赛时能直接敲出来不出错。第二一个稳定的本地调试环境。我一般用g配合VS Code配置好调试任务能打断点、能看变量。有些题目逻辑比较复杂光靠打印中间变量效率太低断点调试能省很多时间。第三一个题目归档系统。把每次比赛的题目按知识点分类存好标注难度和掌握程度。下次复习的时候直接按标签筛选效率很高。我用的是简单的Markdown文件加文件夹分类不需要什么高级工具关键是坚持记录。2.2 如何高效阅读题解看题解也是有方法的。很多人看题解就是扫一眼代码看懂了就觉得自己会了然后关掉页面。过两天再遇到类似的题还是不会。正确的做法是先看思路描述不看代码。理解解题的核心思想比如“这道题的关键是把问题转化为二分答案”自己尝试实现。根据思路自己写代码遇到卡住的地方再回去看题解的细节对比代码风格。看题解的代码和自己的实现有什么不同哪些地方更简洁、更高效总结可复用的模式。这道题用到的技巧能不能迁移到其他题目上注意看题解不是抄代码。抄一遍代码除了让你手指累之外没有任何作用。关键是理解思路然后用自己的方式实现。3. 典型题目类型与解题思路拆解3.1 模拟题细节决定成败模拟题是校赛里最常见的题型也是很多人最容易翻车的题型。因为模拟题不涉及复杂算法大家觉得自己都会但真正写起来各种边界条件、特殊情况能把人逼疯。拿一道典型的模拟题来说比如“日期计算”类的题目给定两个日期计算它们之间相差多少天。看起来很简单对吧但你需要考虑闰年的判断规则能被4整除但不能被100整除或者能被400整除每个月的天数不同跨年、跨月的情况输入格式是否规范我补这类题的时候习惯先把所有特殊情况列出来写成一个检查清单然后逐条验证。比如上面这道日期题我会构造这些测试用例测试场景输入示例预期输出考察点同年同月2023-01-01 到 2023-01-1514基本计算跨月不跨年2023-01-15 到 2023-03-1054月份天数跨年2022-12-25 到 2023-01-0511跨年处理闰年2月2020-02-28 到 2020-03-012闰年判断整年2022-01-01 到 2023-01-01365非闰年这样列出来之后写代码的时候心里就有底了每写完一个逻辑分支就对照测试用例验证一下。3.2 贪心算法证明比实现更重要贪心题的特点是代码通常很短但想清楚为什么这样贪心是对的往往需要花很长时间。校赛里的贪心题一般不会特别难常见的套路有排序后贪心比如区间调度问题按结束时间排序优先队列贪心比如合并果子问题每次取最小的两个相邻交换贪心通过分析相邻元素的交换对结果的影响来确定排序规则我印象比较深的一道题是“排队接水”的变种有n个人排队接水每个人接水时间不同如何安排顺序使所有人的平均等待时间最小。标准解法是按接水时间从小到大排序这个结论大家都知道但为什么是对的简单证明一下假设有两个人A和B接水时间分别为a和b且a b。如果A排在B前面总等待时间为a (ab) 2ab如果B排在A前面总等待时间为b (ab) a2b。因为a b所以2ab a2b即A排在前面更优。这个结论可以推广到n个人所以按时间从小到大排序是最优的。补题的时候每道贪心题我都会尝试写出证明过程。如果证不出来说明我对这道题的理解还不够深需要再想想。3.3 动态规划从状态定义开始DP是校赛区分度最高的题型之一。很多人在补DP题的时候直接看题解的状态转移方程然后照着写一遍就完事了。但下次遇到新题还是不会定义状态。问题出在哪里出在你没有理解“为什么这样定义状态”。DP的核心是状态定义和状态转移。状态定义决定了你能不能用最优子结构来求解状态转移决定了你的时间复杂度。我补DP题的时候会按这个顺序来思考这道题要求什么是求方案数、最大值、最小值还是可行性影响答案的因素有哪些这些因素就是状态的维度当前状态可以由哪些更小的状态推导出来这就是状态转移边界条件是什么最小规模的问题答案是什么计算顺序是什么是从小到大递推还是用记忆化搜索举个例子经典的01背包问题n个物品每个物品有重量w和价值v背包容量为W求能装下的最大价值。状态定义是dp[i][j]表示前i个物品在容量j下的最大价值。为什么这样定义因为“前i个物品”和“容量j”是影响答案的两个因素。状态转移是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])分别对应不选第i个物品和选第i个物品两种情况。补题的时候我会把每道DP题的思考过程写下来包括状态定义的理由、转移方程的推导、边界条件的确定。这样积累下来遇到新题的时候就有章可循了。3.4 图论建图是第一步图论题在校赛中一般出现在中高难度位置。很多图论题的难点不在算法本身而在如何把问题转化为图论模型。比如“判断是否有环”可以转化为拓扑排序“最短路径”可以转化为Dijkstra或Bellman-Ford“连通性”可以转化为并查集或DFS。补图论题的时候我习惯先画图。把题目中的关系用节点和边表示出来然后看这个图有什么性质是有向图还是无向图有没有负权边有没有环根据这些性质选择合适的算法。图的性质适用算法时间复杂度无权图最短路BFSO(VE)非负权最短路DijkstraO((VE)logV)含负权最短路Bellman-FordO(VE)多源最短路FloydO(V^3)最小生成树Kruskal/PrimO(ElogE) / O(V^2)连通分量并查集/DFSO(VE)这张表不是让你背的而是让你在补题的时候对照着看这道题属于哪种情况我选的算法对不对有没有更优的选择4. 补题实战从零到AC的完整过程4.1 题目分析与建模假设我们拿到这样一道题给定一个n个点m条边的无向图每条边有一个权值求从1号点到n号点的所有路径中路径上最大边权的最小值。首先分析题目要求不是求最短路而是求“最大边权的最小值”。这个表述有点绕换个说法找一条从1到n的路径使得这条路径上权值最大的那条边的权值尽可能小。这种问题有一个经典的解法二分答案并查集。二分枚举最大边权的值然后判断只保留权值不超过该值的边1和n是否连通。如果连通说明这个答案可行尝试更小的值如果不连通说明答案需要更大。为什么可以用二分因为如果最大边权为x时可行那么最大边权大于x时也一定可行边更多了连通性不会变差。这就是单调性是二分的前提。4.2 代码实现与调试#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN]; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unite(int x, int y) { int rx find(x), ry find(y); if (rx ! ry) parent[rx] ry; } struct Edge { int u, v, w; }; int main() { int n, m; cin n m; vectorEdge edges(m); int maxW 0; for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; maxW max(maxW, edges[i].w); } int lo 0, hi maxW, ans maxW; while (lo hi) { int mid (lo hi) / 2; // 初始化并查集 for (int i 1; i n; i) parent[i] i; // 只加入权值不超过mid的边 for (auto e : edges) { if (e.w mid) unite(e.u, e.v); } if (find(1) find(n)) { ans mid; hi mid - 1; } else { lo mid 1; } } cout ans endl; return 0; }这段代码的逻辑很清晰二分答案每次用并查集判断连通性。时间复杂度是O((nm)log(maxW))对于n和m在10^5级别的数据完全够用。调试的时候我遇到了两个问题一是并查集的初始化必须在每次二分之前做不能只在最开始做一次二是二分的边界条件lo和hi的初始值以及更新方式需要仔细确认。这两个问题都是写代码时容易忽略的细节但在补题的时候正好可以慢慢调试加深印象。4.3 复杂度分析与优化空间上面这个解法的时间复杂度是O((nm)log(maxW))。如果maxW特别大比如10^9二分的次数大约是30次每次需要O(nm)的时间来建并查集总时间大约是30*(nm)对于10^5的数据量来说是可以接受的。有没有更优的解法其实这道题还可以用最小生成树来做。因为最小生成树有一个性质任意两点之间的路径上最大边权是所有路径中最小的。所以只需要求最小生成树然后找1到n路径上的最大边权即可。这个解法的时间复杂度是O(m log m)比二分并查集更优。补题的时候我会把两种解法都实现一遍对比它们的优缺点。这样不仅加深了对题目的理解也复习了最小生成树的性质。5. 常见问题与排查技巧实录5.1 补题过程中最容易踩的坑补题的时候我踩过不少坑这里整理几个最常见的第一个坑只看题解不自己写。这个前面说过了看懂了和写出来是两回事。很多时候你以为自己懂了一写代码就发现各种问题。第二个坑不重视边界条件。比如数组越界、整数溢出、特殊情况n0或n1没有处理。这些在比赛时可能因为时间压力被忽略但补题的时候一定要补上。第三个坑不分析复杂度。有些题目的暴力解法在小数据下能过但大数据下会超时。补题的时候要养成分析时间复杂度的习惯确保自己的解法在题目给定的数据范围内是可行的。第四个坑不总结。补完一道题就扔了没有记录解题思路和关键点。过一段时间再遇到类似的题还是不会。建议每道题补完之后写一个简短的总结记录核心思路、易错点和可复用的技巧。5.2 调试技巧速查表问题类型排查方法常用工具答案错误构造小数据手动模拟打印中间变量超时分析时间复杂度计时函数运行时错误检查数组越界、除零调试器断点死循环检查循环条件和更新逻辑打印循环变量精度问题检查浮点数比较方式eps容差比较提示构造测试数据的时候优先构造边界数据最小值、最大值、特殊值这些数据最容易暴露问题。5.3 从补题到举一反三补题的最终目的不是会做这一道题而是掌握一类题的解法。每补完一道题我会问自己三个问题这道题的核心技巧是什么能不能用一句话概括这个技巧还能用在哪些类似的题目上如果题目条件变一下解法需要怎么调整比如上面那道“最大边权最小值”的题核心技巧是“二分答案连通性判断”。这个技巧还可以用在很多地方比如“最小化最大值”类问题、“最大化最小值”类问题。掌握了这个模式遇到类似的题目就能快速找到思路。6. 赛后复盘与长期提升6.1 建立自己的知识体系补题不是孤立的每道题都是一个知识点网络中的节点。我习惯用思维导图把知识点串起来比如数据结构数组、链表、栈、队列、树、图、并查集、线段树算法排序、二分、贪心、DP、图论、数论、字符串技巧前缀和、差分、双指针、滑动窗口、位运算每补一道题就在对应的知识点下面记录这道题的解题思路和关键点。时间长了这个知识体系会越来越完善遇到新题的时候就能快速定位到相关的知识点。6.2 定期复习与模拟训练补过的题如果不复习过一段时间就会忘。我的做法是每隔一个月左右把之前补过的题重新做一遍。不需要全部重做挑那些当时觉得有难度的、或者解法比较巧妙的题。如果还能独立做出来说明确实掌握了如果做不出来说明需要再补一遍。另外定期参加一些模拟赛也很重要。模拟赛能帮你保持比赛状态训练时间分配和心态调整。我一般每周会打一场模拟赛赛后同样进行补题和总结。6.3 从校赛到更高层次的准备校赛只是一个起点。如果你在校赛中表现不错接下来可以准备省赛、区域赛甚至更高层次的比赛。这些比赛的题目难度会明显提升涉及的知识点也更广。但核心的补题方法和学习思路是一样的做题、补题、总结、复习循环往复。我自己的经验是从校赛水平到省赛水平大概需要补100到200道高质量的题目。这些题目不需要多难但一定要覆盖各个知识点并且每道题都要真正理解透彻。从省赛到区域赛可能需要再补200到300道题并且开始接触一些高级数据结构和算法。这个过程没有捷径但每一步的积累都是实实在在的。你在补题上花的每一分钟都会在未来的比赛中体现出来。最后分享一个小技巧补题的时候可以找一个水平差不多的队友一起补。两个人互相讲题、互相出测试数据、互相检查代码效率会比一个人高很多。而且讲题的过程本身就是在加深理解很多时候你以为自己懂了一讲出来才发现逻辑有漏洞。找到一个靠谱的补题搭档比什么学习方法都管用。
