跳转至

蓝桥杯【第11届真题】Python 实现

【题目描述】

小蓝给学生们组织了一场考试，卷面总分为100 分，每个学生的得分都是一个0 到100 的整数。请计算这次考试的最高分、最低分和平均分。

【输入格式】

输入的第一行包含一个整数n，表示考试人数。

接下来n 行，每行包含一个0 至100 的整数，表示一个学生的得分。

【输出格式】

输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

【样例】

输入 输出
7

80

92

56

74

88

99

10		 99

10

71.29

【评测用例规模与约定】

50% 1 ≤ n ≤ 100
100% 1 ≤ n ≤10000

【解析及代码】

展开查看 
num = int(input())
score = [int(input()) for _ in range(num)]

print(max(score))
print(min(score))
print(f"{sum(score) / num:.2f}")

回文日期

【题目描述】

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即2021年12月2日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。

【输入格式】

输入包含一个八位整数N，表示日期

【输出格式】

输出两行，每行1 个八位数。第一行表示下一个回文日期，第二行表示下一个ABABBABA 型的回文日期

【样例】

输入 输出
20200202 20211202

21211212

【评测用例规模与约定】

100% 10000101 ≤ N ≤ 89991231


保证 N 是一个合法日期的8位数表示

【解析及代码】

定义 check_date 函数，使用 datetime 模块和 try 语句对日期的正确与否进行判断

然后使用一个 while 循环对两种日期进行搜索，对 result 中的 None 进行替换

date 对象的字符串是 2001-03-23 这种形式，使用字符串的 replace 方法把“-”去掉，再输出就好了

展开查看 
from datetime import date

date_begin = input()
year, month, day = map(int, (date_begin[:4], date_begin[4: 6], date_begin[6:]))
date_begin = date(year, month, day)def check_date(y, md):
    m, d = map(int, (md[:2], md[2:]))
    try:
        date_ = date(y, m, d)
        # 确保日期在起始日期之后
        assert date_ > date_begin
        return date_
    except:
        return Falseresult = [None] * 2
while not all(result):
    # 构建回文日期
    md = str(year)[::-1]
    # 确认是否是正确日期
    date_ = check_date(year, md)
    if date_:
        # 普通回文日期未找到
        if not result[0]: result[0] = date_
        # ABABBABA 回文日期未找到, 判断年份是不是 ABAB
        if not result[1] and year // 100 == year % 100: result[1] = date_
    # 年份递增
    year += 1

result = map(lambda d: str(d).replace('-', ''), result)
print(*result, sep='\n')

子串分值

【题目描述】

对于一个字符串 S (长度 n)，我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如 f(”aba”) = 1，f(”abc”) = 3, f(”aaa”) = 0。

现在给定一个字符串 S (长度为 n)，请你计算对于所有 S 的非空子串 S[i…j] (0 ≤ i ≤ j < n)，f (S[i… j]) 的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串 S。

【输出格式】

输出一个整数表示答案。

【样例】

输入 输出 说明
ababc 21 a     1

ab    2

aba   1

abab  0

ababc 1

b    1

ba   2

bab  1

babc 2

a   1

ab  2

abc 3

b  1

bc 2

c 1

【评测用例规模与约定】

20% 1 \leq n \leq 10
40% 1 \leq n \leq 100
50% 1 \leq n \leq 1000
60% 1 \leq n \leq 10000
100% 1 \leq n \leq 100000

【解析及代码】

换个角度想这个问题，每个字符可以贡献多少分，也就是每个字符可以有效地出现在多少个子串里

如果给定 ababc，那么计算方法如下： * i = 0：a 向左找相同字符索引为 -1 (找不到)，向右找是 2，那么所在的有效子串数为 (0 - (-1)) × (2 - 0) = 2，包含 “a”、“ab” * i = 1：b 向左找相同字符索引为 -1 (找不到)，向右找是 3，那么所在的有效子串数为 (1 - (-1)) × (3 - 1) = 4，包含 “ab”、“b”、“ba”、“aba” * i = 2：a 向左找相同字符索引为 0，向右找是 5 (找不到)，那么所在的有效子串数为 (2 - 0) × (5 - 2) = 6，包含 “ba”、“a”、“ab”、“abc”、“bab”、“babc” 以此类推，可以得到最终答案是 2 + 4 + 6 + 4 + 5 = 21

利用 find 函数进行字符查找：字符串的 find 函数找不到时会返回 -1，左边界的溢出是 -1 不用管；右边界的溢出应该是 n，对 n+1 取模进行纠正

展开查看 
s = input()

ans = 0
for i in range(len(s)):
    lp = s.rfind(s[i], 0, i)
    rp = s.find(s[i], i + 1) % (len(s) + 1)
    ans += (i - lp) * (rp - i)
print(ans)

作物杂交

【题目描述】

作物杂交是作物栽培中重要的一步。已知有N种作物(编号 1 至 N)，第i种作物从播种到成熟的时间为Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。

如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。

初始时，拥有其中 M 种作物的种子(数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。

求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A×B→C，A×C→D。

则最短的杂交过程为：

第 1 天到第 7天(作物B的时间)，A×B→C。

第 8 天到第 12 天(作物 A的时间)，A×C→D。花费 12 天得到作物 D 的种子。

【输入格式】

输入的第 1 行包含4个整数 N,M,K,T，N 表示作物种类总数(编号 1 至 N)，M 表示初始拥有的作物种子类型数量，K 表示可以杂交的方案数，T 表示目标种子的编号。第 2 行包含 N 个整数，其中第 i 个整数表示第 i 种作物的种植时间 T_i

( 1 \leq T_i \leq 100【输出格式】

输出一个整数，表示得到目标种子的最短杂交时间

【样例】

输入 输出 说明
6 2 4 6

5 3 4 6 4 9

1 2

1 2 3

1 3 4

2 3 5

4 5 6		 16 第 1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种子


第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种子


第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种子


第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种子


总共花费16天。

【评测用例规模与约定】

100% 1 ≤ N ≤ 2000, 2 ≤ M ≤ N, 1 ≤ K ≤ 100000, 1 ≤ T ≤ N

【解析及代码】

这个题我是在蓝桥杯练习系统测的

首先来分析一下样例，假设已经完成 A × B -> C，现在要做 A × C -> D
idx A B C D
time 0 0 7 inf
cost 5 7 3 8
time 表示整个流程中得到种子所需时间 (已有的记为0)，cost 代表种子成熟所需时间

我初看这道题时的思路是：time[D] = max([ time[A] + cost[A], time[C] + cost[C] ])

但是这个想法得到的结果是：time[D] = 10，明显与题意不符

正确的思路应该是：time[D] = max([ time[A], time[C] ]) + max([ cost[A], cost[C] ]) = 12

也就是：新种子 time = max(两种子 time) + max(两种子 cost)

官网练习系统给这道题打的标签是：图论、贪心。我建了很复杂的 AOV 网，代码直接把自己绕晕，放弃了。现在发现用树来替代 AOV 网是个很不错的选择，树和 AOV 网一样没有环嘛

定义树结点 Node，在 __init__ 方法里面把 cost 和 time 的信息录入，写个 __add__ 方法用于添加子结点，写个 search 方法用于计算 time

展开查看 
from math import inf

classes, _, ways, target = map(int, input().split())
target -= 1

# 种子成熟所需时间
cost = list(map(int, input().split()))
time = [inf] * classes
# 得到种子所需时间
tran = lambda n: int(n) - 1
for i in map(tran, input().split()): time[i] = 0class Node:
    def __init__(self, cost, time):
        self.cost = cost
        self.time = time
        self.ways = []

    def __add__(self, other):
        # 用于 成对 添加子节点
        self.ways.append(other)
        return self

    def search(self):
        # 用于计算种子的 time
        if self.time == inf:
            for a, b in self.ways:
                waste = max([a.search(), b.search()]) + max([a.cost, b.cost])
                # 方案时间来源: 两种子 time 的最大值 + 两种子 cost 的最大值
                self.time = min([self.time, waste])
        return self.time# 初始化种子结点
seed = [Node(cost[i], time[i]) for i in range(classes)]

for i in range(ways):
    a, b, c = map(tran, input().split())
    # 调用 Node 类的 __add__ 方法，添加子结点 (从 seed 列表中取)
    seed[c] += (seed[a], seed[b])

seed[target].search()
print(seed[target].time)

游园安排

【题目描述】

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球

游乐园的管理员。为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟0 个或多个小写英文字母。游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字母与 B 的前 i 个字母相同，且 A 的第 i+1 个字母小于 B 的第 i+1 个字母。（如果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A 的第 i + 1 个字母小于 B 的第 i + 1 个字母）作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

【输入格式】

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

【输出格式】

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符

【样例】

输入 输出
WoAiLanQiaoBei AiLanQiao

【评测用例规模与约定】

20% 输入的总长度不超过 20 个字母
50% 输入的总长度不超过 300 个字母
70% 输入的总长度不超过 10000 个字母
100% 每个名字的长度不超过 10 个字母


输入的总长度不超过 1000000 个字母

【解析及代码】

这个题其实就是找最长递增序列，用正常的动态规划思路可以求出长度，但是还要记录这个序列、求字典序最小的，这就有点抠门

首先处理一下输入，用这个正则表达式可以匹配“Lan”、“Qiao”、“B”这种字符串，用findall函数找到所有的这种字符串即可完成分组

然后用一个 n 行 2 列的矩阵 dp 来记录状态，第 1 列表示前 n 行最长递增序列长度，第 2 列表示前 n 行最长递增序列 (字典序最小)

然后在做状态转移的时候严格控制字典序最小就好了，考虑达到最大长度的序列可能有多个，所以还要：找到最大长度，找到对应该长度的序列，取字典序最小的输出

展开查看 
import re

mode = re.compile(r"[A-Z][a-z]*")
# 将字符串切分成若干个元素
origin = re.findall(mode, input())

# 初始化: 每个位置的初始长度1, 初始字符串只有对应位置元素
dp = [[1, origin[_]] for _ in range(len(origin))]
for i in range(1, len(origin)):
    # 读取当前状态
    state, string = dp[i]
    # 读取当前索引下的元素
    cur_ele = origin[i]
    for last in range(i):
        # 读取前置状态
        l_state, l_string = dp[last]
        # 读取对应前置状态索引对应的元素
        l_ele = origin[last]
        # < 运算符比较字典序，满足递增条件
        if l_ele < cur_ele:
            # 启动状态转移
            if l_state + 1 > state:
                state = l_state + 1
                string = l_string + cur_ele
            # 取字典序最小的字符串
            elif l_state + 1 == state:
                string = min([l_string + cur_ele, string])
    # 记录到dp矩阵中
    dp[i] = [state, string]

# 找到元素最长的长度
result = max(dp, key=lambda x: x[0])[0]
choose = []
for val, string in dp:
    # 因为达到最大长度的元素有多个，所以要汇总、取字典序最小的
    if val == result: choose.append(string)
print(min(choose))

答疑

【题目描述】

有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下：

首先进入办公室，编号为 i 的同学需要 s i 毫秒的时间。然后同学问问题老师解答，编号为 i 的同学需要 a i 毫秒的时间。

答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。最后同学收拾东西离开办公室，需要 e i 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 e i 取值为 10000，20000 或 30000。一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。

【输入格式】

输入第一行包含一个整数 n，表示同学的数量。

接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 s i , a i , e i ，意义如上所述。

【输出格式】

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少

【样例】

输入 输出 说明
3

10000 10000 10000

20000 50000 20000

30000 20000 30000		 280000 按照 1, 3, 2 的顺序答疑


发消息的时间分别是


20000, 80000, 180000

【评测用例规模与约定】

30% 1 \leq n \leq 20
60% 1 \leq n \leq 200
100% 1 \leq n \leq 1000, 1 \leq s_i\leq 60000, 1 \leq a_i \leq 10^6

【解析及代码】

记准备时间 s = s + a，离开时间 e，将 3 个时间段合并成 2 个

设 basic_{n}

代表前 n 个同学的时间总和

假设当前已经有最优排序，第 n 位同学和第 n + 1 位同学对时间的贡献为：

best = 2 * ( basic_{n - 1} + e_{n - 1}+ s_{n} ) + e_{n} + s_{n + 1} 现交换第 n 位同学与第 n + 1 位同学的位置，第n位同学和第 n + 1 位同学对时间的贡献为：

new = 2 * ( basic_{n - 1} + e_{n - 1} + s_{n + 1} ) + e_{n + 1} + s_{n} 因为第一种是最优排序，所以满足 best < new，得：

s_{n} + e_{n} < s_{n + 1} + e_{n + 1} 所以依照 sum([s, a, e]) 排序就可以得到正确排序了

展开查看 
num = int(input())
greed = []
for _ in range(num):
    s, a, e = map(int, input().split())
    greed.append([s + a + e, s + a])

# 按照三个时间的总和排序
greed.sort()
basic, res = 0, 0
for summary, pre in greed:
    res += basic + pre
    basic += summary

print(res)

蓝跳跳

【题目描述】

小蓝制作了一个机器人，取名为蓝跳跳，因为这个机器人走路的时候基本靠跳跃。

蓝跳跳可以跳着走，也可以掉头。蓝跳跳每步跳的距离都必须是整数，每步可以跳不超过 k 的长度。由于蓝跳跳的平衡性设计得不太好，如果连续两次都是跳跃，而且两次跳跃的距离都至少是 p，则蓝跳跳会摔倒，这是小蓝不愿意看到的。

小蓝接到一个特别的任务，要在一个长为 L 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边，然后掉头，然后从右边走到左边，然后掉头，然后再从左边走到右边，然后掉头，再从右边走到左边，然后掉头，如此往复。为了让观者不至于太无趣，小蓝决定让蓝跳跳每次用不同的方式来走。小蓝将蓝跳跳每一步跳的距离记录下来，按顺序排成一列，显然这一列数每个都不超过 k 且和是 L。这样走一趟就会出来一列数。如果两列数的长度不同，或者两列数中存在一个位置数值不同，就认为是不同的方案。

请问蓝跳跳在不摔倒的前提下，有多少种不同的方案从舞台一边走到另一边。

【输入格式】

输入一行包含三个整数 k, p, L

【输出格式】

输出一个整数，表示答案。答案可能很大，请输出答案除以 20201114 的余数

【样例】

输入 输出
3 2 5 9
5 3 10 397

【评测用例规模与约定】

30% 1 \leq p \leq k \leq 50, 1 \leq L \leq 1000
60% 1 \leq p \leq k \leq 50, 1 \leq L \leq 10^{9}
80% 1 \leq p \leq k \leq 200, 1 \leq L \leq 10^{18}
100% 1 \leq p \leq k \leq 1000, 1 \leq L \leq 10^{18}

【解析及代码】

这个 L 都干到 10^{18}

了，如果用正常的 dp 思路，需要用 10^{18}\times 2

这么大的矩阵

先从简单的说起，就用这么大的矩阵做 dp，dp[i] 存储跳跃总长度为 i 时的方案数： * dp[i][0] 表示下一次跳跃无限制的方案数（即上一次跳跃 < p）： dp[i][0] = \sum_{j=1}^{p-1}dp[i-j][0]+dp[i-j][1]

  • dp[i][1] 表示下一次跳跃有限制的方案数（即上一次跳跃 ≥ p）： dp[i][1]=\sum_{j=p}^{k}dp[i][0] 可见，dp[i] 只与其之前的 k 个状态有关，那么只循环使用一个 k × 2 的矩阵：
  • dp[i] 表示距离下一个落地点距离为 i + 1 的地点
  • 使下一步跳跃无限制的方案数：本次跳跃 < p，dp[: p-1][0] 以及 dp[: p-1][1] 的和
  • 使下一步跳跃有限制的方案数：本次跳跃 ≥ p，dp[p-1: ][0] 的和
展开查看 
k, p, l = map(int, input().split())
mod = 20201114

# 跳跃无限制, 跳跃有限制
dp = [(0, 0) for _ in range(k)]
# dp[0] 永远最新
dp[0] = (1, 0)
# 使下一步无限制: dp[:p - 1] 的和 (跳跃长度 < p)
sum_0 = 1
# 使下一步有限制: dp[p - 1:, 0] 的和 (跳跃长度 >= p)
sum_1 = 1 if p - 1 == 0 else 0

p -= 1
for _ in range(l):
    dp.insert(0, (sum_0, sum_1))
    # dp 发生变化, 更新 sum_0, sum_1
    sum_0 = (sum_0 + sum(dp[0]) - sum(dp[p])) % mod
    sum_1 = (sum_1 + dp[p][0] - dp.pop()[0]) % mod

print(sum(dp[0]) % mod)

补给

【题目描述】

小蓝是一个直升飞机驾驶员，他负责给山区的 n 个村庄运送物资。

每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。

每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 D。每个直升机场都有加油站，可以给直升机加满油。

每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。

总部位于编号为 1 的村庄。

请问，要完成一个月的任务，小蓝至少要飞行多长距离？

【输入格式】

输入的第一行包含两个整数 n , D，分别表示村庄的数量和单次飞行的距离。

接下来 n行描述村庄的位置，其中第 i 行两个整数 xi , yi 分别表示编号为 i 的村庄的坐标。村庄 i 和村庄 j 之间的距离为 \sqrt{(x_i -x_j)^2 + (y_i -y_j)^2 }【输出格式】

输出一行，包含一个实数，四舍五入保留正好 2 位小数，表示答案

【样例】

输入 输出
4 6

1 1

4 5

8 5

11 1		 28.00

【评测用例规模与约定】

100% 1 \leq n \leq20, 1 \leq x_i, y_i \leq 10^4, 1 \leq D \leq 10^5

【解析及代码】

这个题 n 的数据规模是 [1, 20]，所以思路就是 图 + 状态压缩

首先读取输入，得出这个图的邻接矩阵

展开查看 
from math import inf, sqrt, pow

# 表示村庄的数量、飞行距离限制
num, limit = map(int, input().split())
# 记录每个顶点的坐标
loc = [list(map(int, input().split())) for idx in range(num)]
# 初始化邻接矩阵
adj = [[inf] * num for _ in range(num)]

for begin in range(num):
    x_b, y_b = loc[begin]
    for end in range(begin + 1, num):
        x_e, y_e = loc[end]
        # 计算距离
        value = sqrt(pow(x_b - x_e, 2) + pow(y_b - y_e, 2))
        # 如果距离允许则直接填入邻接矩阵
        if value <= limit:
            adj[begin][end] = adj[end][begin] = value

在创建邻接矩阵的时候已经保证了飞机单次飞行的距离不会超限，但这样使在做状态转移时需要考虑某地点被多次经过、状态转移过于繁琐。所以用一下 Floyd 算法处理一下邻接矩阵，求出多源最短路

展开查看 
def Floyd():
    for mid in range(num):
        for begin in range(num):
            if adj[begin][mid] != inf:
                for end in range(begin, num):
                    state = min([adj[begin][end], adj[begin][mid] + adj[mid][end]])
                    adj[begin][end] = adj[end][begin] = state# 求出多源最短路
Floyd()

用二进制数来表示经过的地点。如 0000 表示停留在起点 (第 1 个地点) 未经过任何地点，0010 表示从起点出发经过第 2 个地点，1111 表示从起点出发经过第 2、3、4 个地点并返回起点。现在依据“经过几个地点”对二进制状态进行分层

bin 函数可以将整数转化为二进制字符串，如：5 -> "0b101"。利用该函数可得出经过地点的数目 n，然后利用位运算筛除所有包含第 1 个地点的状态。假设总共有 4 个地点，因为第 1 个地点是要最后到达的，所以最终状态应该是 1111 (15)，即 (1 << 4) - 1，把这个状态分在最后一层

展开查看 
# dp[i][j][k]
# i: 从起点出发并经过 i 个村庄
# j: 二进制状态
# k: 当前停留在 k 号村庄
dp = [{} for _ in range(num + 1)]
for choose in range(1 << num):
    # 筛选掉所有经过起点的状态
    if not choose & 1:
        cnt = bin(choose).count('1')
        dp[cnt][choose] = {}
# 终态: 已经过所有村庄
the_end = (1 << num) - 1
dp[-1][the_end] = {}
# 初态: 停留在起点 (0 号村庄)
dp[0][0] = {0: 0}

last_choose (二进制状态) 取自 dp[count-1]，cur_choose 取自 dp[count]，所以已经过地点的数目必满足：cur_choose - last_choose == 1。假设 last_choose 是 0010，cur_choose 是 0101，利用 last_choose | cur_choose == cur_choose 这个条件可以筛除掉这种不合法的状态转移

假设 last_choose 是 0010，cur_choose 是 0110，cur_choose - last_choose = 0100，用len(bin(cur_choose - last_choose[2:])) - 1 可以求出新经过的地点索引

展开查看 
def deliver(cnt, choose, stay, value):
    # 状态传递函数
    origin = dp[cnt][choose].get(stay, inf)
    dp[cnt][choose][stay] = min([origin, value])for cnt in range(1, num + 1):
    for last_choose in dp[cnt - 1]:
        for cur_choose in dp[cnt]:
            # 判断状态转移是否合法
            if last_choose | cur_choose == cur_choose:
                # 当前状态的停留地
                cur_stay = len(bin(cur_choose - last_choose)[2:]) - 1
                # 枚举上一个状态的所有停留地
                for last_stay in dp[cnt - 1][last_choose]:
                    deliver(cnt, cur_choose, cur_stay,
                            dp[cnt - 1][last_choose][last_stay] + adj[last_stay][cur_stay])

result = min(dp[-1][the_end].values())
print(f'{result:.2f}')