1. 项目概述一份面向实战的真题解析指南最近在整理资料时翻到了2021年蓝桥杯Python组国赛的真题。作为国内编程竞赛的一个重要风向标这份题目不仅是对参赛者算法和编程能力的终极考验其背后蕴含的解题思路和技巧对于任何希望提升Python实战能力、理解算法应用场景的朋友来说都是一笔宝贵的财富。我花了些时间重新梳理了这套题并决定写一份更“接地气”的解析。市面上很多解析要么过于学术化充斥着复杂的数学推导要么过于简略只给个最终答案让人知其然不知其所以然。我的目标是把每道题掰开揉碎用最直白的语言讲清楚“题目到底想考什么”、“为什么这么解”以及“代码怎么写才既高效又易懂”。这份解析适合几类朋友首先是正在备赛蓝桥杯或其他算法竞赛的选手可以直接作为高质量的模拟题和复习材料其次是自学Python已经掌握了基础语法想挑战更有趣、更综合项目的开发者这些题目能很好地锻炼你的逻辑思维和工程化编码能力最后哪怕是经验丰富的程序员看看这些巧妙的题目设计也能从中获得一些解决实际问题的灵感。接下来我会按照题目顺序逐一拆解不仅给出代码更会重点分享我在解题过程中踩过的坑、优化的心路历程以及一些通用的解题技巧。2. 真题整体分析与解题策略总览2021年的国赛题目整体上延续了蓝桥杯“重思维、考基础、贴近应用”的风格。难度梯度设置合理既有考验基础编程和细心程度的送分题也有需要深刻理解算法思想的中等题更有那么一两道需要灵光一现或者扎实的数论、动态规划功底的压轴题。通做一遍下来我感觉这一年对“Python特性”的考察更加深入了不仅仅是把C的算法用Python语法写出来而是需要你真正利用好Python的高阶函数、强大的内置库如collections,itertools,math以及简洁的语法糖来简化代码提升可读性和运行效率。在开始具体题目之前我想先分享几个贯穿始终的解题策略这也是我多年刷题和教学总结出的经验策略一彻底理解题意与数据范围。这是老生常谈但也是最容易出错的一步。国赛题目的描述有时会比较绕一定要自己用几个小例子验证一下对题意的理解是否正确。更重要的是关注数据范围它直接决定了你能用什么算法。比如数据规模n10^3你可能可以用O(n^2)的暴力如果n10^5就必须考虑O(n log n)或O(n)的算法了。Python在处理大数据量时尤其要注意时间复杂度一个O(n^2)的循环很可能就会超时。策略二先有思路再动键盘。不要一上来就着急写代码。先在草稿纸上画一画推演一下简单的测试用例。对于复杂问题尝试分解成几个子问题。想清楚大致的算法框架比如这题是不是用广度优先搜索BFS是不是动态规划状态怎么定义再开始编码。这样能避免写到一半发现思路错误推倒重来的尴尬。策略三善用Python“武器库”。Python之所以在算法竞赛中越来越受欢迎其丰富的内置数据结构和高阶函数功不可没。判断元素是否存在用setO(1)查找需要计数用collections.Counter需要维护最近相关元素用deque队列/栈需要排序用sorted配合key参数需要排列组合用itertools.permutations/combinations。这些工具用好了代码能简洁一半。策略四调试与验证。写完代码先用题目给的样例测试。通过后不要急着提交自己构造一些边界情况进行测试比如空输入、极值输入、有序/无序的特殊情况等。对于无法一眼看出答案的题可以写一个“暴力解法”通常时间复杂度高但正确性容易保证来对拍验证你的“优化解法”的正确性。掌握了这些基本策略我们就能更有底气地面对每一道具体的题目了。下面我将挑选其中最具代表性、最考验思维的几道题进行深度解析。3. 核心真题详解与代码实现3.1 试题A纯质数送分题的“陷阱”这道题通常是第一题考察基础编程能力和细心程度。题目要求找出从1到NN是一个给定的正整数具体数值在题目中给出比如20210605之间所有本身是质数并且其每一个十进制位上的数字也都是质数的数称之为“纯质数”。质数数字只有2, 3, 5, 7。解题思路拆解判断质数这是基础功能。需要写一个is_prime(n)函数。注意1不是质数。对于小的n可以用试除法检查从2到sqrt(n)之间的整数是否能整除n。提取数位对于每一个待检查的数需要将其十进制表示的每一位数字提取出来。双重判断首先这个数本身必须是质数。其次它的每一位数字必须在集合{2,3,5,7}中。遍历与计数从1遍历到N对每个数进行上述判断符合条件的计数加1。代码实现与优化技巧import math def is_prime(n): 判断一个数是否为质数 if n 2: return False if n 2: return True if n % 2 0: return False # 只检查奇数因子到sqrt(n)为止 for i in range(3, int(math.sqrt(n)) 1, 2): if n % i 0: return False return True def is_pure_prime(n): 判断一个数是否为纯质数 # 首先判断每一位数字 digit_set {2, 3, 5, 7} for digit in str(n): if digit not in digit_set: return False # 每一位都合格再判断整个数是否为质数 return is_prime(n) def main(): N 20210605 # 示例N实际以题目为准 count 0 # 注意由于纯质数的每一位只能是2,3,5,7所以它本身不可能以0,1,4,6,8,9结尾更不可能是偶数除了2。 # 我们可以直接遍历但这里为了逻辑清晰先按定义实现。 for num in range(1, N 1): if is_pure_prime(num): count 1 print(count) if __name__ __main__: main()注意事项与避坑指南性能陷阱如果N很大比如上千万对每一个数都调用is_prime函数进行从2到sqrt(n)的检查总计算量会非常大可能导致超时。一个重要的优化是先判断数位再判断质数。因为判断数位O(k)k是数字位数的代价远小于判断大数质数。如果数位都不符合直接跳过耗时的质数判断。边界条件1不是质数。数字0和1也不是质数数字所以任何包含0或1的数都不可能是纯质数。特殊数字22是质数且它的数位‘2’也是质数数字所以2是纯质数。在循环中要能正确处理。进一步优化更激进的做法是既然每位只能是2,3,5,7我们可以用DFS深度优先搜索直接生成所有由这些数字组成的、不超过N的数然后只对这些生成的数进行质数判断。这样需要检查的数会少很多。但在本题给定的N下通常直接的遍历优化后也能通过。3.2 试题B完全日期日期处理与模拟这类日期计算题是蓝桥杯的常客考察对编程语言日期库的熟悉程度或者模拟能力。题目定义“完全日期”为一个日期的年、月、日各位数字之和是一个完全平方数如1,4,9,16...。要求计算在两个给定日期之间包含起止日期有多少个完全日期。解题思路拆解日期遍历核心是如何从一个日期安全、高效地遍历到另一个日期。我们可以使用Python的datetime.date模块它处理日期加减和比较非常方便。数位和计算对于每一个日期将其年、月、日分别取出计算各自每一位数字的和然后相加。完全平方数判断判断这个和是否是完全平方数。最直接的方法是int(sqrt(s))**2 s。计数符合条件则计数加一。代码实现import datetime import math def digit_sum(n): 计算一个整数的各位数字之和 return sum(int(d) for d in str(n)) def is_perfect_square(num): 判断一个数是否是完全平方数 if num 0: return False root int(math.sqrt(num)) return root * root num def count_perfect_dates(start_str, end_str): 计算两个日期之间的完全日期数量 # 解析日期字符串格式假设为YYYYMMDD start_date datetime.date(int(start_str[:4]), int(start_str[4:6]), int(start_str[6:8])) end_date datetime.date(int(end_str[:4]), int(end_str[4:6]), int(end_str[6:8])) current_date start_date delta datetime.timedelta(days1) count 0 while current_date end_date: # 计算年月日的数位和 s digit_sum(current_date.year) digit_sum(current_date.month) digit_sum(current_date.day) if is_perfect_square(s): count 1 current_date delta return count # 示例假设题目给出的起止日期是20010101和20211231 if __name__ __main__: result count_perfect_dates(20010101, 20211231) print(result)实操心得日期库是利器强烈建议使用datetime模块。自己模拟闰年、月份天数很容易出错。datetime.date会自动处理这些细节timedelta可以方便地进行日期加减。遍历效率对于跨度几十年的日期逐天遍历完全可行计算量不大。不必担心性能。输入格式务必仔细看题目输入的日期格式可能是空格分隔的年月日也可能是字符串。上述代码假设了连续的8位数字字符串你需要根据实际题目要求调整解析逻辑。边界包含注意题目是否包含起止日期上述循环条件是表示包含结束日期。3.3 试题C最小权值动态规划典型题这是一道经典的动态规划DP问题可能以二叉树构建、最优排列等形式出现。题目通常描述为给定N个节点要求构建一棵二叉树或类似结构每个节点有一个权重或代价树的权值定义为所有节点的“深度乘以权重”之和。问如何构造树使得这个总权值最小。解题思路拆解以二叉树为例识别DP模型求最优解且问题可以分解为子问题左子树和右子树。典型的区间DP或树形DP。定义状态dp[i]表示用 i 个节点所能构成的最小权值。或者如果节点有权重差异状态可能需要二维dp[i][j]表示从第i个节点到第j个节点构成子树的最小权值。状态转移对于dp[n]我们需要枚举根节点是谁假设根节点是第k个节点那么左子树有k-1个节点右子树有n-k个节点。树的权值 左子树的权值 右子树的权值 根节点的权重 * 1因为根深度为1这里需要根据题目具体定义调整有时是深度有时是到根的距离。但更重要的是左右子树的所有节点深度都增加了1所以它们的贡献要在其子问题权值的基础上额外加上它们各自节点的权重之和因为每个节点的深度1权值贡献就多一份它的权重。初始化dp[0] 0空树权值为0。计算顺序从小到大计算dp[i]。假设一个简化模型有N个节点每个节点权重为1。定义树的权值为所有节点的“深度”之和。求最小权值。 这个问题等价于构建一棵完全二叉树但更精确的解法是霍夫曼树的思想或者直接推导公式。但用DP可以更通用。代码实现简化版模型def min_tree_weight(N): 假设每个节点权重为1权值所有节点深度和。 求N个节点构成的二叉树的最小深度和。 这是一个经典的DP问题状态转移为 dp[n] min_{1kn} { dp[k-1] dp[n-k] n } 不对。 正确的对于一棵树总深度和 左子树深度和 右子树深度和 左子树节点数 右子树节点数。 因为左子树所有节点的深度在作为子树时都加了1。 所以 dp[n] min_{0kn-1} { dp[k] dp[n-1-k] n-1 } 其中k是左子树节点数n-1-k是右子树节点数根节点占1个。 n-1 是除了根以外的节点数它们在新树中深度都增加了1。 dp [0] * (N 1) # dp[0] 0 已经初始化 for n in range(1, N 1): dp[n] float(inf) # 左子树节点数从0到n-1 for k in range(n): # k是左子树节点数 left_cnt k right_cnt n - 1 - k # 总节点数n 1(根) left_cnt right_cnt current_weight dp[left_cnt] dp[right_cnt] (n - 1) # n-1是除根外节点数 if current_weight dp[n]: dp[n] current_weight return dp[N] if __name__ __main__: N 10 # 示例 print(f用{N}个节点权重1能构建的二叉树最小深度和为{min_tree_weight(N)})深度解析与常见误区状态转移方程的理解这是本题最难的地方。为什么是加n-1我们定义dp[x]是x个节点构成的子树在其自身根节点深度为0的体系下的总深度和。当这棵子树作为另一棵树的左子树时它的所有节点深度都要1因此它对新的总深度和的贡献就变成了dp[x] x因为每个节点都多贡献了1共x个节点。在状态转移时我们合并左子树、右子树和根节点形成新树新树的总深度和 (dp[left] left) (dp[right] right) 0根节点在新树中深度为0但在最终统计时根深度是0吗这取决于定义。如果题目定义根深度为1那么需要调整。务必根据题目具体定义画图推导出正确的转移方程。时间复杂度上述DP是O(N^2)的如果N达到10^3或更大可能需要优化如四边形不等式优化。但在蓝桥杯国赛中N通常不会太大O(N^2)可以接受。空树处理dp[0]通常表示空树其权值为0。这在转移方程中很重要。3.4 试题D覆盖问题状态压缩DP或搜索这类问题通常描述为用一个给定形状的小图形如1x2的多米诺骨牌、L形瓦片等去覆盖一个M x N的网格问有多少种不同的覆盖方法。网格中可能有一些障碍物。解题思路拆解以多米诺骨牌覆盖2xN网格为例这是最简单的:对于2xN网格用1x2的骨牌覆盖这是一个经典的斐波那契数列问题。但对于更复杂的网格和形状就需要用状态压缩动态规划。状态压缩DP核心思想状态定义dp[i][state]表示处理到第i列时当前列的状态为state的方案数。state是一个二进制数它的每一位表示当前列对应行的格子是否已经被从左边伸过来的骨牌占据或者说当前格子是否已经被覆盖。通常1表示该位置已被占据无需再覆盖0表示该位置是空的需要由当前列或下一列的骨牌来覆盖。状态转移从dp[i-1][prev_state]转移到dp[i][curr_state]。我们需要枚举所有合法的prev_state和curr_state的组合以及在这一列放置骨牌的方式使得prev_state和curr_state共同决定了第i-1列哪些位置需要被竖放骨牌覆盖。在第i列我们可以选择横放骨牌覆盖第i列和第i1列的两个相邻行这会影响curr_state对下一列状态的表示。初始化dp[0][0] 1表示第0列之前没有任何格子被占据。结果最终答案是dp[N][0]表示处理完所有N列后没有骨牌延伸到网格之外状态为0。这是一个非常抽象的过程我们以一个具体例子说明用1x2骨牌覆盖3xN网格。def domino_tiling_3xN(N): 计算用1x2多米诺骨牌覆盖3xN网格的方案数。 状态压缩DP状态表示当前列各行的覆盖情况0空1已被上一列延伸的竖牌覆盖。 # 预处理所有合法的状态转移对 (prev_state, curr_state) # 状态是0到7(2^3-1)的整数二进制位表示三行 transitions [] for prev in range(8): # 前一列状态 for curr in range(8): # 当前列状态 ok True # 检查当前列的空位即prev中为0且curr中也为0的位置能否被横牌或竖牌覆盖 # 更通用的方法是使用DFS来搜索这一列的所有放置方式 # 这里为了简化我们换一种更清晰的实现方式DFS按行放置 # 另一种更清晰的实现轮廓线DP插头DP思想但代码复杂。 # 对于3xN有经典结论当N为奇数时方案数为0偶数时满足递推式 a[n] 4*a[n-2] - a[n-4] # 这里为了展示状态压缩DP思想我们实现一个更简单的2xN的例子。 def domino_tiling_2xN(N): 2xN网格覆盖方案数就是斐波那契数列。用DP模拟 if N 0: return 1 if N 1: return 1 # 只能竖放 dp [0] * (N 1) dp[0] 1 # 空棋盘一种方式 dp[1] 1 # 2x1只能竖放一种 for i in range(2, N 1): # 第i列的情况 # 1. 最后一列是竖放的两个格子那么方案数等于dp[i-1] # 2. 最后两列是被一个横放的骨牌覆盖那么方案数等于dp[i-2] dp[i] dp[i-1] dp[i-2] return dp[N] if __name__ __main__: N 10 print(f覆盖2x{N}网格的方案数为{domino_tiling_2xN(N)})注意事项与高阶技巧复杂度状态压缩DP的状态数是2^M * NM是行数。当M较大如10时状态数爆炸无法使用。这时可能需要更复杂的插头DP或者找数学规律。预处理合法转移对于固定的M所有合法的(prev_state, curr_state)对是可以预先计算出来的这样在DP循环中只需遍历这些合法对而不是所有组合能提升效率。滚动数组优化由于dp[i]只依赖于dp[i-1]可以用两个一维数组交替使用节省空间。调试技巧对于这类复杂DP先用小规模数据如N1,2,3手动计算答案然后与程序输出对比确保状态定义和转移正确。4. 通用解题技巧与考场策略做完一套真题除了弄懂每一道题更重要的是提炼出通用的方法和考场上的应对策略。以下是我总结的几点1. 输入输出一定要熟练。蓝桥杯是OI赛制需要从标准输入读取数据向标准输出写入结果。务必提前准备好输入输出模板并熟练使用。对于Python常用import sys # 读取一行转换为整数列表 data list(map(int, sys.stdin.readline().split())) # 读取多行直到文件结束 for line in sys.stdin: n int(line.strip()) # ... 处理注意大量输入时使用sys.stdin.read()一次性读取再处理可能更快但要注意内存。2. 时间复杂度估算与算法选择。拿到题先看数据规模。根据经验n 10: 可能是暴力搜索、全排列。n 20: 状态压缩DP/DFS。n 1000: O(n^2)的动态规划、朴素Dijkstra等。n 10^5: 需要O(n log n)的算法如排序、优先队列、线段树、二分答案。n 10^6: 通常需要O(n)的算法如双指针、单调栈、前缀和。3. 空间复杂度注意。Python的列表、字典比较耗内存。如果开一个10^6大小的整数列表内存大约8MB因为Python int对象开销大可以接受。但如果开10^6 * 10^6的二维列表肯定爆内存。遇到需要大数组的题考虑使用array模块或numpy如果允许或者优化数据结构。4. 调试与对拍。编写一个简单的暴力解法通常用于小数据与你的优化解法用随机数据对比结果。这是确保算法正确性的有效手段尤其是在考试中时间紧张容易考虑不周。5. 不会做的题怎么办暴力骗分如果数据有部分小规模的分支写一个暴力程序确保拿到这些分。找规律对于数学题或图形题可以手动模拟小数据看看结果是否有规律比如是斐波那契数列、卡特兰数等。输出特例如果题目有多个询问有些询问的答案可能很简单比如边界情况直接输出这些答案也能得分。5. 备考资源与进阶学习建议如果你想在蓝桥杯或类似的算法竞赛中取得好成绩仅靠真题是不够的需要系统学习和练习。1. 系统学习算法知识体系基础数据结构数组、链表、栈、队列、哈希表、堆优先队列。基础算法排序、二分查找、双指针、前缀和与差分。搜索深度优先搜索DFS、广度优先搜索BFS、回溯、剪枝。动态规划DP线性DP、区间DP、状态压缩DP、树形DP。这是重点也是难点需要大量练习。图论最短路Dijkstra, Floyd、最小生成树Prim, Kruskal、拓扑排序。数学质数筛法、最大公约数/最小公倍数、快速幂、简单组合数学。2. 刷题平台推荐蓝桥杯官方练习系统有历年真题是最直接的备考资料。AcWing有很多蓝桥杯辅导课和真题讲解社区活跃。洛谷题目分类清晰适合按知识点刷题。LeetCode虽然偏重面试但其“题库”中的算法题目质量很高可以用来巩固基础算法。3. 关于Python在竞赛中的使用优势语法简洁开发速度快内置库强大collections,itertools,heapq,bisect等对于某些高精度计算或字符串处理比C方便。劣势运行速度慢递归深度有限默认约1000层内存开销大。因此用Python解题更考验算法的优化程度必须选择时间复杂度更优的算法。必会模块collections:deque双向队列用于BFS、Counter计数、defaultdict带默认值的字典。itertools:permutations排列、combinations组合、product笛卡尔积用于暴力枚举。heapq: 堆优先队列用于Dijkstra算法等。bisect: 二分查找。math: 数学函数gcd最大公约数、sqrt等。functools:lru_cache用于实现记忆化搜索简化DP代码。最后编程竞赛的备赛是一个长期积累的过程没有捷径。从看懂每一道真题的解析开始到自己独立复现代码再到举一反三解决类似问题每一步都算数。我当年备赛时一个类型的题目比如DP会集中刷上十几道甚至几十道直到形成条件反射看到题目描述就能大概猜到状态该怎么定义。希望这份针对2021年国赛真题的解析能成为你算法学习之路上一块有用的垫脚石。如果在练习中遇到任何问题或者对某道题有更巧妙的解法欢迎随时交流。 
长河君 · 2026/8/28 7:36:11 · 阅读 1.2k 蓝桥杯Python国赛真题解析：从纯质数到动态规划的实战技巧
1. 项目概述一份面向实战的真题解析指南最近在整理资料时翻到了2021年蓝桥杯Python组国赛的真题。作为国内编程竞赛的一个重要风向标这份题目不仅是对参赛者算法和编程能力的终极考验其背后蕴含的解题思路和技巧对于任何希望提升Python实战能力、理解算法应用场景的朋友来说都是一笔宝贵的财富。我花了些时间重新梳理了这套题并决定写一份更“接地气”的解析。市面上很多解析要么过于学术化充斥着复杂的数学推导要么过于简略只给个最终答案让人知其然不知其所以然。我的目标是把每道题掰开揉碎用最直白的语言讲清楚“题目到底想考什么”、“为什么这么解”以及“代码怎么写才既高效又易懂”。这份解析适合几类朋友首先是正在备赛蓝桥杯或其他算法竞赛的选手可以直接作为高质量的模拟题和复习材料其次是自学Python已经掌握了基础语法想挑战更有趣、更综合项目的开发者这些题目能很好地锻炼你的逻辑思维和工程化编码能力最后哪怕是经验丰富的程序员看看这些巧妙的题目设计也能从中获得一些解决实际问题的灵感。接下来我会按照题目顺序逐一拆解不仅给出代码更会重点分享我在解题过程中踩过的坑、优化的心路历程以及一些通用的解题技巧。2. 真题整体分析与解题策略总览2021年的国赛题目整体上延续了蓝桥杯“重思维、考基础、贴近应用”的风格。难度梯度设置合理既有考验基础编程和细心程度的送分题也有需要深刻理解算法思想的中等题更有那么一两道需要灵光一现或者扎实的数论、动态规划功底的压轴题。通做一遍下来我感觉这一年对“Python特性”的考察更加深入了不仅仅是把C的算法用Python语法写出来而是需要你真正利用好Python的高阶函数、强大的内置库如collections,itertools,math以及简洁的语法糖来简化代码提升可读性和运行效率。在开始具体题目之前我想先分享几个贯穿始终的解题策略这也是我多年刷题和教学总结出的经验策略一彻底理解题意与数据范围。这是老生常谈但也是最容易出错的一步。国赛题目的描述有时会比较绕一定要自己用几个小例子验证一下对题意的理解是否正确。更重要的是关注数据范围它直接决定了你能用什么算法。比如数据规模n10^3你可能可以用O(n^2)的暴力如果n10^5就必须考虑O(n log n)或O(n)的算法了。Python在处理大数据量时尤其要注意时间复杂度一个O(n^2)的循环很可能就会超时。策略二先有思路再动键盘。不要一上来就着急写代码。先在草稿纸上画一画推演一下简单的测试用例。对于复杂问题尝试分解成几个子问题。想清楚大致的算法框架比如这题是不是用广度优先搜索BFS是不是动态规划状态怎么定义再开始编码。这样能避免写到一半发现思路错误推倒重来的尴尬。策略三善用Python“武器库”。Python之所以在算法竞赛中越来越受欢迎其丰富的内置数据结构和高阶函数功不可没。判断元素是否存在用setO(1)查找需要计数用collections.Counter需要维护最近相关元素用deque队列/栈需要排序用sorted配合key参数需要排列组合用itertools.permutations/combinations。这些工具用好了代码能简洁一半。策略四调试与验证。写完代码先用题目给的样例测试。通过后不要急着提交自己构造一些边界情况进行测试比如空输入、极值输入、有序/无序的特殊情况等。对于无法一眼看出答案的题可以写一个“暴力解法”通常时间复杂度高但正确性容易保证来对拍验证你的“优化解法”的正确性。掌握了这些基本策略我们就能更有底气地面对每一道具体的题目了。下面我将挑选其中最具代表性、最考验思维的几道题进行深度解析。3. 核心真题详解与代码实现3.1 试题A纯质数送分题的“陷阱”这道题通常是第一题考察基础编程能力和细心程度。题目要求找出从1到NN是一个给定的正整数具体数值在题目中给出比如20210605之间所有本身是质数并且其每一个十进制位上的数字也都是质数的数称之为“纯质数”。质数数字只有2, 3, 5, 7。解题思路拆解判断质数这是基础功能。需要写一个is_prime(n)函数。注意1不是质数。对于小的n可以用试除法检查从2到sqrt(n)之间的整数是否能整除n。提取数位对于每一个待检查的数需要将其十进制表示的每一位数字提取出来。双重判断首先这个数本身必须是质数。其次它的每一位数字必须在集合{2,3,5,7}中。遍历与计数从1遍历到N对每个数进行上述判断符合条件的计数加1。代码实现与优化技巧import math def is_prime(n): 判断一个数是否为质数 if n 2: return False if n 2: return True if n % 2 0: return False # 只检查奇数因子到sqrt(n)为止 for i in range(3, int(math.sqrt(n)) 1, 2): if n % i 0: return False return True def is_pure_prime(n): 判断一个数是否为纯质数 # 首先判断每一位数字 digit_set {2, 3, 5, 7} for digit in str(n): if digit not in digit_set: return False # 每一位都合格再判断整个数是否为质数 return is_prime(n) def main(): N 20210605 # 示例N实际以题目为准 count 0 # 注意由于纯质数的每一位只能是2,3,5,7所以它本身不可能以0,1,4,6,8,9结尾更不可能是偶数除了2。 # 我们可以直接遍历但这里为了逻辑清晰先按定义实现。 for num in range(1, N 1): if is_pure_prime(num): count 1 print(count) if __name__ __main__: main()注意事项与避坑指南性能陷阱如果N很大比如上千万对每一个数都调用is_prime函数进行从2到sqrt(n)的检查总计算量会非常大可能导致超时。一个重要的优化是先判断数位再判断质数。因为判断数位O(k)k是数字位数的代价远小于判断大数质数。如果数位都不符合直接跳过耗时的质数判断。边界条件1不是质数。数字0和1也不是质数数字所以任何包含0或1的数都不可能是纯质数。特殊数字22是质数且它的数位‘2’也是质数数字所以2是纯质数。在循环中要能正确处理。进一步优化更激进的做法是既然每位只能是2,3,5,7我们可以用DFS深度优先搜索直接生成所有由这些数字组成的、不超过N的数然后只对这些生成的数进行质数判断。这样需要检查的数会少很多。但在本题给定的N下通常直接的遍历优化后也能通过。3.2 试题B完全日期日期处理与模拟这类日期计算题是蓝桥杯的常客考察对编程语言日期库的熟悉程度或者模拟能力。题目定义“完全日期”为一个日期的年、月、日各位数字之和是一个完全平方数如1,4,9,16...。要求计算在两个给定日期之间包含起止日期有多少个完全日期。解题思路拆解日期遍历核心是如何从一个日期安全、高效地遍历到另一个日期。我们可以使用Python的datetime.date模块它处理日期加减和比较非常方便。数位和计算对于每一个日期将其年、月、日分别取出计算各自每一位数字的和然后相加。完全平方数判断判断这个和是否是完全平方数。最直接的方法是int(sqrt(s))**2 s。计数符合条件则计数加一。代码实现import datetime import math def digit_sum(n): 计算一个整数的各位数字之和 return sum(int(d) for d in str(n)) def is_perfect_square(num): 判断一个数是否是完全平方数 if num 0: return False root int(math.sqrt(num)) return root * root num def count_perfect_dates(start_str, end_str): 计算两个日期之间的完全日期数量 # 解析日期字符串格式假设为YYYYMMDD start_date datetime.date(int(start_str[:4]), int(start_str[4:6]), int(start_str[6:8])) end_date datetime.date(int(end_str[:4]), int(end_str[4:6]), int(end_str[6:8])) current_date start_date delta datetime.timedelta(days1) count 0 while current_date end_date: # 计算年月日的数位和 s digit_sum(current_date.year) digit_sum(current_date.month) digit_sum(current_date.day) if is_perfect_square(s): count 1 current_date delta return count # 示例假设题目给出的起止日期是20010101和20211231 if __name__ __main__: result count_perfect_dates(20010101, 20211231) print(result)实操心得日期库是利器强烈建议使用datetime模块。自己模拟闰年、月份天数很容易出错。datetime.date会自动处理这些细节timedelta可以方便地进行日期加减。遍历效率对于跨度几十年的日期逐天遍历完全可行计算量不大。不必担心性能。输入格式务必仔细看题目输入的日期格式可能是空格分隔的年月日也可能是字符串。上述代码假设了连续的8位数字字符串你需要根据实际题目要求调整解析逻辑。边界包含注意题目是否包含起止日期上述循环条件是表示包含结束日期。3.3 试题C最小权值动态规划典型题这是一道经典的动态规划DP问题可能以二叉树构建、最优排列等形式出现。题目通常描述为给定N个节点要求构建一棵二叉树或类似结构每个节点有一个权重或代价树的权值定义为所有节点的“深度乘以权重”之和。问如何构造树使得这个总权值最小。解题思路拆解以二叉树为例识别DP模型求最优解且问题可以分解为子问题左子树和右子树。典型的区间DP或树形DP。定义状态dp[i]表示用 i 个节点所能构成的最小权值。或者如果节点有权重差异状态可能需要二维dp[i][j]表示从第i个节点到第j个节点构成子树的最小权值。状态转移对于dp[n]我们需要枚举根节点是谁假设根节点是第k个节点那么左子树有k-1个节点右子树有n-k个节点。树的权值 左子树的权值 右子树的权值 根节点的权重 * 1因为根深度为1这里需要根据题目具体定义调整有时是深度有时是到根的距离。但更重要的是左右子树的所有节点深度都增加了1所以它们的贡献要在其子问题权值的基础上额外加上它们各自节点的权重之和因为每个节点的深度1权值贡献就多一份它的权重。初始化dp[0] 0空树权值为0。计算顺序从小到大计算dp[i]。假设一个简化模型有N个节点每个节点权重为1。定义树的权值为所有节点的“深度”之和。求最小权值。 这个问题等价于构建一棵完全二叉树但更精确的解法是霍夫曼树的思想或者直接推导公式。但用DP可以更通用。代码实现简化版模型def min_tree_weight(N): 假设每个节点权重为1权值所有节点深度和。 求N个节点构成的二叉树的最小深度和。 这是一个经典的DP问题状态转移为 dp[n] min_{1kn} { dp[k-1] dp[n-k] n } 不对。 正确的对于一棵树总深度和 左子树深度和 右子树深度和 左子树节点数 右子树节点数。 因为左子树所有节点的深度在作为子树时都加了1。 所以 dp[n] min_{0kn-1} { dp[k] dp[n-1-k] n-1 } 其中k是左子树节点数n-1-k是右子树节点数根节点占1个。 n-1 是除了根以外的节点数它们在新树中深度都增加了1。 dp [0] * (N 1) # dp[0] 0 已经初始化 for n in range(1, N 1): dp[n] float(inf) # 左子树节点数从0到n-1 for k in range(n): # k是左子树节点数 left_cnt k right_cnt n - 1 - k # 总节点数n 1(根) left_cnt right_cnt current_weight dp[left_cnt] dp[right_cnt] (n - 1) # n-1是除根外节点数 if current_weight dp[n]: dp[n] current_weight return dp[N] if __name__ __main__: N 10 # 示例 print(f用{N}个节点权重1能构建的二叉树最小深度和为{min_tree_weight(N)})深度解析与常见误区状态转移方程的理解这是本题最难的地方。为什么是加n-1我们定义dp[x]是x个节点构成的子树在其自身根节点深度为0的体系下的总深度和。当这棵子树作为另一棵树的左子树时它的所有节点深度都要1因此它对新的总深度和的贡献就变成了dp[x] x因为每个节点都多贡献了1共x个节点。在状态转移时我们合并左子树、右子树和根节点形成新树新树的总深度和 (dp[left] left) (dp[right] right) 0根节点在新树中深度为0但在最终统计时根深度是0吗这取决于定义。如果题目定义根深度为1那么需要调整。务必根据题目具体定义画图推导出正确的转移方程。时间复杂度上述DP是O(N^2)的如果N达到10^3或更大可能需要优化如四边形不等式优化。但在蓝桥杯国赛中N通常不会太大O(N^2)可以接受。空树处理dp[0]通常表示空树其权值为0。这在转移方程中很重要。3.4 试题D覆盖问题状态压缩DP或搜索这类问题通常描述为用一个给定形状的小图形如1x2的多米诺骨牌、L形瓦片等去覆盖一个M x N的网格问有多少种不同的覆盖方法。网格中可能有一些障碍物。解题思路拆解以多米诺骨牌覆盖2xN网格为例这是最简单的:对于2xN网格用1x2的骨牌覆盖这是一个经典的斐波那契数列问题。但对于更复杂的网格和形状就需要用状态压缩动态规划。状态压缩DP核心思想状态定义dp[i][state]表示处理到第i列时当前列的状态为state的方案数。state是一个二进制数它的每一位表示当前列对应行的格子是否已经被从左边伸过来的骨牌占据或者说当前格子是否已经被覆盖。通常1表示该位置已被占据无需再覆盖0表示该位置是空的需要由当前列或下一列的骨牌来覆盖。状态转移从dp[i-1][prev_state]转移到dp[i][curr_state]。我们需要枚举所有合法的prev_state和curr_state的组合以及在这一列放置骨牌的方式使得prev_state和curr_state共同决定了第i-1列哪些位置需要被竖放骨牌覆盖。在第i列我们可以选择横放骨牌覆盖第i列和第i1列的两个相邻行这会影响curr_state对下一列状态的表示。初始化dp[0][0] 1表示第0列之前没有任何格子被占据。结果最终答案是dp[N][0]表示处理完所有N列后没有骨牌延伸到网格之外状态为0。这是一个非常抽象的过程我们以一个具体例子说明用1x2骨牌覆盖3xN网格。def domino_tiling_3xN(N): 计算用1x2多米诺骨牌覆盖3xN网格的方案数。 状态压缩DP状态表示当前列各行的覆盖情况0空1已被上一列延伸的竖牌覆盖。 # 预处理所有合法的状态转移对 (prev_state, curr_state) # 状态是0到7(2^3-1)的整数二进制位表示三行 transitions [] for prev in range(8): # 前一列状态 for curr in range(8): # 当前列状态 ok True # 检查当前列的空位即prev中为0且curr中也为0的位置能否被横牌或竖牌覆盖 # 更通用的方法是使用DFS来搜索这一列的所有放置方式 # 这里为了简化我们换一种更清晰的实现方式DFS按行放置 # 另一种更清晰的实现轮廓线DP插头DP思想但代码复杂。 # 对于3xN有经典结论当N为奇数时方案数为0偶数时满足递推式 a[n] 4*a[n-2] - a[n-4] # 这里为了展示状态压缩DP思想我们实现一个更简单的2xN的例子。 def domino_tiling_2xN(N): 2xN网格覆盖方案数就是斐波那契数列。用DP模拟 if N 0: return 1 if N 1: return 1 # 只能竖放 dp [0] * (N 1) dp[0] 1 # 空棋盘一种方式 dp[1] 1 # 2x1只能竖放一种 for i in range(2, N 1): # 第i列的情况 # 1. 最后一列是竖放的两个格子那么方案数等于dp[i-1] # 2. 最后两列是被一个横放的骨牌覆盖那么方案数等于dp[i-2] dp[i] dp[i-1] dp[i-2] return dp[N] if __name__ __main__: N 10 print(f覆盖2x{N}网格的方案数为{domino_tiling_2xN(N)})注意事项与高阶技巧复杂度状态压缩DP的状态数是2^M * NM是行数。当M较大如10时状态数爆炸无法使用。这时可能需要更复杂的插头DP或者找数学规律。预处理合法转移对于固定的M所有合法的(prev_state, curr_state)对是可以预先计算出来的这样在DP循环中只需遍历这些合法对而不是所有组合能提升效率。滚动数组优化由于dp[i]只依赖于dp[i-1]可以用两个一维数组交替使用节省空间。调试技巧对于这类复杂DP先用小规模数据如N1,2,3手动计算答案然后与程序输出对比确保状态定义和转移正确。4. 通用解题技巧与考场策略做完一套真题除了弄懂每一道题更重要的是提炼出通用的方法和考场上的应对策略。以下是我总结的几点1. 输入输出一定要熟练。蓝桥杯是OI赛制需要从标准输入读取数据向标准输出写入结果。务必提前准备好输入输出模板并熟练使用。对于Python常用import sys # 读取一行转换为整数列表 data list(map(int, sys.stdin.readline().split())) # 读取多行直到文件结束 for line in sys.stdin: n int(line.strip()) # ... 处理注意大量输入时使用sys.stdin.read()一次性读取再处理可能更快但要注意内存。2. 时间复杂度估算与算法选择。拿到题先看数据规模。根据经验n 10: 可能是暴力搜索、全排列。n 20: 状态压缩DP/DFS。n 1000: O(n^2)的动态规划、朴素Dijkstra等。n 10^5: 需要O(n log n)的算法如排序、优先队列、线段树、二分答案。n 10^6: 通常需要O(n)的算法如双指针、单调栈、前缀和。3. 空间复杂度注意。Python的列表、字典比较耗内存。如果开一个10^6大小的整数列表内存大约8MB因为Python int对象开销大可以接受。但如果开10^6 * 10^6的二维列表肯定爆内存。遇到需要大数组的题考虑使用array模块或numpy如果允许或者优化数据结构。4. 调试与对拍。编写一个简单的暴力解法通常用于小数据与你的优化解法用随机数据对比结果。这是确保算法正确性的有效手段尤其是在考试中时间紧张容易考虑不周。5. 不会做的题怎么办暴力骗分如果数据有部分小规模的分支写一个暴力程序确保拿到这些分。找规律对于数学题或图形题可以手动模拟小数据看看结果是否有规律比如是斐波那契数列、卡特兰数等。输出特例如果题目有多个询问有些询问的答案可能很简单比如边界情况直接输出这些答案也能得分。5. 备考资源与进阶学习建议如果你想在蓝桥杯或类似的算法竞赛中取得好成绩仅靠真题是不够的需要系统学习和练习。1. 系统学习算法知识体系基础数据结构数组、链表、栈、队列、哈希表、堆优先队列。基础算法排序、二分查找、双指针、前缀和与差分。搜索深度优先搜索DFS、广度优先搜索BFS、回溯、剪枝。动态规划DP线性DP、区间DP、状态压缩DP、树形DP。这是重点也是难点需要大量练习。图论最短路Dijkstra, Floyd、最小生成树Prim, Kruskal、拓扑排序。数学质数筛法、最大公约数/最小公倍数、快速幂、简单组合数学。2. 刷题平台推荐蓝桥杯官方练习系统有历年真题是最直接的备考资料。AcWing有很多蓝桥杯辅导课和真题讲解社区活跃。洛谷题目分类清晰适合按知识点刷题。LeetCode虽然偏重面试但其“题库”中的算法题目质量很高可以用来巩固基础算法。3. 关于Python在竞赛中的使用优势语法简洁开发速度快内置库强大collections,itertools,heapq,bisect等对于某些高精度计算或字符串处理比C方便。劣势运行速度慢递归深度有限默认约1000层内存开销大。因此用Python解题更考验算法的优化程度必须选择时间复杂度更优的算法。必会模块collections:deque双向队列用于BFS、Counter计数、defaultdict带默认值的字典。itertools:permutations排列、combinations组合、product笛卡尔积用于暴力枚举。heapq: 堆优先队列用于Dijkstra算法等。bisect: 二分查找。math: 数学函数gcd最大公约数、sqrt等。functools:lru_cache用于实现记忆化搜索简化DP代码。最后编程竞赛的备赛是一个长期积累的过程没有捷径。从看懂每一道真题的解析开始到自己独立复现代码再到举一反三解决类似问题每一步都算数。我当年备赛时一个类型的题目比如DP会集中刷上十几道甚至几十道直到形成条件反射看到题目描述就能大概猜到状态该怎么定义。希望这份针对2021年国赛真题的解析能成为你算法学习之路上一块有用的垫脚石。如果在练习中遇到任何问题或者对某道题有更巧妙的解法欢迎随时交流。