蓝桥杯国赛Python算法实战：因数分解、最短路与状态压缩DP精讲

1. 项目概述从一道国赛真题看Python算法实战最近在整理资料时翻到了第十一届蓝桥杯Python大学组国赛的几道真题。作为国内颇具影响力的程序设计竞赛蓝桥杯的国赛题目往往能很好地检验选手对算法、数据结构以及Python语言特性的综合运用能力。这些题目不像一些纯理论问题那样枯燥它们通常包裹在一个有趣的情境下但内核却非常扎实涉及动态规划、搜索、贪心、数学等核心算法思想。今天我就挑其中几道有代表性的题目和大家一起拆解一下解题思路并分享一些在竞赛和实际编码中都非常实用的Python技巧。无论你是正在备赛的学生还是希望提升算法能力的开发者相信这种“真题实战分析”的方式会比单纯看算法书更有收获。我们会从题目理解、思路推导、代码实现到优化细节一步步展开过程中我会穿插很多我踩过的“坑”和总结的“偷懒”技巧。2. 真题一货物摆放——因数分解与组合计数的艺术2.1 题目还原与核心诉求这道题的大意是给定一个体积为 ( n ) 的立方体仓库我们需要将一批体积为 ( 1 \times 1 \times 1 ) 的小立方体货物放进去。货物的长、宽、高必须都是整数并且三者相乘等于 ( n )。问有多少种不同的摆放方案考虑长、宽、高的顺序即(L, W, H)作为一个三元组。举个例子如果 ( n 4 )那么可能的方案有(1, 1, 4)(1, 4, 1)(4, 1, 1)(1, 2, 2)(2, 1, 2)(2, 2, 1)一共6种。核心诉求输入一个整数 ( n ) 题目中 ( n ) 通常很大比如 ( n 2021041820210418 )输出满足条件的三元组个数。2.2 暴力枚举的陷阱与优化思路很多同学的第一反应是三重循环暴力枚举。def brute_force(n): count 0 for i in range(1, n1): for j in range(1, n1): for k in range(1, n1): if i * j * k n: count 1 return count当 ( n ) 很小的时候这没问题。但国赛的 ( n ) 动辄 ( 10^{12} ) 以上三重循环到 ( n ) 的复杂度是 ( O(n^3) )完全不可行。我们必须优化。优化思路一减少枚举范围既然i * j * k n那么i、j、k都必须是 ( n ) 的因数。我们只需要枚举 ( n ) 的所有因数即可。求一个数所有因数的复杂度是 ( O(\sqrt{n}) )。优化思路二排列组合代替三重循环我们先找出 ( n ) 的所有因数存放在列表factors中。那么问题转化为从这个因数列表中可重复地选取3个数因为一个因数可以被多次使用比如1使得它们的乘积为 ( n )。我们可以用三重循环遍历factors但此时循环次数是len(factors)的三次方。由于因数个数远小于 ( n )这已经快了很多但对于因数很多的 ( n )比如有很多小质因子的合数可能还是有点慢。进一步优化在第二重和第三重循环时我们可以增加条件判断来提前终止。如果i * j n或者n % (i * j) ! 0那么当前的(i, j)组合就不可能找到合法的k可以跳过。2.3 高效实现与代码详解下面是一个比较高效的实现方案def count_arrangements(n): # 1. 找出n的所有因数 factors [] i 1 while i * i n: # 只需遍历到 sqrt(n) if n % i 0: factors.append(i) if i ! n // i: # 避免重复添加平方根 factors.append(n // i) i 1 factors.sort() # 排序不是必须但便于理解和调试 count 0 length len(factors) # 2. 三重循环遍历因数列表 for a in range(length): for b in range(a, length): # 从a开始利用对称性稍作优化但注意题目要求有序所以不能完全去重 if factors[a] * factors[b] n: # 乘积已经超过n后续的b更大直接跳出内层循环 break if n % (factors[a] * factors[b]) ! 0: continue for c in range(b, length): # 从b开始 product factors[a] * factors[b] * factors[c] if product n: # 超过n跳出循环 break if product n: # 关键计算当前三个因数可能相等的排列数 # 如果三个数互不相等排列数有 3! 6 种 # 如果有两个相等排列数有 3 种 (AAB, ABA, BAA) # 如果三个都相等排列数只有 1 种 if factors[a] factors[b] factors[c]: count 1 elif factors[a] factors[b] or factors[a] factors[c] or factors[b] factors[c]: count 3 else: count 6 return count # 测试 n 2021041820210418 # 这是一个著名的日期数字 print(count_arrangements(n))代码要点与避坑指南因数查找while i * i n是标准写法比i int(n**0.5)更快且避免了浮点数误差。循环优化内层循环的break条件factors[a] * factors[b] n非常重要它能剪掉大量无效计算。这是将复杂度从 ( O(m^3) ) 降低到近似 ( O(m^2) ) 的关键其中 ( m ) 是因数个数。排列计数这是最容易出错的地方。题目要求考虑顺序所以(1,1,4)和(1,4,1)算两种。我们不能简单地对(a,b,c)进行组合去重。我的做法是先找到一组满足a*b*cn的因数组合这里abc因为我们循环时下标是递增的然后根据这三个数的相等情况计算排列数。这是一种“先组合后排列”的思路比直接枚举所有排列并去重更高效。大数处理Python 原生支持大整数所以不用担心溢出问题。这是用 Python 打算法竞赛的一大优势。实测心得对于 ( n 2021041820210418 )这个算法的运行时间在普通电脑上也能控制在几秒内。如果追求极致还可以用math.isqrt来获取整数平方根或者用列表推导式更优雅地生成因数但当前版本的清晰度和效率已经足够应对竞赛。3. 真题二路径——最短路算法与数论结合3.1 问题场景与抽象建模题目描述了一个有趣的场景有2021个结点标号从1到2021。对于两个不同的结点 ( a, b )如果它们的差的绝对值 ( |a-b| ) 小于等于21那么就在它们之间连一条无向边边的权重长度为 ( a ) 和 ( b ) 的最小公倍数lcm(a, b)。问题求从结点1到结点2021的最短路径长度。抽象建模这本质上是一个稠密图上的单源最短路问题。图的顶点数是2021。对于任意顶点i它需要向从i1到min(i21, 2021)的所有顶点j连边边权为lcm(i, j)。同时由于是无向边j也会向i连边但我们在建图时通常按有向处理或者只存一条。3.2 算法选型为什么是Dijkstra最短路算法有很多Floyd、Bellman-Ford、SPFA、Dijkstra。我们逐一分析Floyd求所有点对最短路复杂度 ( O(n^3) )( n2021 ) 时不可接受。Bellman-Ford/SPFA适用于有负权边的图本题边权均为正且SPFA在最坏情况下复杂度不稳定。Dijkstra适用于边权非负的图的单源最短路使用优先队列优化的版本复杂度为 ( O((VE)\log V) )。本题 ( V2021 )每个点最多连21条边总边数 ( E \approx 21*2021 )是一个稀疏图完全在Dijkstra的高效处理范围内。因此堆优化Dijkstra算法是最佳选择。3.3 Python实现与细节剖析import math import heapq def lcm(a, b): 计算最小公倍数 return a // math.gcd(a, b) * b # 先除后乘防止中间结果溢出虽然Python不担心但习惯好 def shortest_path(n2021, limit21): 计算从1到n的最短路径长度 n: 结点总数 limit: 连接条件绝对值差小于等于limit # 1. 建图 - 邻接表 graph [[] for _ in range(n 1)] # 下标从1开始多开一个位置 for i in range(1, n 1): for j in range(i 1, min(i limit, n) 1): # j从i1开始避免重复和自环 weight lcm(i, j) graph[i].append((j, weight)) graph[j].append((i, weight)) # 无向图双向加边 # 2. Dijkstra算法 INF float(inf) dist [INF] * (n 1) # 距离数组 dist[1] 0 # 起点距离为0 pq [] # 优先队列 (当前距离, 顶点) heapq.heappush(pq, (0, 1)) while pq: current_dist, u heapq.heappop(pq) # 如果当前取出的距离大于记录的距离说明是旧的不优解直接跳过 if current_dist dist[u]: continue # 松弛操作遍历u的所有邻居 for v, w in graph[u]: new_dist current_dist w if new_dist dist[v]: dist[v] new_dist heapq.heappush(pq, (new_dist, v)) return dist[n] # 计算并输出结果 result shortest_path() print(f从1到2021的最短路径长度为{result})关键细节与优化技巧邻接表建图使用列表的列表 (graph) 存储图graph[i]是一个列表里面存着(邻居顶点, 边权)的元组。这比邻接矩阵省太多空间尤其对于稀疏图。lcm的计算a // math.gcd(a, b) * b是标准写法。math.gcd是Python内置的求最大公约数函数效率很高。Dijkstra的“惰性删除”注意if current_dist dist[u]: continue这行代码。因为优先队列不支持直接修改元素的优先级当我们更新某个顶点v的距离时我们会将(new_dist, v)压入队列而不是更新队列里旧的那个(old_dist, v)。这样队列里就可能存在同一个顶点的多个不同距离的条目。当弹出时如果弹出的距离大于当前记录的最短距离说明这个条目已经过时了直接忽略。这是堆优化Dijkstra的标准写法必须掌握。复杂度建图双重循环复杂度 ( O(n \cdot limit) )。Dijkstra部分每个边都会被访问一次以进行松弛每次堆操作是 ( O(\log E) )总复杂度 ( O(E \log V) )对于本题规模瞬间完成。一个易错点题目中边的权重是lcm(a, b)而不是gcd(a, b)或a*b。一定要仔细读题。我在第一次做的时候差点看错。4. 真题三回路计数——状态压缩动态规划4.1 问题本质哈密顿回路计数这道题是国赛的压轴题之一难度较大。题目简述有21个编号从0到20的建筑物从一个建筑物到另一个建筑物有走廊连接条件是两建筑物编号互质。从1号建筑物出发访问每个建筑物恰好一次最后回到1号建筑物有多少种不同的访问顺序即哈密顿回路数问题本质求一个无向图中以某个特定顶点为起点和终点的哈密顿回路的数量。这是一个经典的NP-Hard问题但对于顶点数较少n 21的情况可以用状态压缩动态规划来解决。4.2 状态压缩DP的精髓状态压缩DP的核心思想是用一个整数的二进制位来表示一个集合。例如一个21位的二进制数mask如果第i位是1表示建筑物i已经被访问过如果是0则表示未访问。我们定义dp[mask][v]表示当前已经访问过的建筑物集合为mask并且最后访问的建筑物是v时形成的路径有多少种。注意这里dp记录的是从起点到当前状态的部分路径数还不是完整的回路。状态转移方程dp[mask | (1 u)][u] dp[mask][v]这个方程的意思是如果当前状态是(mask, v)并且存在一条从v到u的边即v和u互质并且u还没有被访问过即mask的第u位为0那么我们就可以从v走到u形成一个新的状态(mask | (1u), u)到达这个新状态的路径数要加上从原状态来的路径数。初始化dp[1 1][1] 1。因为从1号建筑出发初始状态是只访问了1号建筑mask 11且最后位置在1这样的路径只有1条就是待在起点。最终答案我们需要的是哈密顿回路即访问完所有建筑mask的所有位都是1并且最后一步能从最后一个建筑走回起点1。所以最终答案不是简单的dp[full_mask][x]求和。我们需要枚举回路中倒数第二个建筑v检查v是否与起点1互质然后将dp[full_mask][v]累加起来。因为最后一步是从v走回1。4.3 Python实现与性能优化import math def count_hamiltonian_circuits(n21): 计算从建筑1出发回到建筑1的哈密顿回路数量。 建筑编号为0到n-1起点是1。 # 1. 预处理邻接矩阵判断是否互质 graph [[False] * n for _ in range(n)] for i in range(n): for j in range(i 1, n): if math.gcd(i, j) 1: graph[i][j] graph[j][i] True full_mask (1 n) - 1 # 所有位都为1表示所有建筑都访问过 # 2. 初始化DP数组。dp[mask][v] # 这里使用列表嵌套列表对于n21mask有2^21≈2百万种内存是瓶颈。 # 更优的方法是使用字典数组或者用一维数组状态编码。 # 这里采用一个更节省内存的写法dp[mask]是一个列表存储最后建筑为v时的路径数。 dp [ [0] * n for _ in range(1 n) ] # 注意这种写法在n21时内存消耗巨大约2M*21*8字节≈350MB可能超出限制。 # 让我们换一种写法使用字典数组 from collections import defaultdict dp [defaultdict(int) for _ in range(1 n)] start 1 dp[1 start][start] 1 # 初始化 # 3. 状态转移 for mask in range(1 n): # 可以优化只遍历包含起点的mask因为从起点出发 if not (mask (1 start)): continue # 遍历当前mask下所有可能的上一个建筑v for v in list(dp[mask].keys()): # 遍历字典的键即所有可能的最后建筑 current_count dp[mask][v] if current_count 0: continue # 尝试从v走到下一个未访问的建筑u for u in range(n): if not graph[v][u]: # 没有边 continue if mask (1 u): # u已经访问过 continue next_mask mask | (1 u) dp[next_mask][u] current_count # 4. 统计结果遍历所有访问完所有建筑的状态且最后建筑v与起点1相连 ans 0 final_mask full_mask for v in dp[final_mask]: if graph[v][start]: # 能从v走回起点 ans dp[final_mask][v] return ans # 注意上述代码的dp数组字典列表在n21时仍然会消耗大量内存和时间。 # 实际上对于竞赛环境n21时状态数2^212097152每个状态用一个字典存储内存和速度压力都很大。 # 更常见的优化是使用位运算和列表并注意遍历顺序。 print(计算中...该方法对n21可能较慢或内存不足) # result count_hamiltonian_circuits(21) # 谨慎运行 # print(f回路数量{result})内存与性能优化实战 上面的代码清晰地阐述了思路但在n21时直接运行很可能内存溢出或超时。在实际竞赛中我们需要进一步优化使用整数数组代替字典dp可以是一个二维列表dp[mask][v]但很多mask状态是无效的比如不包含起点。我们可以用dp作为一个一维字典键是(mask, v)的元组但这样查找慢。更好的办法是预处理出每个mask下可能存在的v即mask中为1的位但这需要额外开销。按mask中1的个数遍历哈密顿路径的长度是递增的。我们可以先遍历所有只访问了1个建筑的状态只有起点然后2个3个...直到n个。这样我们可以用滚动数组的思想只保留当前长度的所有状态可以大幅节省内存。但实现起来复杂。使用Python的数组模块或NumPy如果环境允许使用numpy的int64数组可以显著提升性能并减少内存开销因为底层是C数组。对称性剪枝由于建筑编号除了起点1其他是对称的。我们可以利用这一点减少状态但实现复杂容易出错。一个更可行的优化版本使用列表和位运算import math from collections import deque def count_hamiltonian_circuits_opt(n21): graph [[False]*n for _ in range(n)] for i in range(n): for j in range(i1, n): if math.gcd(i, j) 1: graph[i][j] graph[j][i] True start 1 full_mask (1 n) - 1 # dp[mask][v] 使用列表的列表但只初始化可能用到的行。 # 实际上我们可以用一维数组但需要将(mask, v)编码成一个整数。 # 这里采用一个折中dp是一个列表索引是mask值是一个长度为n的列表用0初始化。 dp [ [0]*n for _ in range(1n) ] dp[1start][start] 1 # 预处理每个mask对应的顶点列表避免内层循环遍历所有n # 但更常见的竞赛写法是直接遍历mask然后遍历所有顶点v判断v是否在mask中。 # 这里采用标准遍历但利用位运算快速判断。 for mask in range(1n): # 如果mask不包含起点跳过因为所有有效路径都必须从起点开始 if not (mask (1start)): continue # 遍历当前mask中所有已访问的顶点v作为上一步的终点 v mask while v: # 获取最低位的1所在的位即一个顶点编号 # 这里需要将位索引转换为顶点编号我们换一种方式 pass # 这种位运算遍历顶点的方式代码较复杂 # 更清晰且效率可接受对于n21的写法是双层循环 for mask in range(1n): if not (mask (1start)): continue for v in range(n): if not (mask (1v)): # v不在mask中 continue cur dp[mask][v] if cur 0: continue # 尝试从v走到u for u in range(n): if not graph[v][u]: continue if mask (1u): # u已访问 continue next_mask mask | (1u) dp[next_mask][u] cur ans 0 final_mask full_mask for v in range(n): if graph[v][start]: ans dp[final_mask][v] return ans这个版本使用了二维列表对于n21dp数组大小约为2^21 * 21 ≈ 44 million个整数。在Python中一个整数对象约28字节这需要超过1GB内存显然不行。因此这道题在Python中必须使用更节省内存的数据结构或者换用C/Java等语言。这也是蓝桥杯国赛的一个特点有时会考察你对问题规模和时间/空间复杂度的敏感度引导你选择更合适的语言或算法。对于Python的可行方案使用array模块的L类型无符号长整型或者Q类型可以大幅减少内存占用因为它们是紧凑的C数组。或者使用numpy。import math import numpy as np def count_hamiltonian_circuits_np(n21): graph [[False]*n for _ in range(n)] for i in range(n): for j in range(i1, n): if math.gcd(i, j) 1: graph[i][j] graph[j][i] True start 1 full_mask (1 n) - 1 # 使用numpy的int64数组内存占用远小于Python列表 dp np.zeros((1n, n), dtypenp.int64) dp[1start, start] 1 for mask in range(1n): if not (mask (1start)): continue # 利用numpy的向量化操作这里不行因为转移是稀疏且依赖graph的。 # 所以还是需要循环但dp的访问是高效的。 # 我们找出mask中所有为1的位即已访问的顶点 # 这里用循环遍历v for v in range(n): if not (mask (1v)): continue cur dp[mask, v] if cur 0: continue # 预计算v的所有邻居中未访问的 for u in range(n): if graph[v][u] and not (mask (1u)): next_mask mask | (1u) dp[next_mask, u] cur ans 0 for v in range(n): if graph[v][start]: ans dp[full_mask, v] return ans # 使用numpy后内存占用约为 2^21 * 21 * 8字节 ≈ 350MB仍然很大但比Python列表的1GB好。 # 在拥有足够内存的机器上可以运行。 print(使用numpy优化计算...) # ans count_hamiltonian_circuits_np(21) # print(ans)最终建议对于此类状态压缩DP且n达到21的题目在竞赛中若使用Python需要格外关注内存限制。如果内存限制严格如256MB上述方法都可能超限。这时可能需要寻找更巧妙的数学性质或利用对称性进行剪枝或者干脆用C实现。这道题本身也考察了选手的算法实现能力和对工具链的掌握。5. 竞赛编程中的通用技巧与避坑指南结合这几道真题的解析我想分享一些在蓝桥杯乃至其他算法竞赛中用Python解题的通用经验。5.1 输入输出与性能瓶颈蓝桥杯的评测系统通常使用标准输入输出。处理大量数据时input()可能成为瓶颈。优化技巧import sys # 一次性读取所有行比多次调用input()快 data sys.stdin.read().strip().split() # 或者使用 sys.stdin.readline() n int(sys.stdin.readline())对于输出如果需要打印大量内容可以考虑使用\n.join(list_of_strings)一次性构造输出但通常直接多次print问题不大。5.2 数据结构的选择列表 vs 集合/字典频繁的in操作使用集合 (set) 或字典 (dict) 的键其时间复杂度接近 O(1)而列表是 O(n)。双端队列需要从两端高效添加/删除元素时使用collections.deque。堆需要快速获取最小/最大值时使用heapq模块。记忆化搜索对于递归函数使用functools.lru_cache装饰器可以自动实现记忆化极大提升效率尤其适合动态规划的自顶向下写法。5.3 数学与数论工具Python的math模块非常强大math.gcd(a, b): 最大公约数。math.lcm(a, b): Python 3.9 支持最小公倍数。math.isqrt(n): 求整数平方根比int(n**0.5)更精确快速。math.comb(n, k),math.perm(n, k): 组合数和排列数。math.prod(iterable): 计算可迭代对象中所有元素的积。5.4 调试与测试小数据验证先用手算或暴力算法对小的测试用例验证正确性。边界条件特别注意输入为0、1、负数如果允许、最大值等情况。使用pdb或打印调试在关键变量处插入print语句或者使用import pdb; pdb.set_trace()进行交互式调试。对拍写一个暴力但正确的算法通常复杂度高只适用于小数据和你的优化算法对同一组随机生成的小数据进行比较确保结果一致。5.5 时间与空间估算在动手前先估算最坏情况下的时间和空间复杂度。时间Python大约1秒能执行 (10^7 \sim 10^8) 次简单操作。如果算法复杂度是 (O(n^2)) 且 (n10^4)那么操作数在 (10^8) 量级可能处于临界点。空间一个int对象约28字节一个list有额外开销。估算你的数据结构占用的内存。如果开一个 (10^6) 大小的list内存占用可能在几十MB到上百MB。蓝桥杯的内存限制通常是256MB或512MB。就像在“回路计数”中我们如果不假思索地开一个dp[121][21]的Python列表内存立刻爆炸。这种估算意识必须养成。5.6 关于Python的“慢”Python确实比C/Java慢但蓝桥杯的许多题目对Python是友好的只要算法复杂度正确。关键在于避免在循环内层进行低效操作。比如能用局部变量就用局部变量避免在循环中反复进行属性查找如list.append或函数调用可以先将函数赋值给一个局部变量。对于计算密集的部分可以考虑使用PyPy解释器如果比赛支持它通常比CPython快很多尤其是在有大量循环和整数运算的场景下。这几道国赛真题从因数分解到最短路再到状态压缩DP覆盖了基础数论、图论和动态规划等多个核心算法领域。解题过程不仅是对算法知识的检验更是对问题抽象、优化建模和代码实现能力的综合锻炼。我个人的体会是刷真题时不要满足于“AC”要多问几个“为什么”为什么这道题用这个算法为什么这个优化有效还有没有其他解法时间复杂度的瓶颈在哪里只有这样每做一道题才能真正收获一份经验在赛场上遇到新题时才能更快地找到那条正确的解题路径。