1. 从“传智杯”到算法竞赛一个参赛者的复盘视角又到了年底各种算法竞赛的赛季也接近尾声。前几天翻看自己的代码仓库看到了去年第五届传智杯时留下的几份题解草稿只写了前四道后两道当时卡住了赛后也没来得及补上。这就像一场没打完的仗心里总有个疙瘩。今天正好有空我想把那次比赛的前四题结合我后来的一些思考重新梳理一遍。这不仅仅是一份“题解”更像是一次事后的技术复盘聊聊当时解题的思路、踩过的坑以及如果现在再让我做我会怎么想。传智杯作为国内面向高校学生和编程爱好者的知名赛事题目风格一直很接地气既考察基础的数据结构与算法也注重思维灵活性和代码实现能力。第五届的题目也不例外前几题看似平易近人但细节处藏着不少“小心思”。对于刚开始接触算法竞赛的朋友来说把这些题目吃透远比盲目刷很多难题更有价值。接下来我就按照我当时解题的顺序也是题目难度大致递增的顺序来逐一拆解。2. 第一题签到题里的“陷阱”与稳健思维通常比赛的第一题都是签到题旨在让选手快速进入状态拿到基础分。第五届传智杯的第一题我记得是一个关于数组操作或者简单模拟的问题。题目描述往往不长但千万别因为它简单就掉以轻心。很多选手的“罚时”错误提交导致的加时都是从签到题开始的。2.1 题目回顾与核心诉求具体题目我记不清原题了但类型很典型可能是给定一个数组进行一系列固定的操作比如交换位置、加减某个值然后询问最终状态或者某个结果。这类题目的核心诉求是“准确无误地翻译题目规则”。你的代码不需要任何高深的算法只需要像一个尽职尽责的文书员把题目描述的操作步骤一字不差地用程序语言复现出来。2.2 常见“陷阱”与我的解法这类题最容易踩的坑有几个下标问题题目描述和编程语言如C、Python的数组下标通常是从1开始还是0开始这必须第一时间确认并贯穿始终。一个偏移错误就会导致全盘皆输。操作顺序题目说的“先A后B”是否真的严格按顺序执行有些操作可能彼此独立可以乱序但有些则不行。数据范围这是新手最容易忽略的。题目给的数组长度N和操作次数M有多大如果N和M都是10^5级别你用了一个O(N*M)的双重循环那必然超时。虽然签到题数据范围通常较小但养成看数据范围的习惯至关重要。我当时采取的步骤是第一步手算样例。不要急着敲代码用笔和纸按照题目描述手动计算一遍题目给出的样例输入和输出。这个过程能帮你极大程度地理解题意并提前发现理解歧义。第二步确定数据结构。根据数据范围选择。如果N不大比如小于1000用普通的数组或列表就行。如果涉及到频繁的插入删除可能需要用到链表但比赛里直接用vector或list模拟也行。第三步模拟流程。在代码里用循环清晰地模拟每一步操作。每写一步心里都默念一遍对应的题目描述。第四步边界检查。循环的起止条件、数组访问是否可能越界、操作完成后是否会产生意想不到的数据如负数这些都是要检查的。2.3 一个通用的稳健编码技巧对于模拟题我强烈建议在本地测试时额外设计几个“边界数据”。比如数组长度为1时操作次数为0时操作涉及首尾元素时你的程序是否能正确运行很多线上评测系统的隐藏测试用例就是这些边界情况。在代码的关键部位添加一些assert断言比赛时记得注释掉也是快速自查的好方法。注意传智杯这类比赛通常使用标准输入输出stdin/stdout。务必确保你的输入读取代码能正确处理多组数据如果题目有多组用例的话并且输出格式严格符合要求多一个少一个空格都可能导致错误。3. 第二题贪心策略的识别与证明第二题的难度通常会有一个爬升往往涉及到简单的贪心算法或者基本的数论/组合知识。我印象中这一题可能是一个关于“分配”或“选择”的问题例如给定一些资源和一些任务如何最大化收益或最小化成本。3.1 问题抽象与贪心直觉贪心算法的核心思想是“每一步都做出当前看来最优的选择”并希望这样的局部最优能导致全局最优。但并不是所有问题都适用贪心能用的前提是问题具有“贪心选择性质”和“最优子结构”。对于竞赛题通常出题人会设计成可以用贪心解决关键就在于你能否识别出来。识别线索往往在题目描述里“最大化总和”、“最小化步骤”、“尽可能多”……当你看到这些词并且感觉“好像每次都选最大的/最小的就行”时贪心可能就是正解。3.2 解题步骤与策略构建以一道可能的“活动安排”变种题为例有若干个区间求最多能选择多少个互不重叠的区间。排序是关键贪心题几乎离不开排序。按什么排序常见的有按结束时间升序、按开始时间升序、按权重降序等。对于区间问题经典贪心是按结束时间升序排序。贪心选择排序后从第一个区间开始选择它。然后跳过所有与它重叠的区间选择下一个不重叠的区间。证明心里过一遍为什么按结束时间排序最优因为这样能给后续选择留下更多的时间余地。你可以这样想如果一个最优解中第一个选择的区间不是结束最早的那么我们可以用结束最早的区间替换它仍然得到一个合法且可能更优不差于原解的解。这个“替换法”是证明贪心策略的常用思路。3.3 实现细节与代码模板实现起来代码通常很简洁// 假设 intervals 是区间数组每个区间有 start, end 两个属性 sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; // 按结束时间升序排序 }); int count 0, last_end -1; // 记录上一个选择的区间结束时间 for (const auto interval : intervals) { if (interval.start last_end) { // 当前区间开始时间不早于上一个结束时间 count; last_end interval.end; } } cout count endl;这就是一个非常经典的贪心模板。在比赛中你需要根据具体问题调整排序规则和选择条件。3.4 为什么贪心有时会错这就是贪心算法的“坑”。如果你排序规则选错了或者问题本身不具有贪心性质比如经典的0-1背包问题那么贪心就会得到错误答案。例如如果区间带权重要求权重和最大那么按结束时间贪心就不对了可能需要动态规划。所以在无法严格证明时用贪心提交前一定要用多组自己构造的数据包括极端数据验证一下。4. 第三题搜索与简单剪枝的应用到了第三题一般会考察搜索算法深度优先搜索DFS或广度优先搜索BFS可能是在一个矩阵里找路径或者枚举所有排列组合满足某种条件。搜索是算法竞赛的基石必须熟练掌握。4.1 问题建模状态与转移拿到一个搜索题首先要定义“状态”。状态就是你搜索到某一步时需要记录的所有信息。比如在迷宫问题中状态就是当前的坐标(x, y)在八皇后问题中状态可以是一个记录每行皇后列号的数组。 其次要定义“状态转移”即从一个状态可以走到哪些下一个状态。在迷宫里就是上下左右四个方向移动在排列生成中就是选择下一个还没用过的数字。4.2 DFS与BFS的抉择DFS深度优先搜索用递归或栈实现特点是“一条路走到黑”适合寻找所有可行解、判断连通性、拓扑排序等。代码写起来通常更简洁。BFS广度优先搜索用队列实现特点是“一层一层向外扩”适合寻找最短路径在边权为1的图中、最少步骤等问题。在传智杯的题目中如果问“是否存在一条路径”DFS可能更直接如果问“最短路径长度”BFS通常是首选。我当时遇到的第三题印象中是一个在网格上进行操作的最少步骤问题很自然地就用了BFS。4.3 剪枝避免无效搜索的关键纯暴力搜索的复杂度往往是指数级的必须剪枝。剪枝就是提前判断出某些分支不可能产生最优解或合法解从而不再继续搜索。 常见的剪枝技巧可行性剪枝当前状态已经不可能达到目标比如坐标越界、资源已耗尽。最优性剪枝当前状态即使继续搜索得到的结果也不会比已知的最优解更好比如当前步骤数已经超过了历史最小步骤数。记忆化去重如果搜索过程中会多次到达同一个状态那么只搜索一次即可。在BFS中用visited数组记录已访问状态在DFS中可以用哈希表记录状态对应的最优值避免重复计算这其实已经是记忆化搜索迈向动态规划了。4.4 我的BFS实现框架对于网格BFS我有一个固定的框架struct State { int x, y; // 坐标 int step; // 到达此状态的步数 // ... 其他必要信息如携带的钥匙状态等 }; int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 上下左右 bool visited[N][N]; // 访问标记数组维度根据问题定 queueState q; q.push({start_x, start_y, 0}); visited[start_x][start_y] true; while (!q.empty()) { State cur q.front(); q.pop(); // 判断是否到达终点 if (cur.x end_x cur.y end_y) { ans cur.step; break; } // 遍历四个方向 for (auto d : dirs) { int nx cur.x d[0], ny cur.y d[1]; // 1. 可行性剪枝是否越界是否是障碍物 if (nx 0 || nx n || ny 0 || ny m || grid[nx][ny] #) continue; // 2. 去重是否访问过有时状态包含更多维度需要扩展visited数组 if (visited[nx][ny]) continue; visited[nx][ny] true; q.push({nx, ny, cur.step 1}); } }这个框架非常通用大部分网格BFS题都能套用。难点在于状态的设计。如果题目增加了条件比如“可以打破一面墙”或者“需要收集所有宝石”那么状态里就需要额外增加一个维度来记录这些信息visited数组也要变成多维例如visited[x][y][key_state]这就是常说的“状态压缩BFS”。5. 第四题动态规划的入门与状态设计第四题往往是一个动态规划DP问题。DP是区分选手水平的一个重要分水岭。很多人觉得DP难其实难就难在“状态设计”和“转移方程”。5.1 识别DP问题DP问题通常有几个特征求最值最大价值、最小成本、最长长度、最多方案数等。问题可以分解大问题的最优解可以由小问题的最优解推导出来。有重叠子问题在递归求解过程中很多子问题会被重复计算多次。传智杯的DP题一般不会太复杂可能是经典的线性DP、背包DP或者区间DP的简单变种。5.2 经典思路从“记忆化搜索”到“递推”对于新手我强烈推荐从“记忆化搜索”开始理解DP。它本质上是带缓存记忆化的DFS。定义递归函数dfs(pos, status)表示从pos位置、处于status状态下能达到的最优解。写出递归关系思考在当前状态下有哪些选择每个选择会导向哪个子问题。dfs(pos, status) max/min( choice1 dfs(next_pos, next_status), choice2 dfs(...) )。添加记忆化用一个数组dp[pos][status]记录已经计算过的dfs(pos, status)的结果。下次再遇到相同的状态直接返回缓存值避免重复计算。记忆化搜索想明白了再把它转化成递推表格DP就相对容易了。递推就是自底向上地填充这个dp表。5.3 以一道可能的“爬楼梯”变种为例假设题目是每次可以爬1级、2级或3级楼梯但不能连续爬两次相同的级数求爬到第n级有多少种方案。状态设计dp[i][j]表示爬到第i级且最后一步是爬了j级j1,2,3的方案数。我们需要这个j就是为了满足“不能连续相同”的限制。初始化dp[1][1]1爬1级到1dp[2][2]1dp[3][3]1。同时dp[2][1]可以从dp[1][2]或dp[1][3]转移过来因为最后一步是1前一步就不能是1但dp[1][2]和dp[1][3]不合法不可能一步爬2或3级到第1级所以为0。同理分析其他初始状态。状态转移dp[i][1] dp[i-1][2] dp[i-1][3]// 最后一步爬1级前一步就必须是爬2级或3级dp[i][2] dp[i-2][1] dp[i-2][3]// 最后一步爬2级前一步就必须是爬1级或3级dp[i][3] dp[i-3][1] dp[i-3][2]// 最后一步爬3级前一步就必须是爬1级或2级最终答案dp[n][1] dp[n][2] dp[n][3]。5.4 调试DP的实用技巧DP写错了很难调试因为整个表是关联的。我的技巧是先写记忆化搜索逻辑更直观更容易写对。用小的n比如5测试打印出所有递归调用和结果看是否符合预期。手动模拟填表对于递推写法在纸上画出dp表格手动计算前几行i1,2,3,4确保和你的程序输出一致。关注边界i小于1、2、3的时候怎么办dp数组的初始值是什么这些地方最容易出错。输出中间状态在最终代码里可以临时把整个dp表打印出来对于小数据检查是否有异常值。6. 第五、六题的折戟瓶颈分析与后续学习方向这就是我标题里说的“后俩没写出来”的部分。当时比赛时间所剩无几面对第五和第六题思路完全卡住连暴力搜索的方向都找不到。赛后复盘我发现问题出在几个方面这也是很多算法学习者的共同瓶颈。6.1 知识盲区高级数据结构与算法的缺失前四题覆盖了模拟、贪心、搜索、基础DP这些都是算法竞赛的“标配”。而第五、六题往往会涉及更专门的知识点例如图论进阶最短路径Dijkstra, SPFA、最小生成树Kruskal, Prim、网络流、强连通分量等。我当时可能遇到了一道需要巧妙建图然后求最短路的题但没想到如何抽象成图模型。高级数据结构线段树、树状数组用于高效区间查询更新、并查集处理分组问题、单调栈/队列优化DP。题目可能要求维护一个动态变化的序列并快速查询某种属性。数学与数论组合数学容斥原理、博弈论SG函数、快速幂、模运算性质。这类题需要较强的数学思维和公式推导能力。6.2 思维定势与模型转换能力不足即使知识点学过在紧张的比赛环境中能否快速识别出题目背后的模型也是一大挑战。比如一道题表面上是字符串处理但核心可能需要用到动态规划DP或自动机一道题描述了一个复杂的游戏过程其本质可能是一个博弈论问题或者状态压缩搜索。我当时就是被困在了题目的表面描述里没能进行有效的“问题转化”。6.3 时间管理与策略失误这是实战经验问题。我在前四题尤其是第三题的调试和第四题的推导上花了过多时间导致留给后两题的时间严重不足。在时间紧迫的情况下心态容易急躁更难进行冷静的深度思考。合理的策略应该是快速读完所有题目对每道题进行难度预估和知识点归类。先解决所有有清晰思路的题对于难题先写一个暴力解法哪怕只能过小数据保底再思考优化。6.4 我后续的针对性学习那次比赛后我针对自己的薄弱环节做了调整专题突破不再泛泛地刷题而是针对图论、数据结构、数学等薄弱专题进行集中训练。每个专题先系统学习理论然后刷一定量的经典例题LeetCode、洛谷、AcWing等平台的专题集非常好用最后再做一些综合性的题目。练习“题眼”识别每做一道题尤其是做不出来的题看完题解后我会问自己这道题的“题眼”是什么是哪个关键条件或性质引导了解法我为什么没想到把这个思考过程记录下来。参加虚拟比赛定期在OJ上参加虚拟竞赛严格模拟比赛环境时间、心态锻炼快速读题、决策和编码的能力。赛后无论成绩如何都认真补题。构建代码模板库将常用的算法如Dijkstra、快速幂、线段树封装成自己熟悉的、bug-free的模板。比赛时可以直接套用节省时间并减少出错。比赛的意义远不止于排名和奖项。每一次“没写出来”的经历都是一次宝贵的诊断清晰地告诉你下一步该往哪里努力。传智杯的题目设置很有梯度前四题是巩固基础后两题是引导你探索更广阔的算法世界。把这次未完成的挑战当作一个学习路标持续积累下次定能更进一步。