1. 赛题回顾与整体策略复盘第十二届蓝桥杯国赛B组的题目对于很多从省赛一路杀上来的选手来说是一个不小的挑战。国赛的题目风格往往更偏向于考察选手的综合能力包括对算法本质的理解、代码实现的严谨性以及在有限时间内的策略选择。我这次用Python参赛一方面是个人对Python的熟练度更高另一方面也是想验证一下Python在算法竞赛尤其是蓝桥杯这种对时间要求相对“宽容”的赛事中的实战表现。很多人觉得Python慢不适合打竞赛但我的体会是在蓝桥杯的赛制下Python的劣势并没有想象中那么大关键在于你如何扬长避短以及如何精准地理解题目意图。这次国赛B组的题目覆盖了动态规划、搜索、数学、字符串处理等多个经典领域没有出现特别偏、特别怪的题但每道题都设置了“坎”要么是数据规模需要你仔细设计算法要么是题意理解上容易有偏差。我的做题记录与其说是一份答案不如说是一次完整的解题思路复盘包含了当时考场上的思考过程、代码实现的关键点以及事后回顾时发现的更优解或潜在陷阱。对于准备冲击更高奖项的同学来说理解“为什么这么做”远比记住“怎么做”更重要。2. 真题逐题拆解与核心思路剖析下面我将按照题目顺序回忆版可能与官方顺序有细微出入结合我的解题代码逐一拆解每道题的考点、难点和实现细节。我会尽量还原考场上的思考链路并补充一些赛后总结的优化点。2.1 试题A货物摆放整数分解与因子枚举这道题是经典的因子枚举问题。题目大意是给定一个巨大的整数 n具体数值很大例如2021041820210418问有多少种三元组(a, b, c)满足a * b * c n并且a, b, c均为正整数。核心考点因子的高效枚举与去重计数。考场第一反应暴力三重循环遍历所有可能的 a, b, c 显然不可行因为 n 很大。必须从因子的角度入手。既然a*b*c n那么 a, b, c 都必须是 n 的因子。所以第一步是求出 n 的所有因子。实现细节与踩坑点因子枚举的优化求所有因子不能从 1 遍历到 n时间复杂度 O(n) 不可接受。标准做法是遍历到sqrt(n)。对于每个能整除 n 的 i我们就能得到一对因子i和n // i。需要特别注意完全平方数的情况避免重复添加。def get_factors(n): factors set() # 使用集合自动去重 for i in range(1, int(n**0.5) 1): if n % i 0: factors.add(i) factors.add(n // i) return list(factors)三重循环的优化即使得到了因子列表如果直接三重循环遍历所有因子假设因子个数为 m复杂度是 O(m³)如果 m 有几百个依然会超时。这里需要利用a*b*cn这个条件进行剪枝。我们可以先枚举 a 和 b然后检查 c n // (a * b) 是否为正整数并且是 n 的因子即 c 在因子集合中。这样复杂度就降到了 O(m²)。factors get_factors(n) factor_set set(factors) count 0 for a in factors: for b in factors: if a * b n or n % (a * b) ! 0: continue c n // (a * b) if c in factor_set: count 1结果运行上述逻辑即可得到正确的方案数。这道题在考场上属于“送分题”但必须保证因子枚举和循环剪枝的代码正确无误否则容易因小失大。2.2 试题B路径最短路与数论结合这道题是图论中最短路径问题的一个变种。题目描述了一个有2021个结点的图结点编号从1到2021。对于任意两个结点 i 和 j (i j)如果 j - i 21那么它们之间有一条无向边边权为 i 和 j 的最小公倍数lcm(i, j)。问从结点1到结点2021的最短路径长度是多少。核心考点最短路径算法Dijkstra或动态规划、最小公倍数计算。思路选择建图 Dijkstra这是最直观的想法。构建一个包含2021个节点的邻接表或邻接矩阵然后使用堆优化的Dijkstra算法求最短路。边数大约为2021*21/2量级完全在可接受范围内。Python的heapq库可以实现优先队列。动态规划由于图的特殊性节点编号有序且只能从小编号指向大编号边权有规律这本质上是一个线性DP问题。定义dp[i]为从节点1到节点 i 的最短距离。状态转移方程为dp[i] min(dp[j] lcm(j, i))其中i-21 j i。这种方式比Dijkstra更简洁效率也相当。我采用的DP解法import math def lcm(a, b): return a * b // math.gcd(a, b) n 2021 dp [float(inf)] * (n 1) dp[1] 0 # 起点距离为0 for i in range(2, n 1): # 只能从 i-21 到 i-1 的节点转移过来 start max(1, i - 21) for j in range(start, i): dp[i] min(dp[i], dp[j] lcm(j, i)) print(dp[n])注意事项math.gcd是Python内置的求最大公约数函数效率很高。DP数组初始化时dp[1]0其他为无穷大。内层循环的start需要和1取最大值防止下标越界。最终dp[2021]即为答案。这道题考察的是能否将图论问题转化为更高效的DP模型是国赛水平的典型题目。2.3 试题C砝码称重动态规划之背包变种这是经典的砝码称重问题变种。题目给出N个砝码重量分别为W1, W2, ..., WN。砝码可以放在天平的左右两边。问用这些砝码能称出多少种不同的正整重量。核心考点动态规划01背包的扩展重量可加可减。难点分析普通的01背包砝码只能放一边求的是sum(weights)以内的重量能否被组成。现在砝码可以放左边加或右边减或者不放。这意味着我们最终天平平衡时左右重量差可以表示多种重量。状态定义与转移 定义dp[i][j]为一个布尔值表示考虑前 i 个砝码能否称出重量差为 j 的状态。这里的 j 可以是负数、零、正数。为了用数组表示我们需要一个偏移量offset sum(weights)将下标范围平移到[0, 2*sum]其中joffset对应实际的重量差。状态转移有三种情况不选第 i 个砝码dp[i][j] | dp[i-1][j]把第 i 个砝码放到左边重物对面dp[i][j] | dp[i-1][j - w[i]](相当于增加了重量差)把第 i 个砝码放到右边和重物一起dp[i][j] | dp[i-1][j w[i]](相当于减少了重量差)代码实现关键n int(input()) weights list(map(int, input().split())) total sum(weights) # dp[i][j] 表示前i个砝码能称出重量差为(j-offset)的状态 offset total dp [[False] * (2 * total 1) for _ in range(n 1)] dp[0][offset] True # 初始状态重量差为0 for i in range(1, n 1): w weights[i-1] for j in range(2 * total 1): if dp[i-1][j]: dp[i][j] True # 不选 if j - w 0: dp[i][j - w] True # 放左边 if j w 2 * total: dp[i][j w] True # 放右边 # 统计所有可能称出的正整重量 ans_set set() for j in range(offset 1, 2 * total 1): # 只关心正重量差 if dp[n][j]: ans_set.add(j - offset) print(len(ans_set))经验之谈偏移量offset的技巧在处理有负下标的状态时非常常用。最终统计的是dp[n][j](j offset) 为 True 的数量因为题目问的是能称出的正整重量即重量差为正数。空间可以优化到一维但考场上为了思路清晰用二维更稳妥。这道题是动态规划的经典题目理解其状态设计是解题的关键。2.4 试题D括号序列动态规划之区间DP或线性DP这道题是括号匹配问题的加强版。给定一个长度为 n 的括号序列可能不完整包含(,),?其中?可以替换成(或)。问有多少种替换方案使得替换后的括号序列是合法的。核心考点动态规划对括号序列合法性的深刻理解。合法性定义一个括号序列合法需要满足整个序列的左右括号数量相等。对于序列的任意前缀左括号的数量不少于右括号的数量。思路演化暴力搜索每个?有两种选择复杂度 O(2^m)m是?的个数不可行。动态规划定义dp[i][j]表示考虑前 i 个字符当前未匹配的左括号数量为 j 的方案数。这里 j 必须始终 0。状态转移 遍历序列的每个字符s[i](1-indexed)如果s[i] (那么未匹配的左括号数必然增加1dp[i][j] dp[i-1][j-1](j1)。如果s[i] )那么必须有一个左括号来匹配未匹配数减1dp[i][j] dp[i-1][j1]。如果s[i] ?那么它可以是(也可以是)所以是上面两种情况的加和dp[i][j] dp[i-1][j-1] dp[i-1][j1](注意边界)。初始化与答案dp[0][0] 1表示考虑0个字符未匹配左括号为0的方案数为1空序列。 最终答案就是dp[n][0]表示考虑完所有n个字符后未匹配左括号数为0即序列合法的方案总数。代码示例s input().strip() n len(s) MOD 10**9 7 # 通常结果会很大需要取模 dp [[0] * (n 2) for _ in range(n 1)] # j的范围是[0, n] dp[0][0] 1 for i in range(1, n 1): ch s[i-1] for j in range(n 1): # 未匹配左括号数不会超过总长度 if ch ( or ch ?: if j 1: dp[i][j] (dp[i][j] dp[i-1][j-1]) % MOD if ch ) or ch ?: if j 1 n: dp[i][j] (dp[i][j] dp[i-1][j1]) % MOD print(dp[n][0] % MOD)踩坑提醒dp数组第二维的大小要开足够因为未匹配左括号数 j 最大可能是 n全是左括号。每一步计算最好都进行取模操作防止中间结果溢出。理解dp[i][j]中 j 的含义是“当前未匹配的左括号数”这是将括号匹配的前缀合法性条件完美融入状态的关键。这道题是区间DP/线性DP的经典好题需要反复体会。3. 考场时间分配与策略反思国赛的紧张氛围下时间管理至关重要。我的策略大致如下供大家参考第一阶段约1小时快速通读锁定目标拿到题目后用15-20分钟快速浏览所有题目对每道题的题型、难度有个初步判断。像“货物摆放”、“路径”这类题目思路比较直接属于必须拿下的分数我会标记为“优先做”。而“砝码称重”、“括号序列”需要更细致的推导和编码标记为“核心攻坚”。如果看到完全没思路的题这次比较幸运没有就先跳过。第二阶段约2.5小时稳扎稳打实现基础分按照“优先做”的顺序快速且准确地编码、调试、验证样例。这个阶段的目标是确保所有思路清晰的题目都做对不犯低级错误如数组开小、边界条件漏掉。每做出一道题立即在代码头部加上清晰的注释并在草稿纸上记录下关键思路和答案方便最后检查。这个阶段结束后至少应该拿到大部分基础分。第三阶段约1小时攻坚克难冲击高分集中精力解决“核心攻坚”题。这时需要沉下心来仔细分析题目条件在草稿纸上推演状态定义和转移方程。对于动态规划类题目先想清楚再写代码避免反复重构。如果一道题卡了超过30分钟还没有清晰思路要果断决策是继续深挖还是转去检查已做题目或者尝试暴力方法骗分。国赛部分题目数据有梯度有时暴力也能拿到可观分数。第四阶段最后30分钟全面检查查漏补缺停止攻击新题。从头到尾检查每道已提交的代码重新阅读题目确认输入输出格式用题目给的样例和自己构造的临界样例如最小输入、最大输入、特殊情况进行测试检查是否有明显的逻辑漏洞或笔误。对于Python要特别注意递归深度、列表索引、整数溢出Python本身无此问题但取模要注意等问题。我的反思 这次比赛我在“括号序列”这道题上花费了比预期多的时间。起初我试图用记忆化搜索去解决思路有点绕导致调试不畅。后来果断切换到上述的线性DP解法才顺利通过。这给我的教训是对于经典模型变种题优先考虑最标准、最稳妥的DP定义不要过早追求“巧妙”的解法。在考场上正确性和稳定性永远排在第一位。4. Python在算法竞赛中的优劣势与编码技巧通过这次国赛我对Python参赛有了更深的理解。优势编码速度快语法简洁内置数据结构list, dict, set强大能极大缩短编码时间让你有更多时间思考算法本身。代码可读性强清晰的代码结构有助于在调试时快速定位问题。大整数无忧Python原生支持大整数运算在做一些数论题如“货物摆放”中处理大数时非常省心。丰富的内置库mathgcd, sqrt、heapq优先队列、bisect二分等库在竞赛中非常实用。劣势与应对策略运行速度慢这是最大的劣势。应对策略包括避免低效操作多用list.append()和list comprehension少用拼接字符串在循环内尽量减少函数调用和属性访问。使用PyPy解释器蓝桥杯环境通常提供PyPy。PyPy对很多循环密集型代码有极佳的JIT优化速度可能比CPython快数倍甚至十倍。强烈建议在提交时选择PyPy。优化算法复杂度这是根本。Python的常数因子大O(nlogn)的算法可能比O(n²)的算法在更小的n时就体现出优势因此要更追求最优算法。递归深度限制默认递归深度约1000对于深搜DFS题目可能不够。可以用sys.setrecursionlimit(1000000)提高限制但更推荐使用显式栈进行迭代或者确保递归深度在安全范围内。内存占用Python对象开销大。在处理超大二维数组时如dp[10000][10000]要警惕内存超限。可以考虑使用array模块、numpy如果允许或者用list of lists时注意引用问题。实用的编码技巧快速输入对于大量数据输入使用sys.stdin.read().split()一次性读取再处理比循环调用input()快得多。import sys data sys.stdin.read().split() n int(data[0]) # ... 后续用 data[1], data[2]...常用模板函数提前写好并熟记一些模板如Dijkstra、快速幂、并查集、素数筛等考试时直接套用节省时间。善用本地调试在本地用文件重定向模拟输入输出可以高效调试。# 假设代码为 solve.py输入数据在 input.txt python solve.py input.txt5. 从做题到备赛给后来者的训练建议如果你也打算用Python挑战蓝桥杯国赛以下是我结合自身经验的一些建议1. 夯实基础算法与数据结构不要因为Python简单就忽视基础。动态规划线性DP、区间DP、树形DP、状压DP、搜索DFS、BFS、剪枝、图论最短路、最小生成树、拓扑排序、数论gcd、lcm、素数、同余、字符串KMP、字典树等核心内容必须熟练掌握其思想和Python实现。推荐在洛谷、AcWing等平台进行专题训练。2. 进行严格的模拟赛训练每周至少进行一次完整的、限时的模拟赛。使用蓝桥杯真题或类似难度的套题。严格模拟考场环境不能查资料、不能调试器单步跟踪只用print调试、按时交卷。赛后不仅要看答案更要复盘当时为什么没想到思路卡在哪里时间分配是否合理这个过程是提升应试能力最有效的途径。3. 建立自己的“代码库”将常用的算法模板、工具函数如快读、离散化、二维坐标处理整理成一个个独立的、经过验证的代码片段。比赛时可以直接复制粘贴但要确保你完全理解每一行代码避免因模板错误而失分。4. 刻意练习“题解翻译”能力看到一道题的优秀题解特别是C版后尝试不看他人的Python代码自己独立将其思路翻译成Python代码。这个过程能极大地锻炼你对算法本质的理解和跨语言实现能力。5. 关注官方大纲与历年真题蓝桥杯的命题有很强的延续性。历年真题尤其是近三年的国赛题是最宝贵的复习资料。通过真题你可以熟悉出题风格、常见考点和难度分布。官方公布的大纲也是复习的指挥棒。国赛的舞台比拼的不仅是知识储备更是心态、策略和应变能力。这次用Python完成B组的挑战让我深刻体会到语言只是工具对问题的洞察力和扎实的算法功底才是决定上限的关键。希望这份详细的做题记录和复盘能为你照亮一些前行的路。在算法的世界里每一行代码都是思考的结晶每一次AC都是对努力的馈赠。祝你备赛顺利赛场得意。