算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
n 片竹简，使用二分查找最快可以在多少次比较内找到目标（最坏情况）？dp[i] 表示前 i 个城市能获得的最大利润。已知递推关系为：dp[i] = max(dp[i-1], dp[i-2] + profit[i])（表示要么跳过城市i，要么选择城市i并加上i-2之前的利润）。这种状态转移体现了动态规划的哪个核心思想？state = 3，执行 state | 4（按位或）后，第2位（值=4，表示是否配鞍）被设置为什么？n 个城市中选出 3 个作为贸易中转站，顺序不重要。使用Python的 itertools.combinations 可以生成所有组合。combinations([1,2,3,4,5], 3) 生成的组合总数是多少？题目描述：
考古学家在丝绸之路遗址中发现了两批竹简，分别刻有两段文字。为了判断它们是否来自同一文献，需要计算两段文字的相似度。一个常用的方法是计算编辑距离（Levenshtein距离）：即将一个字符串转换成另一个字符串所需的最少操作次数。允许的操作有：插入一个字符、删除一个字符、替换一个字符。
请你使用动态规划编写程序，计算两段文字（由汉字组成的字符串）之间的编辑距离。
动态规划思路提示：
- 设 dp[i][j] 表示将字符串A的前 i 个字符转换成字符串B的前 j 个字符所需的最少操作次数。
- 如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1]（无需操作）。
- 否则，dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])（分别对应删除、插入、替换）。
- 初始化：dp[i][0] = i（删除i个字符），dp[0][j] = j（插入j个字符）。
输入格式：
第一行：一个字符串（由汉字组成），表示第一段竹简文字。
第二行：一个字符串（由汉字组成），表示第二段竹简文字。
输出格式：
一行，输出"编辑距离：X"（X为最少操作次数）。
示例输入：
示例输出：
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
# 初始化 dp 表
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
s1 = input().strip()
s2 = input().strip()
result = edit_distance(s1, s2)
print("编辑距离：" + str(result))
题目描述：
丝绸之路上的城市之间通过商路相连，构成了一个贸易网络。商人需要计算从某个起始城市到目标城市的最短路径长度（即最少经过的城市数，不含起点但含终点）。
请你使用广度优先搜索（BFS）编写程序，输入城市的数量、连接关系以及起始和目标城市，输出最短路径经过的城市数量。如果无法到达目标城市，则输出 -1。
输入格式：
第一行：两个正整数 n 和 m，以空格分隔。n 表示城市数量（城市编号从 1 到 n），m 表示直接相连的路线数量。
接下来 m 行：每行两个整数 u 和 v，以空格分隔，表示城市 u 和城市 v 之间有一条直接路线（双向通行）。
最后一行：两个整数 start 和 target，以空格分隔，表示起始城市和目标城市。
输出格式：
一行，输出一个整数：从 start 到 target 的最短路径经过的城市数量（不含起点，含终点）。如果无法到达，输出 -1。
示例输入1：
5 6
1 2
1 3
2 4
3 4
4 5
3 5
1 5
示例输出1：
2
（解释：最短路径为1→3→5，经过城市3和5，共2个城市。）
示例输入2：
4 2
1 2
3 4
1 4
示例输出2：
-1
（解释：城市1和城市4之间没有路径相连。）
示例输入：
示例输出：
from collections import deque
n, m = map(int, input().split())
# 建立邻接表
adj = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
start, target = map(int, input().split())
# BFS
visited = [False] * (n + 1)
dist = [-1] * (n + 1)
queue = deque()
visited[start] = True
dist[start] = 0
queue.append(start)
while queue:
current = queue.popleft()
if current == target:
break
for neighbor in adj[current]:
if not visited[neighbor]:
visited[neighbor] = True
dist[neighbor] = dist[current] + 1
queue.append(neighbor)
print(dist[target])
题目描述：
敦煌莫高窟的壁画数字化项目中，研究人员需要对壁画的线描图进行数据压缩。一幅线描图可以表示为一个由 0 和 1 组成的二维列表（0表示空白，1表示线条）。为了节省存储空间，使用游程编码（Run-Length Encoding, RLE）进行压缩。
游程编码的规则：
- 将连续相同的字符用"字符+连续次数"来表示。
- 压缩策略：对二维列表按行展开为一行（先行后列），然后进行游程编码。
例如：
原始二维列表：
1 1 0
0 1 1
1 0 0
按行展开（先行后列）：1 1 0 0 1 1 1 0 0
游程编码结果：
1出现2次，0出现2次，1出现3次，0出现2次
输出格式：1 2 0 2 1 3 0 2
请你编写程序实现以下功能：
1. 读取用户输入的 m 行 n 列的二维01矩阵。
2. 按先行后列的顺序展开为一维序列。
3. 对一维序列进行游程编码。
4. 输出压缩后的编码结果和压缩率。
输入格式：
第一行：两个正整数 m 和 n，以空格分隔，表示矩阵的行数和列数。
接下来 m 行：每行 n 个字符（0 或 1），以空格分隔。
输出格式：
第一行：游程编码： 后依次输出编码结果（数字之间以空格分隔）。
第二行：原始大小：X个字符
第三行：压缩后大小：Y个数字
第四行：压缩率：Z%（保留1位小数，压缩率 = (原始大小 - 压缩后大小) / 原始大小 × 100%）
示例输入：
示例输出：
m, n = map(int, input().split())
# 读取矩阵并展开为一维序列
flat = []
for _ in range(m):
row = input().split()
for ch in row:
flat.append(ch)
# 游程编码
encoded = []
if len(flat) > 0:
current_char = flat[0]
count = 1
for i in range(1, len(flat)):
if flat[i] == current_char:
count += 1
else:
encoded.append(current_char)
encoded.append(str(count))
current_char = flat[i]
count = 1
encoded.append(current_char)
encoded.append(str(count))
# 输出编码结果
print("游程编码：" + " ".join(encoded))
# 计算压缩率
original_size = m * n
compressed_size = len(encoded)
rate = round((original_size - compressed_size) / original_size * 100, 1)
print("原始大小：" + str(original_size) + "个字符")
print("压缩后大小：" + str(compressed_size) + "个数字")
print("压缩率：" + str(rate) + "%")
题目描述：
丝绸之路上的驼队有 n 件货物可供选择，每件货物有固定的重量（斤）和价值（文）。骆驼的最大负重为 W 斤。商人希望选择若干件货物（每件货物最多选一次），使得总重量不超过 W 的前提下，总价值最大。
请你使用回溯算法编写程序，对货物进行深度优先搜索，找出最大总价值。为了优化搜索效率，请实现简单的剪枝策略：如果当前路径即使把后面所有货物全选上也无法超过已知的最大价值，则不再继续搜索（此剪枝非强制，可不实现。但需正确输出结果）。
输入格式：
第一行：两个正整数 n 和 W，以空格分隔。n 表示货物件数，W 表示最大负重。
接下来 n 行：每行两个正整数 weight 和 value，以空格分隔，分别表示该货物的重量和价值。
输出格式：
一行，输出"最大总价值：X文"（X为最大总价值）。
示例输入：
示例输出：
n, W = map(int, input().split())
weights = []
values = []
for _ in range(n):
w, v = map(int, input().split())
weights.append(w)
values.append(v)
# 计算后缀最大可能价值（用于剪枝）
suffix_max = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix_max[i] = suffix_max[i + 1] + values[i]
max_value = 0
def dfs(index, current_weight, current_value):
global max_value
# 更新最大价值
if current_value > max_value:
max_value = current_value
# 所有货物都考虑完了
if index >= n:
return
# 剪枝：即使把后续所有货物都选上也无法超过当前最优
if current_value + suffix_max[index] <= max_value:
return
# 选择当前货物（如果重量允许）
if current_weight + weights[index] <= W:
dfs(index + 1, current_weight + weights[index],
current_value + values[index])
# 不选当前货物
dfs(index + 1, current_weight, current_value)
dfs(0, 0, 0)
print("最大总价值：" + str(max_value) + "文")