上周的 LeetCode 第 512 场周赛我侥幸拿了个国服 22 名并且难得地“无伤”AKAll Kill即四题全部 AC。说实话作为一个“老年”选手现在每次打周赛感觉最吃力的已经不是算法本身而是读题和数数——生怕看错一个条件或者边界情况没数清楚。这篇文章我想和你聊聊的远不止这场周赛的四道题解。我更想分享的是在算法竞赛这个领域当你的基础算法知识框架搭建得差不多之后到底是什么在决定你的上限和稳定性是更刁钻的算法吗很多时候并不是。是信息提取能力、边界处理能力和心态管理能力。这场“无伤”AK的经历恰好是这三个能力一次集中的体现。我会结合具体的题目拆解我是如何“吃力”地读题、如何“笨拙”地处理边界以及如何管理时间与心态最终实现稳定发挥的。无论你是想冲击更高排名还是希望减少比赛中的“愚蠢错误”相信这些实战中的细节思考会比单纯的题解更有价值。1. 算法竞赛的下半场拼的是“工程能力”很多同学在刷了几百道题后会有个困惑为什么感觉都会但一比赛就各种 WAWrong Answer、TLETime Limit Exceeded问题可能不在于算法模板没背熟而在于将算法思想安全、准确、高效地落地成代码的“工程能力”。这场比赛的四道题恰好涵盖了不同的挑战点第一题看似简单的模拟但藏有阅读理解陷阱和边界条件。第二题经典的数组操作与贪心思维考验能否将问题转化为清晰的数学模型。第三题动态规划DP或记忆化搜索核心在于状态定义不能有歧义转移要考虑周全。第四题图论最短路的变种需要熟练运用标准算法如 Dijkstra并对其进行适配改造。“无伤”意味着全程没有提交错误。这要求我们在编码前、中、后每个环节都建立有效的“检查点”和“防御性编程”习惯。下面我们就从最开始的环节——读题开始。2. 题目详解与“防御性”读题技巧2.1 第一题老年痴呆数数其实是条件过滤注由于无法获取第512场周赛原题此处根据常见题型和“数数”、“读题吃力”等关键词构建一道典型例题用于演示思维过程。你的实战中请务必以官方题目为准。假设题目描述给你一个整数数组nums和一个整数k。你需要执行一个操作从nums中选择一个恰好包含k个元素的子序列不一定连续使得这个子序列的和是偶数。请问有多少种不同的选择方案答案可能很大对10^97取模。子序列的定义从原数组通过删除一些也可以不删除元素而不改变剩余元素顺序得到的新数组。两个子序列只要选取的下标不同就视为不同的方案。“吃力”的读题过程分析抓核心动词与名词“选择子序列” - “和是偶数” - “多少种方案”。立刻明确这是组合计数问题大概率用数学组合数计算而不是回溯枚举。标出绝对关键词“恰好k 个元素”、“偶数和”、“下标不同视为不同”。这些是约束条件任何一条理解偏差都会导致全盘皆输。转化为数学模型设数组中有even个偶数odd个奇数even odd n。一个子序列和为偶数当且仅当其中包含偶数个奇数因为偶数加任意偶数仍为偶数奇数个奇数相加为奇数。问题转化为从even个偶数中选i个从odd个奇数中选j个满足i j k且j为偶数。求所有合法(i, j)对应的方案数C(even, i) * C(odd, j)之和。边界与陷阱自查k可以大于n吗题目没说但根据经验如果k n无法选择“恰好” k 个方案数应为 0。k 0怎么办选 0 个元素和为 0偶数应算一种方案。但题目要求“恰好 k 个”如果 k0 是输入范围必须考虑。组合数C(n, m)当m n或m 0时值为 0。在计算时需要判断。取模运算加法、乘法都要取模。代码实现PythonMOD 10**9 7 class Solution: def countEvenSumSubsequences(self, nums: List[int], k: int) - int: n len(nums) even sum(1 for x in nums if x % 2 0) odd n - even # 预处理组合数 C(n, m) 这里用递推式 C[n][m] # 实际比赛可用 math.comb (Python 3.8) 或预计算阶乘逆元 # 此处为演示使用简单循环计算适用于 n 不大时 def comb(n, m): if m 0 or m n: return 0 # 计算 C(n, m) 的值 res 1 for i in range(1, min(m, n-m) 1): res res * (n - i 1) // i return res % MOD total 0 # j 表示选取的奇数个数必须为偶数 for j in range(0, odd 1, 2): # 步长为2保证j为偶数 i k - j # 需要选取的偶数个数 if i 0 or i even: continue total (total comb(even, i) * comb(odd, j)) % MOD return total关键检查点跑示例前先在脑中用一个小例子验证逻辑比如nums[1,2], k1。偶数1个奇数1个。k1j可为 0 或 2偶数。j0时i1:C(1,1)*C(1,0)1j2时i-1无效。结果为1。符合预期只能选[2]。测试k0j0, i0C(even,0)*C(odd,0)1返回1。2.2 第二题贪心策略与“正确性证明”假设题目描述给你一个整数数组nums和两个整数limit和k。你可以执行最多k次操作每次操作可以将nums中任意一个元素加上limit或减去limit。你的目标是使数组的极差最大值减最小值最小化。返回最小的极差。思维过程问题转化加减limit相当于在数轴上“跳跃”。一个数x可以变为x t * limit其中t是任意整数。但操作次数有限k次且每次操作针对一个元素进行limit或-limit。关键洞察每个元素x可以映射到一个“基值”base x % limit以及“层数”floor x // limit。加减limit操作只会改变floor不会改变base。因此所有数可以按base分组。贪心猜想为了缩小极差我们希望所有数的floor尽可能接近。由于有操作次数限制我们应该优先调整那些“离群”的、使极差变大的数。“证明”与验证这不是严格的数学证明但在比赛中需要快速说服自己。可以想象把所有数画在数轴上limit是一个周期。极差最小意味着最大值和最小值落在尽可能接近的“周期带”内。k次操作就是移动一些数到相邻的周期。一个可行的策略是将数组排序后考虑一个滑动窗口窗口内的元素可以通过最多k次操作使其floor调整到某个目标值附近。问题转化为寻找一个最小的窗口使得窗口内的元素调整到同一“水平”所需的操作次数不超过k。这可以用前缀和来优化计算。边界k可能为0limit可能为1数组元素可能为负数注意取模运算在编程语言中的处理Python的%结果非负方便处理。代码框架思路class Solution: def minRange(self, nums: List[int], limit: int, k: int) - int: n len(nums) # 1. 处理每个数得到 base 和 floor bases [] for x in nums: base x % limit floor x // limit # 对于负数需要调整以保证 base 在 [0, limit) 区间 # Python中 -3 % 5 2, -3 // 5 -1 需要特殊处理吗 # 我们更关心相对关系可以统一转换 bases.append((base, floor)) # 2. 按 base 排序不按数值排序可能更好处理窗口 nums.sort() # 3. 问题转化为找到一个长度为 L 的连续子数组 # 使得将其所有元素通过 /- limit 操作调整到某个值附近的最大最小值差最小。 # 更具体假设我们想将窗口内所有数调整到以某个数为基准。 # 所需操作次数 sum(|(target_floor - floor_i)|) for i in window。 # 我们需要这个和 k。并且调整后窗口内数的实际值范围是 [base target_floor*limit, base target_floor*limit]? # 不对因为base不同。实际上排序后窗口的极差主要由两端的数决定。 # 一个常见技巧枚举右端点 i维护左端点 j使得窗口 [j, i] 满足操作次数约束。 # 计算操作次数需要快速求区间内 floor 的和可以用前缀和。 # 目标 target_floor 可以取中位数使操作次数最小。 # 具体实现略这是一个经典的最小化极差滑动窗口问题。要点这道题在比赛中需要快速识别出“周期limit”这一特性并将操作转化为对floor的调整。贪心选择中位数作为目标floor是关键。实现时滑动窗口结合前缀和与二分查找可以在 O(n log n) 内解决。2.3 第三题DP状态定义与“无后效性”动态规划题最怕状态定义有歧义或遗漏导致样例过了却 WA。假设题目描述你有一个n x m的网格每个格子是空地.或障碍物#。你从(0, 0)出发想去(n-1, m-1)。你可以向右或向下移动。此外你最多可以使用一次“跳跃”技能直接跳到当前列下方最近的空地上即跳到同一列行号更大的第一个空地。求到达终点的不同路径数对10^97取模。“防御性”状态设计识别维度位置(i, j)是必须的。还有一个关键维度是否使用过跳跃技能。因为技能只能用一次且使用后状态发生根本改变。定义状态dp[i][j][0]: 到达(i, j)且从未使用过跳跃技能的路径数。dp[i][j][1]: 到达(i, j)且已经使用过跳跃技能的路径数。状态转移对于dp[i][j][0]未使用技能可以从左边(i, j-1)向右走来如果左边是空地。可以从上面(i-1, j)向下走来如果上面是空地。也可以通过在本列(?, j)上方某个格子使用跳跃技能直接跳到(i, j)。但注意技能只能用在“当前列下方最近的空地”。这意味着如果我们想通过跳跃到达(i, j)那么(i, j)必须是其所在列j中从某个起跳点(p, j)p i下方“第一个空地”。这个关系需要预处理。对于dp[i][j][1]已使用技能只能通过常规移动右、下从其他已使用技能的状态转移而来。不能从“未使用技能”的状态通过常规移动得到因为技能使用是瞬间的移动不会改变技能使用状态。关键dp[i][j][1]可以从dp[p][j][0]通过使用一次跳跃技能转移到(i, j)得到其中(i, j)是(p, j)下方第一个空地。预处理对于每一列j我们可以预处理一个数组next_empty[i][j]表示从(i, j)向下找第一个空地的行号。这可以用于快速判断跳跃目的地。代码框架关键部分MOD 10**9 7 class Solution: def uniquePathsWithJump(self, grid: List[List[str]]) - int: n, m len(grid), len(grid[0]) if grid[0][0] # or grid[n-1][m-1] #: return 0 # 预处理 next_empty next_empty [[-1]*m for _ in range(n)] for j in range(m): last_empty -1 for i in range(n-1, -1, -1): # 从下往上扫 if grid[i][j] .: last_empty i next_empty[i][j] last_empty dp0 [[0]*m for _ in range(n)] # 未使用技能 dp1 [[0]*m for _ in range(n)] # 已使用技能 dp0[0][0] 1 # 起点未使用技能 for i in range(n): for j in range(m): if grid[i][j] #: continue # 状态转移dp0[i][j] if i 0 and grid[i-1][j] .: dp0[i][j] (dp0[i][j] dp0[i-1][j]) % MOD if j 0 and grid[i][j-1] .: dp0[i][j] (dp0[i][j] dp0[i][j-1]) % MOD # 通过跳跃到达 (i, j) 且是第一次使用技能 # 需要找到上方某个格子 (p, j) 跳下来 # 我们可以这样考虑对于当前列j如果 (i, j) 是某个 (p, j) 的 next_empty则可以从 dp0[p][j] 转移过来 # 更高效的做法是在遍历时维护一个当前列上一行的dp0值用于更新下方的dp1? 这里需要仔细设计。 # 一个实现思路先处理常规移动再单独处理跳跃转移。 # 状态转移dp1[i][j] (已经用过技能只能常规移动来) if i 0 and grid[i-1][j] .: dp1[i][j] (dp1[i][j] dp1[i-1][j]) % MOD if j 0 and grid[i][j-1] .: dp1[i][j] (dp1[i][j] dp1[i][j-1]) % MOD # 单独处理跳跃转移遍历每个格子作为起跳点 for i in range(n): for j in range(m): if grid[i][j] # or dp0[i][j] 0: continue nj next_empty[i][j] # 跳跃目的地行号 if nj ! -1 and nj i: # 可以跳跃 dp1[nj][j] (dp1[nj][j] dp0[i][j]) % MOD # 终点可能通过两种状态到达 return (dp0[n-1][m-1] dp1[n-1][m-1]) % MOD易错点跳跃技能是“最多一次”不是必须使用。所以最终答案是dp0[终点] dp1[终点]。跳跃的起点和终点都必须是空地。跳跃的目的地是“下方最近的空地”如果正下方就是空地则跳到那里如果正下方是障碍则继续往下找。注意数组边界不要越界。2.4 第四题图论建模与算法选择图论题往往难点在于建模而不是算法本身。假设题目描述有n个城市编号0到n-1。给你一个二维数组roads其中roads[i] [u_i, v_i, time_i, cost_i]表示城市u_i和v_i之间有一条双向道路通过需要time_i分钟并需要支付cost_i元。你从城市0出发初始有money元。你可以在任何城市无限次地执行一个特殊操作花费1分钟获得1元即用时间换钱。你的目标是到达城市n-1求所需的最短总时间包括移动时间和换钱时间。建模与算法选择问题本质在每个城市你都可以选择“停留”一段时间来赚钱然后用钱去支付道路的cost。这相当于每条边有一个时间和金钱双重约束。我们最终要最小化总时间移动时间赚钱时间。状态扩展传统的 Dijkstra 算法使用dist[node]记录到达某个节点的最短时间。但现在到达同一个城市时你拥有的钱数不同后续决策也不同。因此状态需要增加一维dist[node][money]表示到达城市node时拥有money元的最短时间。但money的范围可能很大money初始值可达10^9无法直接作为维度。关键优化注意到我们只关心“能否支付路费”。对于一条需要cost元的边如果我们当前钱不够就需要在之前某个城市提前赚钱。有一个重要的贪心性质赚钱用时间换钱的操作越早进行越好。因为钱是通用的早赚到钱可以提前解锁那些需要高费用的边避免后续阻塞。更进一步的我们可以证明或直觉上接受最优路径上赚钱的操作只会发生在起点。为什么因为如果你在某个中间城市赚钱不如在起点就赚够这些钱这样你带着更多的钱上路在任何中间节点都有更多的选择权不会更差。问题简化基于上述性质问题可以转化为在起点我们可以决定花t分钟赚钱获得t元。初始有money元所以总钱数为money t。然后我们带着这些钱上路途中不能再赚钱但必须保证任何时候钱都足够支付途经边的cost注意钱花在过路费上不会增加。我们需要找到最小的总时间 t 最短移动时间其中最短移动时间是在钱足够即money t 路径上最大 cost不是每一条边的 cost 都能即时支付的条件下的最短路径时间。最终模型我们实际上是在寻找一条从0到n-1的路径使得路径上所有边的cost的最大值不超过某个值C。因为只要我带的钱money t C我就能顺利走完这条路。而t max(0, C - money)。所以总时间 max(0, C - money) 路径时间。我们需要枚举所有可能的路径但路径太多。怎么办二分答案 BFS/最短路二分查找最终的总时间T。对于某个T我们可以在起点赚钱的时间最多为T因为总时间就是T。所以最多能赚T元总资金为money T。我们在图中只考虑那些cost money T的边因为走这条边时我们最多有money T元。在这个新图中跑一遍最短路Dijkstra边权为time求从0到n-1的最短移动时间min_time。判断条件如果min_time T说明我们可以在T总时间内完成赚钱花了T - min_time分钟移动花了min_time分钟。注意我们还需要确保赚钱的时间T - min_time是够用来赚取所需费用的但因为我们只保留了cost money T的边而money (T - min_time) money T - min_time对于cost money T的边只要min_time 0这个不等式不一定恒成立。更严谨的条件是存在一条路径其上的最大cost为C路径时间为P满足max(0, C - money) P T。这个条件在二分检查时可以通过“只保留cost money T的边然后看最短路径时间是否 T”来近似吗需要推导。更稳妥的二分检查对于猜测的总时间T我们枚举路径上允许的最大费用max_cost。实际上我们可以这样想我们最终拥有的钱是money earn_time其中earn_time T - travel_time。为了能通过一条费用为cost的边需要money earn_time cost即money (T - travel_time) costtravel_time T money - cost。对于整条路径需要满足对于每条边travel_time T money - cost_i。这很复杂。更清晰的解法直接使用状态扩展 Dijkstra但状态是(city, money)其中money是离散化的或者我们使用(city, earned)earned是已经赚的钱。由于我们可以在任何城市无限赚钱状态图是无限的。但我们可以观察到赚钱的数量只需要达到路径中最大的cost即可不需要更多。因此我们只需要考虑赚钱到max_cost这个值。而max_cost最多是所有边cost的最大值MAXC。所以我们可以定义状态dist[city][extra]表示到达城市city并且额外赚了extra元钱超出初始money的部分所花的最短时间。extra的范围是0到MAXC因为赚更多钱没用。这样状态数就是n * (MAXC1)。在 Dijkstra 松弛时有两种操作走边(u, v, time, cost)需要满足money extra cost。新状态(v, extra)时间增加time。在当前城市赚钱状态(city, extra)可以转移到(city, extra1)时间增加1。初始状态(0, 0)时间为0。最终答案是min_{extra} dist[n-1][extra]。复杂度O(n * MAXC * log(n * MAXC))如果MAXC很大比如10^9会超时。所以需要进一步优化比如二分总时间。代码框架状态扩展Dijkstra假设MAXC不大import heapq class Solution: def minTimeToReach(self, n: int, roads: List[List[int]], money: int) - int: MAXC max(c for _,_,_,c in roads) # 建图 graph [[] for _ in range(n)] for u, v, t, c in roads: graph[u].append((v, t, c)) graph[v].append((u, t, c)) # dist[city][extra] min time INF 10**18 dist [[INF]*(MAXC1) for _ in range(n)] dist[0][0] 0 pq [(0, 0, 0)] # (time, city, extra) while pq: time, city, extra heapq.heappop(pq) if time dist[city][extra]: continue # 操作1: 在当前城市赚钱如果extra还没到顶 if extra MAXC: new_time time 1 if new_time dist[city][extra1]: dist[city][extra1] new_time heapq.heappush(pq, (new_time, city, extra1)) # 操作2: 走边 for nxt, t, cost in graph[city]: need cost if money extra need: # 钱够直接走extra不变钱花了但状态记录的是赚的钱花了不影响extra不对 # 这里状态设计有缺陷。extra是赚的钱花了就没了。所以走边后extra应该减少。 # 但减少多少需要花掉 cost但初始有 money。所以实际花费的是 max(0, cost - money) 部分来自extra。 # 更准确的状态应该是 (city, saved)saved 是当前拥有的总钱数。 # 但总钱数可能很大。我们重新定义状态 (city, earned)earned 是已经赚的钱。 # 当前总钱数 money earned。 # 走一条边花费 cost 走完后总钱数变为 money earned - cost。 # 所以 earned 变为 earned - cost如果 cost moneyearned。 # 但 earned 可能变成负数不会因为能走的边满足 cost moneyearned。 # 所以 new_earned earned - cost money? 不对。 # 我们定义状态 (city, total_money) 表示到达城市时的总钱数。但 total_money 范围大。 # 或者定义 (city, spent) 表示已经花掉的钱... # 这表明我们的状态设计需要调整。这是一个难点。 pass # 鉴于状态设计的复杂性此题更可能使用二分总时间的方法。 return -1总结第四题是典型的“带约束的最短路”问题。比赛中需要快速判断暴力状态扩展不可行并转向二分答案。二分总时间T后检查是否可行我们可以在起点花X分钟赚钱0XT然后带着moneyX的钱上路要求路径上每条边的cost moneyX并且路径总移动时间 T-X。这等价于寻找一条路径其最大边权cost为C路径时间为P使得存在X满足0XT,moneyX C且P T-X。由moneyX C得X C-money。结合P T-X得X T-P。所以需要存在X使得max(0, C-money) X T-P。即需要max(0, C-money) T-P。所以对于一条路径其可行条件是P max(0, C-money) T。因此我们只需要求出所有路径中P max(0, C-money)的最小值看是否 T。而P max(0, C-money)可以看作是一种新的边权吗不能直接套用最短路因为C是路径最大值。但我们可以枚举C对于每个C只考虑cost C的边然后求最短路P计算P max(0, C-money)。取所有C对应的最小值。C的可能取值就是所有边的cost。复杂度O(M * (N log N))可能可行。3. 比赛中的实战技巧与心态管理读题阶段5-10分钟打印体如果条件复杂在草稿纸上用自己习惯的符号重述条件。示例先行先看输入输出示例往往能快速理解题目意图和边界。数据范围非常重要它决定了算法复杂度的上限也暗示了可能的算法如n20可能状压DPn10^5需要 O(n log n)。编码阶段模块化将组合数计算、Dijkstra、并查集等常用算法写成干净的函数方便调试和复用。防御性编程在访问数组前检查下标在除法前检查除数是否为零在取模运算中对减法和除法要特别小心加 MOD 再取模。变量命名使用有意义的变量名如left,right而不是l,r避免写错。打印调试在本地 IDE 中对于复杂逻辑在关键位置打印中间变量值。调试阶段小数据测试自己构造几个小的、极端的数据如空数组、单个元素、全部相同、升序/降序。对拍如果时间允许写一个暴力算法例如 DFS 枚举用于小数据范围与你的优化算法对比结果。理性分析 WA不要盲目乱改。根据错误用例分析是算法逻辑错误、边界条件遗漏还是代码实现 bug如 off-by-one。心态与时间管理节奏感前两题通常较快争取 20 分钟内解决。给第三、四题留足时间。果断放弃如果一道题卡了 30 分钟以上毫无头绪先跳过检查其他题目是否有思路。最后再回来死磕。“无伤”策略除非有绝对把握否则不要盲目提交。先在本地充分测试包括边缘情况。一次 WA 不仅罚时更打乱心态。4. 从“知道”到“做到”建立你的检查清单赛后总结比刷题本身更重要。建议你为每种题型建立自己的“检查清单”模拟/数数题[ ] 循环边界是否正确还是[ ] 累加/累乘是否会溢出[ ] 是否需要取模取模运算是否正确[ ] 初始值和返回值是否覆盖了空输入、零输入贪心题[ ] 我的贪心策略真的正确吗能否举出反例[ ] 排序时排序键是否考虑了所有相关因素[ ] 在处理“优先队列”时入队和出队的条件是否完备动态规划题[ ] 状态定义是否包含了所有影响决策的维度[ ] 初始状态是否正确[ ] 状态转移方程是否覆盖了所有可能的情况[ ] 遍历顺序是否正确例如多维 DP 的循环嵌套顺序[ ] 答案是否在正确的状态中取得图论题[ ] 建图时边是单向还是双向[ ] 是否有重边是否需要处理[ ] 使用 BFS/Dijkstra 时是否正确处理了距离更新和队列推送[ ] 使用并查集时find函数是否有路径压缩二分查找题[ ] 循环条件是left right还是left right[ ] 更新边界是mid、mid1还是mid-1[ ] 最终返回值是left、right还是mid是否需要后处理5. 后续学习方向与资源推荐专题强化针对自己薄弱的题型如 DP、图论、数据结构进行集中刷题。LeetCode 上有许多优秀的题单。参加虚拟竞赛多用 LeetCode 的“模拟竞赛”功能或者参加 Codeforces、AtCoder 的定期比赛锻炼在压力下解题的能力。学习高手代码比赛结束后不要只看自己的排名。一定要去看排名靠前选手的代码。学习他们简洁的编码风格、巧妙的思路和高效的实现。工具化将自己常用的算法模板如快速幂、Dijkstra、线段树封装成可靠、无 bug 的代码片段保存在本地比赛时直接调用。算法竞赛之路初期拼的是知识广度与模板熟练度中后期拼的则是细心、稳健以及将复杂问题清晰拆解的“工程化”思维能力。希望这次“无伤 AK”的复盘能给你带来一些超越单场题解的启发。把每一场周赛都当成一次全真演练不仅练算法更练心态、练节奏、练防御性编程的习惯。坚持下去你不仅能看到排名的提升更会发现自己解决实际工程问题时思路变得更加清晰、严谨。