SMU-ACM 的 2026 冬训周报来了这是第一期。写这个系列的目的很直接把每周训练的安排、选题思路、代码实现、踩过的坑都摊开来讲给队里同学一个复盘参考也顺便给正在入门 ACM 的选手们一些可以抄作业的路线。这一周我们主要解决的事情是把基础算法里的输入输出、排序二分、栈队列、并查集和图论入门重新过一遍并且用题目把每个知识点砸实。无论你是刚接触 ACM 的新手还是准备明年省赛的老队员这份周报都值得花十分钟翻一翻。1. 冬训第一周我们到底在练什么1.1 为什么第一周不直接上难题每年冬训总有人问不能直接刷 CF 的 div2 吗不能直接啃树剖吗我的回答一直是先别急。ACM 竞赛题目看着花哨但真正的底层永远是那几张牌——排序、查找、数据结构、搜索、图论、动态规划。第一周如果就上难题进度看起来很快实际上大多数人会陷入看题解靠背、敲代码靠猜的假努力循环。我们队这周的做法是全员过一遍代码基本功。很多同学以为会写sort(a, an)就算会排序了但比赛里要求的是知道什么时候排序是瓶颈、怎么用二分把复杂度从 O(n²) 降到 O(n log n)、怎么在离散化后手动实现排序逻辑。这一周本质上是在给后面的专题训练打地基地基歪了后面盖什么都塌。另外还有一个现实原因冬训刚开始每个人的状态参差不齐。有人刚从期末考试缓过来有人是零基础刚接触 OJ如果统一上难题新手会直接被劝退老队员也难有提升。用一周时间把所有人拉到同一条起跑线上比接下来任何一周的训练都重要。1.2 训练节奏与每日安排本周的训练节奏分三块个人刷题、专题讲解、队内小结。个人刷题是主线每天至少 3 道完整 AC 的题专题讲解安排在晚上由队里轮流讲内容对应当天刷题涉及的知识点队内小结在周末做把这一周的题统一拉出来复盘。具体到每天大概是这样的安排上午复习前一天专题补题把没 AC 的题重新做一遍下午刷当天专题的题目至少完成 3 道新题 1 道变形题晚上专题讲解 40 分钟之后是自由讨论和互相 review 代码周日一场 3 小时的小型模拟赛题量 4~5 道难度控制在省赛签到题级别题量看起来不大但每道题我们都要求写完整代码不能用思路对了就行搪塞过去。这周有个规矩一道题想不出来先憋 30 分钟再问问的时候必须说出自己的思考过程。这样逼出不少好代码也逼掉了不少抄完题解就当会了的坏习惯。2. 核心算法模块拆解这周真正练了什么2.1 输入输出优化ACM 模式的第一道坎很多刚接触 ACM 的人对ACM 模式的理解就是用cin读数据、算出结果、cout输出。这种理解在第一周就被我们用题目怼回去了。ACM 模式的本质是输入数据量可能非常大输出要求完全匹配中间出现任何格式问题都是白费力气。这周我们专门练了快读快写。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是入门标配但遇到几百万级别的输入scanf也不一定够就得自己写 getchar 快读。我贴一个平时常用的模板#include bits/stdc.h using namespace std; int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }这个快读支持负整数思路很简单跳过所有非数字字符连续读数字累加。实际测试下来在数据规模达到 1e6 时它比cin开优化还要快一半以上。别忘了输出也要优化大量输出用putchar拼字符串而不是一次次cout。这周第一天的作业就有一道多组输入加大量输出的题很多同学直接在 OJ 上收获了Time Limit Exceeded这就是 ACM 模式给的第一记闷棍。我的建议是从入队第一天就把快读快写当成肌肉记忆不要等到卡超时才想起来优化。2.2 二分与排序从裸题到变形二分是冬训第一周的重头戏。原因是二分太常用了而且它的错误往往是隐蔽的——在二分边界、终止条件上出错拿小数据测试一切正常大数据一提交就错。我们的训练从三分支递进裸二分查找、二分答案、二分套数据结构。裸二分是热身重点在理解left和right的更新条件二分答案是重头戏几乎所有最优值类问题都会用到比如最小化最大值、最大化最小值二分套数据结构则是埋伏笔为后面树状数组、线段树做准备。这里给新手的两个口诀都是踩坑踩出来的第一二分的循环条件是left right还是left right取决于你让 left 还是 right 作为答案的最终位置第二mid (left right) / 2永远不如mid left (right - left) / 2稳妥后者不会溢出。别看这是个细节平台上的数据范围一旦开到 1e9前一种写法就真的会炸。排序方面这周我们没有专门去练快排、归并的实现因为库函数真的够用了而是把重点放在排序如何辅助其他算法上。比如逆序对问题先归并排序边排边数或者用树状数组离散化之后统计这在之后处理很多计数类问题时会反复出现。第一周只要求掌握两种套路归并排序求逆序对和二分答案的标准框架。2.3 并查集与图论基础数据结构的骨架并查集是冬训必讲的知识点因为它本身简单但变化极多。第一周的并查集训练只做了三件事路径压缩、按秩合并、带权并查集的概念铺垫。路径压缩就是那个经典的递归findint find(int x) { return father[x] x ? x : father[x] find(father[x]); }很多同学一开始写不好这个函数容易写成死循环或者忘写返回语句。我的建议是画图理解比如有四个点1 指向 22 指向 33 指向自己find(1)的过程就是把 1、2 都直接指向 3。路径压缩的实质是记忆化搜索如果把这个类比讲清楚代码就非常容易记住。本周并查集的经典题目是亲戚问题判断两个人是否有亲戚关系。这道题本身很简单但它衍生出了合并两个集合再查询动态加边这些基础操作之后很多图论算法的前置操作都和它有关。比如Kruskal求最小生成树第一步就是按边权排序然后用并查集判断两个端点是否已经在同一个集合里。第一周把这棵小树苗种下后面长成森林就不慌。图论基础我们只安排了 BFS 和 DFS。BFS 的队列实现、DFS 的递归栈实现配合一个迷宫最短路模板题让每个人都能手写一遍。这里强调一个观念搜索是后面所有算法题的兜底方案。遇到一个问题哪怕暂时没思路先想能不能暴力搜索出一个小规模答案再去优化。冬训期间暴力写不出的人优化一定是空中楼阁。2.4 栈与队列被低估的基础工具如果说并查集和图论是骨架那栈和队列就是算法世界里的扳手和螺丝刀。可惜很多人觉得栈不就是括号匹配吗、队列不就是 BFS 吗结果遇到单调栈、单调队列、优先队列变形题就一脸茫然。本周我们在栈上安排了括号匹配题和单调栈的入门题。括号匹配的核心逻辑很简单遇到左括号压栈遇到右括号弹栈并检查配对。但很多人写出的代码会在空栈时top()崩溃这就是边界没考虑清楚。单调栈稍微进阶一点经典场景是求每个元素左边第一个比它小的位置它的时间复杂度是 O(n)很多人第一次会被这个灵巧的优化惊艳到。队列部分除了 BFS我们强调了循环队列的数组实现——虽然比赛里直接用 STL 的deque也很方便但理解底层是怎么用一个数组首尾相连地存元素的能避免很多莫名其妙的 bug。特别在写单调队列优化 DP 时你会知道head和tail指针到底在干什么而不仅仅是盲目调用front()和pop_front()。这周还埋了一个伏笔优先队列堆。我们知道优先队列能维护动态最大值这周只要求会用priority_queue解决合并果子这类贪心题真正的堆优化 Dijkstra 放在后两周这周不展开。3. 实操记录有代表性的题目与代码细节3.1 快读与多组输入的实战本周练习第一题是一个经典的求和题输入不定组数每行两个整数要求输出和。题目本身一点不难但它把 ACM 模式最恶心的地方暴露了你不知道输入什么时候结束得靠while (cin a b)或者while (scanf(%d%d, a, b) 2)来判断。用cin的话必须开优化否则 1e5 行输入也能让你超时但更关键的是很多人不知道scanf的返回值是成功读取的变量数。这道题的意义不在题面而在让大家统一一个输入输出模板。我建议所有队员从现在开始固定使用自己写好的快读快写代码块每次交题直接复制不要现场重写。比赛时每一分钟都很珍贵不要浪费在重复劳动上。3.2 二分答案题进击的奶牛第二周周三我们练了一道很经典的二分答案题——进击的奶牛在一条直线上给 n 个坐标选 m 个牛棚让牛之间的最小距离尽可能大。这个问题的本质是最大化最小值它明晃晃地指向二分答案。代码核心是check函数bool check(int d) { int cnt 1; int last a[1]; for (int i 2; i n; i) { if (a[i] - last d) { cnt; last a[i]; } } return cnt m; }这里最容易错的就是排序后的第一个坐标要不要选。我见过很多人的代码直接默认选第一个实际上这不是必然的但在这道题里因为坐标是升序且我们要让最小距离最大贪心选第一个位置作为起点通常没有错。问题是——通常这个词在竞赛里就是坑。正确的思考姿势是check(d)判断的是当最小距离定为 d 时能否选出至少 m 个点如果你每次都从头开始那第一个坐标必然作为第一头牛的棚这不会让可行解变差所以可以这样贪心。二分的循环写法也有讲究我们统一用左开右闭的变体int l 0, r a[n] - a[1] 1; while (l 1 r) { int mid (l r) / 2; if (check(mid)) l mid; else r mid; } cout l \n;这个写法我觉得是新手最好理解的l表示当前可行的答案r表示当前不可行的答案目标就是不断逼近中间临界点。代码不容易出现死循环边界问题也更容易通过小样例自测。3.3 并查集的经典合并问题周三下午练的是一道连通块题目给出 n 个点 m 条边动态查询两个点是否连通。这是一道标准的并查集模板题但加了动态查询后很多人开始犹豫不知道该用什么数据结构。实际上并查集天生就是为这种场景设计的find判断连通性merge动态加边。完整的主函数结构大概是这样的int n, m; int fa[N]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; } int main() { cin n m; for (int i 1; i n; i) fa[i] i; for (int i 0; i m; i) { int op, x, y; cin op x y; if (op 1) merge(x, y); else cout (find(x) find(y) ? YES : NO) \n; } return 0; }注意并查集的初始化千万不能漏。很多同学一开始写fa数组忘了初始化成自己的下标然后find返回 0导致所有查询全都错误。这个问题我几乎每个学期都见到所以这周专门盯着所有人把初始化代码写在最前面。关于按秩合并这周我们只用一句话要求能写就写。路径压缩已经能把复杂度压到近乎 O(1)按秩合并更多是理论上的保护代码多两行关键时刻能防退化。我自己的模板是保留按秩合并的因为后面带权并查集往往会用到size提前习惯总是好的。3.4 栈与队列的日常使用陷阱周四的题组里有一个括号匹配题加一个单调栈入门题都是经典中的经典。括号匹配我给大家一个统一的写法思考顺序遇到左括号入栈遇到右括号时先判断栈是否为空为空则直接判定不合法栈顶元素不匹配也判定不合法最后扫描完还要检查栈是否为空。这四步一个都不能少尤其最后一步很多人会漏导致((()))能过但((())这种非法输入也会被错误判定。单调栈的问题则更有趣比如柱子最大矩形面积这道题。它要求每个柱子往左右找第一个比自己矮的位置暴力是 O(n²)但用单调栈可以做到 O(n)。核心思想是维护一个栈栈内元素高度单调递增遇到一个比栈顶矮的柱子时就不断弹出并计算以弹出柱子为高的矩形面积。很多人第一次看到这个解法会懵我的建议是自己拿一组数据走一遍栈的变化过程比单纯看十遍题解都有用。4. 第一周常见问题与排查技巧实录4.1 OJ 提交超时的排查顺序这一周收到的求助信号里有超过一半是超时问题。超时的排查我要求大家按固定顺序来不要瞎猜第一看数据范围。如果 n 是 1e5你还在用 O(n²) 的暴力直接砍掉重写不需要优化。第二检查输入输出。是不是忘了关同步是不是在循环里反复cout换成/* 快读 */或者拼接大字符串输出。第三检查是否有不必要的 STL 拷贝比如函数参数传vector而不是传引用这是隐形杀手。第四如果都排除了再怀疑自己的算法复杂度是否真的达标。有一种很扎心的情况是本地跑 0.5 秒OJ 上超时。这种往往是输入数据量极大cin本地因为缓冲区小反而表现好到了 OJ 上因为整体吞吐量大暴露问题。与其瞎猜不如直接上快读通常立竿见影。4.2 数组越界与边界条件那些本地过、提交错的元凶本周有很多本地编译运行结果完全正确交到 OJ 上 WA的案例。排查后七成是数组越界。ACM 的题目输入经常有 n1 或者 n0 的边界情况很多代码在循环for (int i 1; i n; i)访问a[i1]时在最后一轮就越界了。本地开大数组可能不崩OJ 上直接读到了脏数据于是 WA。我的建议是所有数组开大小的时候都多加 5 到 10 个单位空间题目说 n 最大 1e5就开const int N 100010而不是恰好 100000。这个习惯能省掉无数个找 bug 两小时发现数组开小一位的夜晚。另外很多同学不喜欢造边界样例比如 n1、最小值、最大值、重复数据、空数据。这一周我强制要求每道题提交前至少自测三组数据最小的情况、数据最大的情况、一组随机数据。这三组能堵住大部分低级错误。4.3 训练状态管理与周报的意义最后说一个可能不算技术的技术训练状态。冬训刚开始会很兴奋但第一周往往会迅速遇到挫败感因为每个人都会在某个简单题上卡住。我见过太多人第一天干劲十足第二天因为一道题做不出来就陷入自我怀疑然后开始摆烂。冬训周报的意义就在于把每周的进展和问题都记录下来让人看到这周我确实做完了这些题、理解了这些知识点而不只是停留在我好菜的情绪里。我在队里也一直强调代码能力是手熟活今天卡住的题下周回头再看就是基本功。第一周是打地基打地基的工地上没有摩天大楼但每一锤子都有意义。我个人在这周实操中最大的体会是不要贪多一道题能写完整、讲清楚胜过囫囵吞枣写十道题。周末做模拟赛的时候发现很多同学看到长题面就发慌先静下来拆解条件、画样例、构造测试数据比盯着题面发呆管用得多。下周开始我们会逐渐加入更复杂的数据结构专题但第一周打下的这些基础才是整个冬天最关键的底子。