🎁2020第十一届蓝桥杯python组国赛真题

🚀 真题练习，冲刺国赛 🚀

2020年第十一届蓝桥python组国赛真题+解析+代码

博观而约取，厚积而薄发

---

🏆国赛真题目录

---

试题A.美丽的2⭐️

🍰1.题目

美丽的2

👑2.思路分析

难度：⭐️

标签：枚举&字符串

🎇思路：暴力法

🔱思路分析：

本题为填空题，只需要遍历$1\to 2020$即可：

1. 将数字转为字符串$(str)$
2. 如果 ${}^{\prime }{2}^{\prime }$ 在字符串$s$中，则结果$+1$

💯3.代码实现

cnt=0
for i in range(1,2021):s=str(i)if '2' in s:cnt+=1
print(cnt) # 563

输出结果：

试题B.合数个数⭐️

🍰1.题目

合数个数

👑2.思路分析

难度：⭐️

标签：枚举

🎇思路①：试除法

🔱思路分析：

本题为填空题，因此可以直接使用暴力法得出结果

1. 由于$1$和$2$均为素数，所以只需遍历$3\to 2020$
2. 当遍历到一个数时，我们对其进行判断：
   ①用$2\to \sqrt{x}$进行试除
   ②如果整除，则说明有除了$1$和本身外的其他因子存在，为合数；否则，为素数
3. 返回值为$1$，则为合数，$cnt+1$

🎇思路②：素数筛

🔱思路分析：

对于任意一个素数，它的正整数倍$(\ge 2)$一定是合数

1. 构造$vis$数组，先初始化$vis$为$True$（$True$为素数，$False$为合数）
2. 遍历$2\to 2020$，若当前的数$x$为$True$（未被标记），则为素数，对他进行处理：
   ①遍历$x$的倍数 $i=2x,3x,...$
   ②如果$i$未被标记过（防止合数重复标记，如2的3倍为6，3的2倍也为6，则统计的合数个数会增多），则标记vis[i]=False，并让$cnt+1$

图解：

💯3.代码实现

1.试除法实现

from math import sqrtdef not_prime(x):for i in range(2,int(sqrt(x))+1):if x%i==0:return 1 # 为合数return 0 # 为素数cnt=0
for x in range(3,2021):if not_prime(x):cnt+=1
print(cnt) # 合数个数：1713

2.素数筛实现

vis=[True]*2021 # 默认都是素数
cnt=0
for x in range(2,2021):if vis[x]: # 如果是素数(没有被标记过)for i in range(x+x,2021,x): # 将[x,2020]中素数x的倍数全部标记为合数if vis[i]==True:cnt+=1vis[i]=False
print(cnt) # 1713

输出结果：

试题C.阶乘约数⭐️⭐️⭐️

🍰1.题目

阶乘约数

👑2.思路分析

难度：⭐️⭐️⭐️

标签：数论——唯一分解定理

🎇思路①：暴力法

🔱思路分析：

要得到所有的因子，不难想到用暴力法统计，但是！！不出意外地超时了

step：

1. 遍历$i=1\to \sqrt{100!}$，不断试除
2. 如果能被整除，我们对该数进行讨论：
   ①如果$i=\sqrt{100!}$，则这里因子只增加了一个，cnt+=1
   ②如果$i$为其他数，则这里因子必然有两个，cnt+=2

不通过代码： ❌

from math import sqrt
num=1
for i in range(2,101):num*=icnt=0
for j in range(1,int(sqrt(num))+1):if num%j==0:if j==int(sqrt(num)):cnt+=1else:cnt+=2
print(cnt)

🎇思路②：唯一分解定理

🔱思路分析：

我们先来介绍一个与此题相关的数学定理：

🚀 整数的唯一分解定理：

即正整数n（＞1）可分解为：$n=p_1^{\alpha 1}\ast p_2^{\alpha 2}\ast ...\ast p_k^{\alpha k}$

其中，$p1<p2<\dots <pk$皆素数，$\alpha i(i=1，2，\dots ，k)$皆为正整数，而正整数n的正因数个数为：$num=(\alpha 1+1)\ast (\alpha 2+1)\ast ...\ast (\alpha k+1)$，也就是将素数的次方加1后求乘积

为什么？

因为对于$p_1$来说，它的指数为$\alpha 1$，则分解时它可以有$\alpha 1+1$种取法；同理，$\alpha 2$有$\alpha 2+1$种取法；…；所以，总的因数个数为$(\alpha 1+1)\ast (\alpha 2+1)\ast ...\ast (\alpha k+1)$

什么意思呢？

举个例子：

我们要求100的正因数个数：

1. 将100分解为：$100=2^2\ast 5^2$
2. 则$p_1=2，\alpha 1=2，p_2=5，\alpha 2=2$，所以正因数的个数为：$(2+1)\ast (2+1)=9$
3. 这$9$个数即为：$1,2,4,5,10,20,25,50,100$

有了上面的定理支撑，我们就可以用代码实现了：

step：

1. 由于$n!=1\ast 2\ast ...\ast n$，所以，我们先找到$[1,n]$中的质数，记录在数组$s$中
2. 质因数分解：将每一个数都分解为质数的乘积，用字典记录$s$中每一个素数的得到次数，最终即为指$\alpha i$
3. 最后用公式：$(\alpha 1+1)\ast (\alpha 2+1)\ast ...\ast (\alpha k+1)$即可

💯3.代码实现

唯一分解定理实现：

from math import *def is_prime(x):for i in range(2,int(sqrt(x))+1):if x%i==0:return 0 # 为合数return 1 # 为素数s=[2] # 记录[1,100]的素数
for i in range(3,101):if is_prime(i):s.append(i)p=dict()
for i in s:p[i]=0 # 将质数的次数初始化为0# 质因数分解
for i in range(1,101):for a in s:while i%a==0:i=i/ap[a]+=1# 求正因数个数
res=1
for d in p.values():res*=(d+1)
print(res)

输出结果：

试题D.本质上升序列⭐️⭐️⭐️

🍰1.题目

本质上升序列

👑2.思路分析

难度：⭐️⭐️⭐️

标签：dp动态规划

🎇思路：线性dp

🔱思路分析：

要求升序字符串，即字符串中从左到右满足线性关系（后一个大于前一个），因此，我们可以用动态规划从前到后不断统计个数

step：

1. 字符串为$s$，$s[k]$即代表字符串中第$k+1$个字符
2. 动态规划数组$dp[i]$：$dp[i]$表示以字符$s[i]$结尾的满足本质上升序列的字符串的个数，其中$i\in [1,n-1]$，初始化$dp[]=1$
3. 遍历$i$从$1$到$n-1$，对于每一个$i$，我们遍历i之前的所有字符$s[j]$：
   ①如果当前$s[i]>s[j]$：则表明，以$s[j]$结尾的满足本质上升序列的字符串，在结尾加上$s[i]$后，也满足升序条件，且为一种新的字符串情况，因此：dp[i]+=dp[j]
   ②如果当前$s[i]=s[j]$：则表明，对于$s[j]$之前的字符，以$s[j]$结尾和$s[i]$结尾的本质是一样的，只是换了尾字符的位置，所以，要减去这些重复的情况：dp[i]-=dp[j]
   ③如果当前$s[i]<s[j]$：则表明，不能直接向以$s[j]$结尾的字符串后添加$s[i]$，因为不满足升序条件了，所以跳过，继续判断下一个$s[j]$：continue
4. 最后，统计$dp$数组$[0,n-1]$的和，即为所有情况

为什么要初始化$dp$为$1$？

1. $dp[0]$需要：因为以s[0]（第一个字符）结尾的情况必定有$1$种，且后续$dp[1\to n]$的值都是由$dp[0]\to dp[i-1]$递推而来的，所以初始化$dp[0]=1$
2. 默认以$s[i]$结尾的满足条件的字符串都是一种情况（也就是单个字符的情况）：我们在遍历时，只遍历了$s[i]$之前的$s[0\to (i-1)]$的情况，而没有考虑单个$s[i]$自身，所以，要初始化为1，如果字符串$s$中有单个重复的情况，也会在$s[i]=s[j]$时被减去

以字符串${}^{\prime }lanqia{o}^{\prime }$为例：

特别注意，当$s[5]=s[1]{=}^{\prime }{a}^{\prime }$时，应该执行dp[5]-dp[1]，这里可以直观地看到，就是减去’a’这一情况，避免了重复字符串的出现

以此类推，最终相加即可得到总数为：$1+1+3+6+2+0+8=21$

💯3.代码实现

线性dp实现：

s='tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl'
n=len(s)
dp=[1]*n # dp[i]表示以s[i]结尾的字符串中本质上升序列的数目(单个字符都满足)
for i in range(1,n):for j in range(i): # [0,i-1]if s[i]>s[j]: # 如果s[i]>s[j]，则可以看做以s[j]结尾的字符串之后再添加一个s[i]便可以得到新的一种本质上升序列dp[i]+=dp[j]elif s[i]==s[j]: # 如果s[i]=s[j]，则表示dp[j]的情况和dp[i]部分重复了，所以要减去这些情况dp[i]-=dp[j]else:continue # 如果s[i]<s[j]，继续下一轮
print(sum(dp)) # 3616159

输出结果：

试题E.玩具蛇⭐️⭐️⭐️

🍰1.题目

玩具蛇

👑2.思路分析

难度：⭐️⭐️⭐️

标签：dfs深度优先遍历

🎇思路：dfs深搜

🔱思路分析：

题目要求找到所有摆放蛇各个身段的情况，由于蛇身是连续的，也就是相邻的身段只能朝上下左右摆放，不能是对角线，所以，我们可以对蛇头（序号为$1$）在每一个方格处都进行$dfs$深搜操作，最终得到所有满足条件的情况

注意：对于相同形状，但存在在相同方格中，蛇的位置不同时，为不同的方案

图示：

step：

1. 将$4x4$方格中每一个格子都作为一次蛇头的位置（序号为1）进行$dfs$
2. $dfs(x,y,step)$：从蛇头出发，表示当前蛇尾所在位置为$(x,y)$，且蛇的身长为$step$：
   ①结束条件：如果蛇的身长达到16 step=16，则表示该方案可行，cnt+=1
   ②深搜四个方向：如果蛇尾向该方向扩展后，仍在4x4方格内，且该方格未被标记过时：$标记+深搜+回溯$
3. 最后$cnt$的值即为情况总数

注意：在 $4x4$方格中，每一轮以新的方格作为蛇头时，要重新构造 $vis[4][4]$数组，因为要清空之前 $dfs$留下的标记

💯3.代码实现

dfs实现：

def judge(x,y):if x>=0 and x<=3 and y>=0 and y<=3 and vis[x][y]==False: # 如果该点还未被访问过return Truereturn Falsedef dfs(x,y,step):global cnt,vis# 结束条件if step==16:cnt+=1returnfor d in [(1,0),(-1,0),(0,1),(0,-1)]: # 对四个方向进行深搜nx,ny=x+d[0],y+d[1]if judge(nx,ny):# 标记vis[nx][ny]=True# dfsdfs(nx,ny,step+1)# 回溯vis[nx][ny]=Falsecnt = 0
for i in range(4):for j in range(4):vis = [[False] * 4 for _ in range(4)]  # 存4x4方格图（注意：每次到一个新的点，必须要清空vis数组，重新dfs）vis[i][j] = True # 对当前点（蛇头）进行标记dfs(i,j,1)  # 对点(i,j)进行深搜，1表示：经过了(i,j)位置，为第一步
print(cnt)

输出结果：

试题F.天干地支⭐️

🍰1.题目

天干地支

👑2.思路分析

难度：⭐️

标签：列表

🎇思路：模拟

🔱思路分析：

本题要求任意年份的天干地支$([1,9999])$，由于天干的周期为$10$，地支的周期为$12$，因此，我们可以根据周期的差异分别计算天干和地支

step：

1. 构造天干和地支的列表
   这里有一个小技巧 $tips$：我们可以先算出公元$0$年的天干地支$\to$为庚申年
   于是，我们可以将天干地支列表的首元素变为${}^{\prime }gen{g}^{\prime }$和${}^{\prime }she{n}^{\prime }$，之后则按照正常顺序放置，这样，我们就可以实现 年份除以相应周期的余数$=$对应列表的下标
2. 年份分别对$10$和$12$取余：t=year%10;d=year%12
   再将对应列表下标中的元素取出，拼在一起即为结果

💯3.代码实现

列表操作实现：

Tiangan=['geng','xin','ren','gui','jia','yi','bing','ding','wu','ji']
Dizhi=['shen','you','xu','hai','zi','chou','yin','mou','chen','si','wu','wei']
year=int(input())
t=year%10
d=year%12
print(Tiangan[t]+Dizhi[d])

输出结果：

试题G.重复字符串⭐️⭐️⭐️

🍰1.题目

重复字符串

👑2.思路分析

难度：⭐️⭐️⭐️

标签：枚举

🎇思路：字符串分组

🔱思路分析：

要令字符串$s=$某字符串$s^{\prime }$重复$k$次，且满足对字符串$s$ 的修改次数最少，因此，我们可以将字符串$s$分成连续的$k$ 个子串，每一个子串的大小为 $L=len(s)//k$ （如果有余数则无解），我们对这$k$个子串对齐摆放，按列处理即可

step：

1. 先将字符串$s$ 切片处理，也就是取长度为 $L=len(s)//k$ 的子串，如果有余数 $len(s)\%k!=0$，则无解；反之，则继续进行下一步

2. 由于新字符串的长度为 $L$，也就是：
   将$[0,len(s)-1]$分成$[0,L-1]，[L,2L-1]，...，[len(s)-L,len(s)-1]$

   
   

   如何得到这样一个 $k$ x $L$ 阶的矩阵呢？
   可以依次以$s[0\to (L-1)]$为起始，$L$为步长遍历整个字符串并取出对应位置的元素：即可得到一列的元素

   
   

3. 我们按列进行处理，每得到一列的元素，我们将其放入字典中，判断哪一个字符出现的次数最多（为$num$），则我们将出现次数少的其他元素全部改为该元素即可满足在该位置上修改的次数最少，其中，每一列至少需要修改的次数为：$cnt=k-num$

   
   

   因为总共有 $k$行，所以减去包含次数最多元素的 $num$行后，剩下的 $k-num$行需要修改

4. 循环遍历$0\to L-1$列，统计每一列至少需要修改次数之和即为$res$

图解：

$e.g$ 以字符串$s{=}^{\prime }abcababcaca{a}^{\prime }$ 为例，假设$k=4$，也就是重复出现4次

我们可以得到：$k=4，L=12//4=3$，按照上述方法，则字符串$s$ 分组为 $4$ x $3$ 阶矩阵

我们对每一列进行字典统计操作，统计出现次数最多的字符和对应的次数

所以，至少需要修改：$2+2+1=5$ 次，即将其变为 ${}^{\prime }ab{a}^{\prime }$ 重复$4$次得到$s$

💯3.代码实现

字符串分组实现：

k=int(input())
s=input()
res=0
if len(s)%k!=0: # 不能被整除print(-1) # 无解
else:l=len(s)//k # l是列数for i in range(l):  # 分别取首位置为[0,l-1]dic = {}  # 清空字典for j in range(i,len(s),l): # 以l为步长 构造同一列下的字符集字典dic[s[j]]=dic.get(s[j],0)+1val=dic.values()num=max(val) # 找到同一列中出现次数最多的数res+=k-num # k是行数 k-num即为要修改的最小数字个数print(res)

输出结果：

试题H.答疑⭐️⭐️⭐️

🍰1.题目

答疑

👑2.思路分析

难度：⭐️⭐️⭐️

标签：贪心

🎇思路：贪心算法

🔱思路分析：

首先，由贪心算法可知，我们只需要让答疑消耗总时间越短的人越先答疑，即可实现发送消息的时刻之和最短

step：

1. 将发送消息前后所需要的时间视为两个部分：即 $x_i\to 发消息\to y_i$，总时间为 $z_i=x_i+y_i$，嵌套列表存放每一个人的 $[x_i,y_i,z_i]$
2. 依据$z_i$进行从小到大的排序，当前同学发消息的时刻为 $time+x_i$，遍历所有嵌套列表，每一轮循环结束后，都让时刻处于当前同学完全结束的时刻，也就是 $time=z_0+z_1+...+z_i$，之后继续下一个同学的答疑
3. 最终，时刻之和即为$res$

证明：

现在我们来证明，为什么这道题可以用贪心算法：

$def$：首先，每个人的 $s_i$ 和 $a_i$ 都可以视为一个部分（也就是前期准备），记为 $d$；收拾时间即为 $e$

规定 $P_i$ 表示第 $i$ 个人，$x_i$和$y_i$分别对应了第$i$个人的$d$和$e$ ，$z_i=x_i+y_i$ 对应第$i$个人的答疑总时间

假设当前序列为 $P_1{P}_2...P_i{P}_{i+1}...P_n$，令 $j=i+1$

易得，交换 $P_i$ 和 $P_j$ 顺序并不会影响除了二者之外的发送消息时间，所以交换后变化的只有二者的发送时间，而影响最终结果

假设除了 $i,j$ 之外的人的发送时间之和为 $S$，则 $res=S+P_i发送时间+P_j发送时间$

记 $x_1+y_1+x_2+y_2+...+x_{i-1}+y_{i-1}$ 为 $S_{i-1}$

①交换顺序前：$P_i$ 的发送时间为 $S_{i-1}+x_i$ ，$P_j$的发送时间为 $S_{i-1}+x_i+y_i+x_j$ ，$res=S+(S_{i-1}+x_i)+(S_{i-1}+x_i+y_i+x_j)$
②交换顺序后：$P_i$ 的发送时间为 $S_{i-1}+x_j+y_j+x_i$ ，$P_j$ 的发送时间为 $S_{i-1}+x_j$ ，$re{s}^{\prime }=S+(S_{i-1}+x_j+y_j+x_i)+(S_{i-1}+x_j)$

对比 $res$ 和 $re{s}^{\prime }$，代入 $z_i,z_j$ 后可以看出：

$res=S+2S_{i-1}+x_i+x_j+$ $z_j$
$re{s}^{\prime }=S+2S_{i-1}+x_i+x_j+$$z_i$

所以，影响结果的只有每个人答疑花费的总时间 （$z_i$ 和 $z_j$），因此，只需要将总时间小的放在前面进行答疑即可（即对 $z$ 进行排序）

💯3.代码实现

贪心算法实现：

n=int(input())
li=[]
for i in range(n):x,y,z=map(int,input().split())li.append([x+y,z,x+y+z])
li.sort(key=lambda x:x[2])  # 根据总时间排序，短的放前面
time=0
res=0
for i in range(n):time+=li[i][0] # 加上前期准备时间res+=timetime+=li[i][1] # 加上离开时间
print(res)

输出结果：

试题I.补给⭐️⭐️⭐️⭐️⭐️

🍰1.题目

补给

👑2.思路分析

难度：⭐️⭐️⭐️⭐️⭐️

标签：$状压dp+Floyd$算法

🎇思路：状态压缩$dp+Floyd$算法

🔱思路分析：

本题为经典的"旅行商"问题：从起点出发，找一条经过所有n个点再回到起点的最短路径长度，于是，我们可以建模为带权无向图

step：

1. $Floyd$算法:

$Floyd$算法思想是：由小图逐渐扩展为大图，不断向已有点的集合中加入一个新的点，依次判断该点的加入是否会对集合中的点之间的最短路径产生影响

1. 用邻接矩阵$w[i][j]$储存路径：表示从点$i$到点$j$的最短路径
   初始时：$w[i][j]$表示点$i$到点$j$之间的直接路径长度
   结束时：$w[i][j]$表示点$i$到点$j$之间的最短路径长度

   
   

   注意：
   ①没有直接相连的两点默认值为无穷大
   ②w[i][i]=0

2. 将第$1$到$n$个点依次加入点集$S$中，对图中每一个点对$（i,j）$进行遍历，其中$i\in [1,n],j\in [1,n]$，如果$w[i][j]＞w[i][k]+w[k][j]$，也就是$i\to k\to j$的距离比$i$直接到$j$的距离小，于是更新 $i$ 到 $j$ 的最短路径 $w[i][j]$

3. 至此，我们就得到了无向图中任意两点间的最短距离

代码实现 $Floyd$：

def Floyd():global wfor i in range(n): # 点0到n-1for j in range(n): # 表示点i到点jfor k in range(n): # 引入第三点kw[i][j]=min(w[i][j],w[i][k]+w[k][j])

如图所示：

2. 状态压缩$dp$

对于上述问题，也就是给定一张n个点的带权无向图，点为$0$ ~ $n-1$，现在已知任意两个点的最短路径，要求起点0到达每一个点后再回来的最短路径长度，也就是$0$ ~ $n-1$个点都要经过

①确认状态：

$dp$动态规划：不难发现，我们只需要知道：①哪些点已经走过；②目前停在那个点上 即可，而此时不用关心已经遍历过的点之间的具体顺序，因为我们已经得到了经过当前点集$S$中的点的最短路径

于是，我们设状态为 $S$，$dp[S][j]$表示起点$0$到点$j$，且经过点的点集 $S$ 时的最短路径长度

则有 $dp[S][j]=dp[S-j][k]+w[k][j]$，其中$S-j$表示点集$S$中去除掉点$j$后且包含点$k$的集合，$w[k][j]$ 即为已经求得的点 $k$ 到点 $j$ 的最短路径长度

所以，当前新加入的点为 $j$，我们依次遍历$S-j$中的点 $k$，找到$S-j$到$j$最短的一条路，再更新$dp[S][j]$的值即可，以此类推，$S$ 则由 $0$ 逐渐扩展到 $n-1$

图解算法：

②状态压缩$dp$：

那么，我们应该如何表示这个集合 $S$呢？

这里就是状态压缩 $dp$的核心：用二进制数 $0/1$表示是否经过该点，$1$表示经过，$0$表示未经过

如 $01101$，表示经过了点$0$、$2$和$3$，此时点集为：$S=0,2,3$

所以，$[1,(1<<n)-1]$ 为每一个状态的点集 $S$ ，最终为 $\mathrm{111...1}(n个1)$，表示所有点都经过了

1. 初始化：dp[1][0]=0，表示只有起点时，到起点的最短距离自然为 $0$

   
   

2. 对每个状态下的$S$，遍历所有点 $[0,n-1]$，记为 $j$，判断当前 $j$ 是否在当前点集 $S$ 中：
   ①如果$j$不在：即S>>j & 1==0 （按位与 ‘&’）
   则继续找下一个在集合中的 $j$ 点；
   ②如果$j$在：即S>>j & 1!=0
   则找到没有点 $j$ 时的集合 $S-j$，遍历 $S-j$ 中的所有点 $k$，即满足：S^(1<<j)>>k &1 !=0 （按位异或 ‘^’）
   从而找到一个k，得到一条最短路径 $w[k][j]$，则有：dp[S][j]=dp[S-j][k]+w[k][j]

代码实现：

dp=[[float('inf')]*21 for _ in range(1<<21)]
dp[1][0]=0
for S in range(1,1<<n):for j in range(n):if S>>j & 1!=0: # 找到在集合S中的点jfor k in range(n):if S^(1<<j)>>k &1 !=0: # 找到在集合S-j中的点kdp[S][j]=min(dp[S][j],dp[S^(1<<j)][k]+w[k][j])

3. 最后，找到经过所有点时的最佳停留点$i(i\ne 0)$，使得此时走过的距离dp[(1<<n)-1][i]，加上点 $i$ 到起点$0$的距离w[i][0]最短

res=float('inf')
for i in range(1,n):res=min(res,dp[(1<<n)-1][i]+w[i][0]) # 最短距离=min(到最终停留点i的距离+i到0的距离)

💯3.代码实现

状压 $dp$+$Floyd$算法实现：

from math import *
def dis(a,b):d=sqrt(pow(a[0]-b[0],2)+pow(a[1]-b[1],2))return ddef Floyd():global wfor i in range(n): # 点0到n-1for j in range(n): # 表示点i到点jfor k in range(n): # 引入第三点kw[i][j]=min(w[i][j],w[i][k]+w[k][j])n,D=map(int,input().split())
w=[[float('inf')]*n for _ in range(n)] # 邻接矩阵记录最短路径
xy=[] # 记录坐标点
for i in range(n):xy.append(list(map(float,input().split())))# 最短路径
for i in range(0,n):for j in range(i+1,n):d=dis(xy[i],xy[j]) # 传入两点的坐标if d<=D: # 如果两点的距离不超过最大飞行距离 更新w[i][j] = dw[j][i] = d
Floyd()# 状态压缩
dp=[[float('inf')]*n for _ in range(1<<n)]
dp[1][0]=0
for S in range(1,1<<n):for j in range(n):if S>>j & 1!=0: # 找到在集合S中的点jfor k in range(n):if S^(1<<j)>>k &1 !=0: # 找到在集合S-j中的点kdp[S][j]=min(dp[S][j],dp[S^(1<<j)][k]+w[k][j])res=float('inf')
for i in range(1,n):res=min(res,dp[(1<<n)-1][i]+w[i][0]) # 最短距离=min(到最终停留点i的距离+i到0的距离)
print("%.2f"%res)

输出结果：（python本身运行较慢，只能通过60%）

试题J.蓝跳跳⭐️⭐️⭐️⭐️⭐️⭐️

🍰1.题目

蓝跳跳

👑2.思路分析

难度：⭐️⭐️⭐️⭐️⭐️⭐️

标签：$dp$动态规划 +矩阵快速幂

🎇思路：$dp$ +矩阵快速幂

🔱思路分析：

本题要求方案总数，因此考虑用$dp$或者$dfs$解决

此时会存在两个问题：

①$dp[L][k]$，需要的空间很大（$L=10^{18}$）
②$L$ 太大，会超时

但不要着急，我们来一一解决

step：

1.动态规划 $dp$

我们考虑直接 $dp$：

定义 $dp[i][j]$ ，$i$表示当前跳到的位置，$i$从$1$递推到$L$，$j$ 则表示走到 $i$ 位置时最后一次走的步长为 $j$

则状态转移方程为：

$$dp[i][j]=\{\begin{array}{ll}{\sum }_{d=1}^{k}dp[i-j][d]& j<p\\ & \\ {\sum }_{d=1}^{p-1}dp[i-j][d]& j\ge p\end{array}$$

也就是说，如果到位置 $i$ 时：

1. 最后一步的步长 $j<p$：那么可以选择 $[1,k]$ 中的任意一个距离跳跃到 $i-j$ 位置，因为对于当前状态下来说，无论如何都不可能存在连续两次跳跃距离 $>p$
2. 最后一步的步长 $j\ge p$：那么此时只能选择 $[1,p-1]$ 中的一个距离跳跃到 $i-j$ 位置，因为这一步超过了 $p$，那么前一步就一定不能超过 $p$

此时的时间复杂度即为： $O(kpL)$

最终结果为： $res={\sum }_{d=1}^{k}dp[L][d]$

接下来进行状态压缩<空间优化>：不难发现，对于 $j$，只有 $<p$ 和 $\ge p$ 两种状态，我们不需要直到 $j$ 的具体值，因此，将状态 $j$ 压缩为 $0/1$，于是：

定义 $dp[i][0/1]$，表示当前跳到位置 $i$，$0/1$表示最后一步是否小于 $p$ 的计数

状态转移方程变为：

$$dp[i][d]=\{\begin{array}{ll}{\sum }_{j=1}^{p-1}dp[i-j][0]+dp[i-j][1]& d=0\\ & \\ {\sum }_{j=p}^{k}dp[i-j][0]& d=1\end{array}$$

此时的时间复杂度为：$O(kL)$

最终结果为：$res=dp[L][0]+dp[L][1]$

2.矩阵快速幂

由上分析，我们发现，其状态转移 $O(kL)$ 是线性的，也就是说，对于当前状态 $i$，只和前 $k$ 个状态有关，且可以写成矩阵乘法的形式，具体地，我们写成 $2k$ x $2k$ 矩阵

例如，当 $k=3，p=2$ 时：

我们先列出线性方程组：

$$\{\begin{array}{l}dp[i][1]=dp[i-2][0]+dp[i-3][0]\\ dp[i][0]=dp[i-1][1]+dp[i-1][0]\\ dp[i-1][1]=dp[i-1][1]\\ dp[i-1][0]=dp[i-1][0]\\ dp[i-2][1]=dp[i-2][1]\\ dp[i-2][0]=dp[i-2][0]\end{array}$$

再表示为对应的矩阵乘法，也就实现了状态转移：

也就是由状态 $i-1$ 扩展到了状态 $i$

$$\left(\begin{array}{c}dp[i][1]\\ dp[i][0]\\ dp[i-1][1]\\ dp[i-1][0]\\ dp[i-2][1]\\ dp[i-2][0]\end{array}\right)=\left(\begin{array}{cccccc}0& 0& 0& 1& 0& 1\\ 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)\left(\begin{array}{c}dp[i-1][1]\\ dp[i-1][0]\\ dp[i-2][1]\\ dp[i-2][0]\\ dp[i-3][1]\\ dp[i-3][0]\end{array}\right)$$

此时，时间复杂度为：$O(8k^{3}logL)$

(这里还没有做出来，先挖个坑吧…)

💯3.代码实现

动态规划 $dp$ 实现：

k,p,L=map(int,input().split())
dp=[[0]*2 for _ in range(L+1)]
dp[0][0]=1
for i in range(1,L+1):# 1.考虑步长小于p时for j in range(1,p):if i-j<0:breakdp[i][0]+=(dp[i-j][0]+dp[i-j][1])%20201114# 2.考虑步长大于等于p时for j in range(p,k+1):if i-j<0:breakdp[i][1]+=dp[i-j][0]%20201114res=sum(dp[L])%20201114
print(res)

输出结果：

---

 

🎇觉得有帮助的话，就赏个三连吧~🎇

如有错误，欢迎指正~！