SMU-ACM冬训周报：第一周基础算法训练与实战复盘-平芜编程栈

SMU-ACM 的 2026 冬训周报来了，这是第一期。写这个系列的目的很直接：把每周训练的安排、选题思路、代码实现、踩过的坑都摊开来讲，给队里同学一个复盘参考，也顺便给正在入门 ACM 的选手们一些可以抄作业的路线。这一周我们主要解决的事情是：把基础算法里的输入输出、排序二分、栈队列、并查集和图论入门重新过一遍，并且用题目把每个知识点砸实。无论你是刚接触 ACM 的新手，还是准备明年省赛的老队员，这份周报都值得花十分钟翻一翻。

1. 冬训第一周我们到底在练什么

1.1 为什么第一周不直接上难题

每年冬训，总有人问：不能直接刷 CF 的 div2 吗？不能直接啃树剖吗？我的回答一直是：先别急。ACM 竞赛题目看着花哨，但真正的底层永远是那几张牌——排序、查找、数据结构、搜索、图论、动态规划。第一周如果就上难题，进度看起来很快，实际上大多数人会陷入"看题解靠背、敲代码靠猜"的假努力循环。

我们队这周的做法是：全员过一遍代码基本功。很多同学以为会写sort(a, a+n)就算会排序了，但比赛里要求的是：知道什么时候排序是瓶颈、怎么用二分把复杂度从 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 并查集与图论基础：数据结构的骨架

并查集是冬训必讲的知识点，因为它本身简单，但变化极多。第一周的并查集训练只做了三件事：路径压缩、按秩合并、带权并查集的概念铺垫。

路径压缩就是那个经典的递归find：

int find(int x) { return father[x] == x ? x : father[x] = find(father[x]); }

很多同学一开始写不好这个函数，容易写成死循环或者忘写返回语句。我的建议是画图理解：比如有四个点，1 指向 2，2 指向 3，3 指向自己，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 的题目输入经常有 n=1 或者 n=0 的边界情况，很多代码在循环for (int i = 1; i <= n; i++)访问a[i+1]时，在最后一轮就越界了。本地开大数组可能不崩，OJ 上直接读到了脏数据，于是 WA。

我的建议是：所有数组开大小的时候都多加 5 到 10 个单位空间，题目说 n 最大 1e5，就开const int N = 100010，而不是恰好 100000。这个习惯能省掉无数个"找 bug 两小时，发现数组开小一位"的夜晚。

另外，很多同学不喜欢造边界样例，比如 n=1、最小值、最大值、重复数据、空数据。这一周我强制要求每道题提交前至少自测三组：数据最小的情况、数据最大的情况、一组随机数据。这三组能堵住大部分低级错误。