寒假还没开始的时候我就在朋友圈立了Flag这个假期要把 Acwing 算法基础课完整过一遍。当时很多人觉得我疯了——好不容易放假不休息还给自己上强度。但实际情况是我前半年在 LeetCode 上断断续续刷了两百多道题每次一看到陌生的题型就懵知识点完全是散的。后来我才意识到问题不是刷题量不够而是缺少一套系统的算法骨架。Acwing 算法基础课恰好就是干这个的它不教奇技淫巧而是把排序、二分、数据结构、搜索与图论、动态规划这些核心专题按竞赛选手的训练逻辑重新组织了一遍。这篇文章把我那段寒假学习经历的完整复盘写出来包括课程怎么安排、每个章节怎么学、哪些地方最容易卡壳、怎么排查问题给准备蓝桥杯、考研机试或者单纯想系统补算法底子的同学做个参考。1. 为什么我选了 Acwing 算法基础课作为寒假主攻方向1.1 课程内容与寒假场景的匹配度先说结论寒假学算法最理想的不是找一堆零散视频而是选一条有明确章节和配套题单的完整课程。原因很简单假期只有二十几天如果今天看排序、明天看图论、后天刷几道随机题最后大概率什么都没留下。Acwing 算法基础课的章节设置我大致梳理了一下主线非常清晰基础算法、数据结构、搜索与图论、数学知识、动态规划、贪心。这个顺序本身是有讲究的——先打底子再学结构然后进入搜索图论这种偏思维的模块最后才是动态规划和数学。它不是按难度从低到高排的而是按依赖关系排的不上完前缀和与差分后面很多区间操作题会看不懂不掌握单调栈和单调队列后面学滑动窗口、直方图最大矩形就会很痛苦。我当时给自己定了一个目标节奏每天固定三个小时听课加两小时刷题周末可以休息半天。合理的课程体量配上固定的时间表才可能在一个假期里真正吃透一轮。1.2 课程之外的学习闭环听课、刷题、模板总结一样不能少光听课是不可能学会算法的。Acwing 的课程设计好在每一节后面直接挂在对应的题目上你学完一个知识点马上去做配套习题趁热打铁。我在实际操作中的体验是听课只占整个学习时间的四成左右剩下的时间全在写代码、调 bug 和整理模板。我的完整闭环是这样的先以 1.5 倍速把视频过一遍理解思路、记好模板然后立刻打开题目列表做当天对应专题的题做完之后把每道题的思路、边界条件、易错点写进一个 Markdown 笔记文件里。这件事看起来笨但效果极好。两三天后回看笔记时往往能发现当时记下来的很多坑现在看根本不用踩。提示别急着追求把每个题目背下来算法基础课的价值在于建立条件反射——看到一道题先能判断它属于哪个专题再能回忆起对应的模板框架。这个判断能力比硬背代码重要得多。2. 基础算法章节的核心细节与实操要点2.1 排序与二分从找规律到形成肌肉记忆基础算法这一章开始就是快速排序和归并排序。很多人觉得排序有什么好学的其实排序在竞赛里不是给数据排个序那么简单重点在两个延伸应用快排的 partition 思想以及归并排序的合并过程。归并排序有一个极其高频的考点——求逆序对数量。原理就是归并的两个序列各自已经有序当左边序列的当前元素大于右边序列的当前元素时左边序列剩余的所有元素都大于这个右边元素逆序对数量直接累加。我第一次看到这个解法时觉得这是整章里最有灵气的一个知识点因为它把排序过程本身变成了计算工具而不只是整理数据。二分是这章最容易阴沟翻船的地方。整数二分的边界问题真的能把人折磨到怀疑人生。我总结出来的实用规律是// 找左边界相当于把区间向右压缩 int l 0, r n - 1; while (l r) { int mid l r 1; if (check(mid)) r mid; else l mid 1; } // 找右边界相当于把区间向左压缩 int l 0, r n - 1; while (l r) { int mid l r 1 1; if (check(mid)) l mid; else r mid - 1; }为什么求右边界时 mid 要加一这里涉及一个很关键的问题如果不加一当 l 和 r 只差 1 时l r 1取到的是 l如果此时 check(mid) 为真l 保持不变l mid就等于没动死循环就出现了。加了 1 之后再取整mid 会偏向右边l mid才能把区间真正压过去。很多初学者第一次死循环就死在这搞懂这个原因比背模板重要得多。2.2 前缀和、差分、双指针为什么它们才是真正的基本功如果说排序和二分的地位是常用工具那前缀和与差分就是底层基础设施。前缀和的核心就一句话用 O(n) 的预处理换取 O(1) 的区间查询。for (int i 1; i n; i) s[i] s[i - 1] a[i]; // 查询 [l, r] 的和s[r] - s[l - 1]这个式子有个细节数组下标从 1 开始s[0] 保持为 0。这样写的好处是查询时不需要特殊处理 l1 的情况这就是我从代码里总结出的经验处理前缀和这类问题从 1 开始存数据能省掉一半的边界特判。差分是前缀和的逆运算。比如要给 [l, r] 区间内所有数加 c只需要操作两个端点b[l] c; b[r 1] - c;全部操作完成后再做一遍前缀和就得到了最终的数组。我第一次学这个的时候觉得怎么可能这么简单后来才发现树状数组、线段树里的区间修改思想源头都能追溯到差分这个朴素的想法上。把这十几行代码吃透后面学复杂数据结构的时候会顺很多。双指针算法则是把嵌套循环 O(n^2) 降成 O(n) 的那把钥匙。经典的最长不重复子序列问题右指针不断向前扫描扩展窗口左指针在窗口内出现重复字符时收缩。看起来只是把两个循环合在一起但精髓在于利用了单调性——左指针只会向右移动不会回头因此均摊下来每个元素只被访问固定次数。理解这个均摊逻辑比记住模板要有用。2.3 高精度、位运算、离散化这些小知识点为什么不能跳过高精度加减乘除在竞赛里是一种看着会、写起来全是坑的题。我的建议是大数用vectorint存低位在前也就是把个位存在下标 0 的位置。这样做的最大好处是两个数做加法时对齐的难度大幅下降所有的进位都只需要在尾部 push_back。当初我第一次写高精度减法时比较两个数大小的操作写在了函数里结果因为符号判断错误调了整整一个小时。后来我总结出一个铁律高精度减法的第一步永远是判断谁大谁小决定要不要在前面加负号再做逐位减法。位运算这个知识点单独讲很枯燥但它的应用非常广泛求一个数的二进制表示、判断奇偶、用 lowbit 操作统计二进制中 1 的个数甚至状态压缩 DP 的全套基础都靠位运算支撑。推荐把每个位运算操作与、或、异或、左移、右移、取反单独写一段测试代码把常见位模式跑一遍比看十遍文档都管用。离散化是我这个假期最开始忽略、后来发现很实用的技巧。它解决的核心问题是数据的值域很大但个数很少比如坐标范围到 10^9 但只有 10^5 个点这时不能直接开数组需要把这些值重新映射到连续的地址空间。实现方法就是排序加去重然后对原数据逐一二分查找映射后的新下标。配合前缀和做区间查询时这套组合拳非常高频务必在小本本上记下来。3. 数据结构章节怎么学才不会背了又忘3.1 单调栈与单调队列理解背后的单调性思想数据结构从单链表、双链表开始这些在竞赛里一般不直接考链表操作而是作为模拟的基础。紧接着就进入了第一章的高潮部分单调栈和单调队列。单调栈的经典题是找到每个数左边第一个比它小的数。暴力肯定是双重循环但单调栈的精妙之处在于维护一个从栈底到栈顶递增的序列每次新元素入栈前把所有比它大或等于它的元素弹出因为这些元素在它面前已经不可能再作为左边第一个更小的候选。每个元素入栈一次、出栈最多一次总复杂度就成了 O(n)。单调队列和单调栈的区别在于栈只能从尾部进出队列还能从头部弹出所以单调队列天然适合处理滑动窗口问题队头是当前窗口内的最优值窗口滑动时把过期的元素从队头弹掉。注意刚学这两个结构时千万别急着背代码先画一个数组手动用纸笔模拟一遍入栈、出栈的每一步搞清楚牺牲了什么、得到了什么。单调栈牺牲了部分元素的右侧视野换来的是一遍扫描就能得到所有答案的高效率理解了这个交换逻辑才能举一反三。3.2 KMP、Trie、并查集从原理到背出稳定模板KMP 算法是很多人数据结构部分的第一道坎。它的核心是一场自我匹配构造 next 数组时模式串的每个位置都在和它自身比较。我个人的学习方法是先不看任何推导直接手写一个模式串 ABABCAB把 next 数组手工推一遍然后再去看课程里的解释瞬间就通了。这里贴一个我在用的 KMP 模板配合注释理解// 模式串 p下标从 1 开始 for (int i 2, j 0; i m; i) { while (j p[i] ! p[j 1]) j ne[j]; if (p[i] p[j 1]) j; ne[i] j; } // 文本串 s 的匹配 for (int i 1, j 0; i n; i) { while (j s[i] ! p[j 1]) j ne[j]; if (s[i] p[j 1]) j; if (j m) { // 匹配成功起点为 i - m 1 j ne[j]; } }这套模板的细节在于循环变量从 2 开始ne[1] 默认是 0以及匹配成功后 j 回退到 ne[j] 以便继续找下一个匹配位置。把这三处置对KMP 基本就稳了。Trie 树处理字符串前缀相关的查询非常直接本质就是一棵按字符分叉的多叉树。并查集则是处理连通性问题的神器。并查集的代码极短但有一个很容易忽略的点是路径压缩一定写在 find 函数里每次查找的同时把路径上的节点直接挂到根节点上int find(int x) { if (p[x] ! x) p[x] find(p[x]); return p[x]; }如果不压缩路径并查集在极端数据下会退化成一条链查找复杂度变成 O(n)。另外并查集还能维护集合大小、到根节点的距离这些扩展用法在后面处理带权并查集时会用到。3.3 哈希表和 STL 的边界问题这章最后讲哈希表和 C STL。哈希表在竞赛里的应用主要有两个一是字符串哈希借助前缀哈希在 O(1) 时间内比较任意子串是否相等二是直接用unordered_map做映射。我踩过的一个典型坑是使用map时时间复杂度会多个 log数据量一大就超时换成unordered_map才过。反过来如果题目故意构造哈希冲突数据unordered_map反而可能被卡这时需要自己写哈希函数或者改用map。这种取舍没有固定答案必须在做题中积累经验。STL 部分我建议把所有常用容器、常用算法接口过一遍重点练习vector 的遍历、stack 和 queue 的 pop 返回值问题、priority_queue 默认是大根堆、pair 的排序规则。这些小东西不难但考试时想不起接口才是致命的。4. 搜索与图论寒假最容易卡壳的部分4.1 DFS 与 BFS 的分工与转化搜索与图论章节从 DFS 和 BFS 开始。DFS 天然适用于有多少种方案某个路径是否存在这类问题它的代码结构非常统一进入递归前做状态标记递归返回后撤销标记。这个回溯动作是 DFS 的灵魂少了它所有方案之间就会互相污染。BFS 则适用于最少步数最短距离这类问题。BFS 的队列操作和 Dijkstra 算法的雏形高度相关理解了 BFS 的层序遍历后面学最短路算法会轻松得多。剪枝是 DFS 的精华。比如在八皇后或排列类问题中提前判断当前放置是否合法不合法直接减掉整个子树能不递归就不递归。暴力枚举算法和剪枝算法往往是一套组合拳先用枚举定出搜索树再用剪枝把搜索树砍掉大部分叶子。我学这章时的体会是DFS 模板很好背难的是想清楚什么时候要回溯什么时候不要回溯。比如排列问题需要回溯因为每个选择是互斥的而迷宫是否可达类问题有时只需要访问标记不需要回溯因为每条路径独立探索、不需要恢复现场。4.2 最短路算法的选型逻辑图论的重头戏是四种最短路算法Dijkstra、Bellman-Ford、SPFA、Floyd。基础课会把这些算法按单源正权、单源负权、多源分类但实际做题时选哪个算法更关键的是看数据范围和题目性质。我的选型逻辑是这样的场景推荐算法时间复杂度注意事项稠密图、单源、正权边朴素 DijkstraO(n²)适合点数量级在几千以内稀疏图、单源、正权边堆优化 DijkstraO(m log n)最常用的单源最短路方案单源、含负权边Bellman-Ford 或 SPFAO(nm) 或 O(km)有负环时 Bellman-Ford 更可靠多源、点数很小FloydO(n³)实现简单适合 n ≤ 500堆优化 Dijkstra 的核心是把找当前距离最小点这件事交给优先队列每次用更新后的距离入堆从堆顶取的点如果不是最新的就 continue。这个懒删除策略必须配合一个 visited 标记数组否则会反复处理同一个点导致死循环或超时。我第一次写堆优化 Dijkstra 就漏了这个标记结果本地跑小样例全对一提交就 TLE排查了半小时才反应过来。SPFA 在竞赛里容易挂它本质上可以被构造出特殊数据卡死让复杂度退化成 O(nm)。所以能用堆优化 Dijkstra 解决的题我尽量不用 SPFA。4.3 最小生成树与二分图最后几天的硬骨头最小生成树的两种算法Kruskal 和 Prim对应两种截然不同的思路。Kruskal 基于并查集把边排序后从小到大选不会成环就加入Prim 则类似 Dijkstra从任一顶点出发贪心地扩展。我的建议是优先掌握 Kruskal因为它的实现更短、逻辑更直观绝大多数最小生成树题用它能搞定Prim 只要看懂过程能写出朴素版本即可。二分图的判定与最大匹配是两个经典问题。判定用染色法在图上交替染色如果相邻两点颜色相同就说明不是二分图这里用 BFS 或 DFS 都能实现。最大匹配则用匈牙利算法它的能占则占占不了就让路的递归找增广路思想第一次看很绕第二次看觉得很妙。匈牙利算法在男女匹配、任务分配这类建模题里出现频率极高值得花一个下午把递归过程画清楚。5. 动态规划与数学知识拉高算法水平的关键章节5.1 背包问题的套路化学习动态规划章节从背包问题开始这是整个课程中公式最明确、最适合背模板的一部分。01 背包是基础中的基础其状态转移方程为 f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i])。由于每个物品只用一次滚动数组优化时体积必须从大到小遍历for (int i 1; i n; i) for (int j m; j v[i]; j--) f[j] max(f[j], f[j - v[i]] w[i]);完全背包则改为从小到大遍历因为每个物品可以无限取用for (int i 1; i n; i) for (int j v[i]; j m; j) f[j] max(f[j], f[j - v[i]] w[i]);这两个循环方向的选择是背包问题最核心的考点也是最容易搞混的地方。我的记忆方法是01 背包从大到小是因为每次更新依赖上一层的小体积状态从大到小可以防止本轮更新被覆盖完全背包从小到大正好利用本轮刚更新的状态实现无限取同一物品的效果。多重背包在朴素写法基础上引入了二进制拆分优化把 10 个相同物品拆成 1、2、4、3 四组从而转化为 01 背包。这个技巧在现场做题时非常实用。分组背包则只是把物品组内部做一次 01 选择。5.2 线性 DP 与区间 DP从翻译题意到定义状态线性 DP 的关键是状态定义。最典型的两个例子最长上升子序列和最长公共子序列。前者定义为以 i 结尾的最长上升序列长度后者定义为 A 前 i 个字符和 B 前 j 个字符的公共子序列长度。状态定义对了转移方程基本就是照着定义写出来的。区间 DP 的模板是枚举区间长度从小到大枚举起点和终点然后枚举区间分割点。经典题目石子合并、回文子序列都在这个框架下。我这里有个非常实在的建议区间 DP 的很多题暴力复杂度都带立方但数据范围通常很小所以不要担心复杂度先保证把三重循环写对再去考虑优化。5.3 数学章节的战略取舍与高阶话题数学知识这一章包含质数判断、约数、欧拉函数、快速幂、扩展欧几里得、中国剩余定理、高斯消元、组合数、容斥原理和博弈论。对于目标是蓝桥杯或日常刷题的人来说快速幂和组合数是必须掌握的重点欧拉函数和博弈论则可以放后不求精通但至少要能识别题型、能写出基础结论。快速幂的本质是二进制的拆分把指数按二进制展开底数每次自乘指数为 1 的位才乘到答案里。这个思路后续还可以扩展到矩阵快速幂用来高效计算斐波那契数列的第 n 项等递推问题。我当时学完快速幂后的感受是这一小段十几行的代码性价比极高值得反复默写三遍以上。组合数的求法有多种数据范围小用递推公式 C(n, k) C(n-1, k) C(n-1, k-1)k 小且 n 大的时候用预处理阶乘加逆元数据特别大、需要精确值时用 Lucas 定理。我自己在实战中 90% 的组合数题都用递推公式解决建议先把这一种吃透再扩展其他方法。6. 常见问题与排查技巧实录6.1 编译错误和运行错误是最容易自查的问题寒假刷题时最常见的报错集中在编译错误和运行错误两类。编译错误通常是拼写问题、缺头文件、变量名冲突这类错误编译器会直接告诉你行号基本就是动手改就能过。真正麻烦的是运行错误比如数组越界、除以零、栈溢出。我踩过最典型的一个坑是在递归 DFS 函数里开了一个大数组作为局部变量结果栈空间瞬间爆掉系统直接报段错误。后来我把所有大数组改成全局变量问题立刻消失。这个经验我一直记到现在大数组永远开全局递归深度的题目永远不要在大函数体里申请大块栈空间。访问越界的排查我习惯用边界样例去测长度为 1 的数组、两个元素的数组、全部元素相等的情况往往跑这几个用例就能让越界暴露。二分题尤其要用找不到目标值的用例去验证边界返回。6.2 超时和超内存先确认算法复杂度是否达标TLE 出现时第一件事不是调常熟优化而是重新审视算法复杂度。如果数据量是 10^5你写的代码复杂度是 O(n²)再怎么优化循环里的小常数都没有意义必须换成 O(n log n) 或者 O(n) 的算法。我用一个粗略的估算标准1 秒的执行量大约在 10^8 这个量级上下超过这个量级大概率超时。MLE 则主要来自无意识的额外存储。常见的问题包括本来只用数组记录状态却顺手开了 mapBFS 队列里存了整个状态对象而不是索引开数组时没有按题目给的数据范围认真估算。排查方式很简单把每个数组按其类型大小乘上长度估算总内存和题目限制对比。int 数组一个元素 4 字节1e6 个就是 4MB心里有数就不会超。6.3 思路正确却过不了样例时的检查顺序有时候最崩溃的情况不是想不出来而是明明觉得思路没问题样例却和答案不一样。这种时候我建议按这个顺序检查先看是不是数组下标边界写错了比如循环从 0 开始但数据从 1 开始。再看输入输出格式是不是把输入顺序读反了或者漏读了一组数据。检查是否是 long long 精度问题。很多看似 int 的中间结果乘起来就溢出数据范围上界超过 2×10^9 时直接用 long long不要犹豫。如果还不过写一个小型暴力版本和当前版本在随机小数据下对拍。这是解决样例过、提交错最狠的招。我当时学归并排序求逆序对时就是靠对拍来验证边界写法是否准确的。6.4 高频问题速查表现象可能原因排查方向二分死循环mid 没有加一导致区间不缩小检查右边界二分是否l r 1 1DFS 递归爆栈大数组开在函数内部全局变量代替局部变量01 背包结果错体积循环方向反了从大到小改回从小到大或反过来Dijkstra 超时没有 visited 标记反复入堆加上 st 数组跳过旧记录输出结果偏大int 溢出中间运算转 long long高精度减法符号反没先比较两数大小先判大小再决定符号这个速查表是我边刷题边积累出来的建议你也照着做一张自己的表。每个人常踩的坑不一样只有亲手记录过的错误才会真正记住。7. 寒假学习计划的具体参考模板7.1 三周时间线的安排建议如果你计划按三周来过 Acwing 算法基础课我下面的时间线可以直接抄作业根据自己的基础调整阶段天数内容目标第一周第 1-3 天基础算法排序、二分、高精度、前缀和、差分每个专题至少完成 3 道对应练习题第一周第 4-7 天双指针、位运算、离散化、区间合并掌握区间合并的排序思维第二周第 8-10 天数据结构链表、栈、队列、单调栈、单调队列手动模拟单调栈、单调队列的进出过程第二周第 11-14 天KMP、Trie、并查集、哈希表、STLKMP 模板能默写并查集能处理带权问题第三周第 15-17 天DFS、BFS、树与图遍历、拓扑排序能独立完成排列、迷宫、拓扑排序题第三周第 18-20 天最短路、最小生成树、二分图建立选型逻辑能用正确算法解决原题第三周第 21 天起动态规划、数学、贪心专题背包问题必须精通数学量力而行这套安排有一个原则每周周末用半天做一次综合回顾把所有模板自己不看书默写一遍。默写不出来的内容就是下周必须优先复习的内容。7.2 每天的学习节奏与精力分配一天六小时听起来很多但如果分配得当反而比硬坐十小时有效。我用的节奏大致是上午两小时看新课、记笔记下午两小时做当天对应题晚上一小时整理模板、修改昨天的错题。中间每隔 45 到 60 分钟休息一次避免注意力断崖式下降。下午刷题遇到卡住的题我会先给自己设一个 30 分钟的死线。30 分钟想不出来就去看题解思路但看完思路后一定关掉题解自己重写代码而不是跟着抄。这个习惯让我避免了看懂了但不会写的假学习状态。7.3 一个容易被忽略的收尾工作整理自己的错题本寒假学习的最后一天我没有开新内容而是把所有错题和易错点重新过了一遍。我在这份错题本里记录了三类内容一类是边界条件写错的题一类是算法选错的题一类是思路对但代码实现细节不对的题。每一个都附带当时的错误代码和错误原因。这个错题本的量不大二十多天大概累积了六十多道但它比任何刷题量都珍贵。寒假结束后的几个月里每次刷题前翻一遍这份错题本很多坑都能提前避开。我的体会是这套输入-输出-复盘的动作比单纯听课多十倍价值——很多人学完课程就散件了而真正把知识变成自己能力的人靠的恰恰是这些看似笨拙的整理工作。最后再分享一个小技巧别害怕在笔记里写废话。我当时经常在模板旁边写这个边界为什么这样哪怕是口语化的吐槽都行。一两个月后再看这些笔记那些带着当时思考痕迹的记录比任何教科书都更容易让你快速恢复记忆。算法这条路没有捷径但合理的节奏、扎实的复盘还有那一本属于自己的错题笔记确实能让你走得又快又稳。