算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
m[i][n] 表示第n年、具有i年经验的人数（i=0表示新学徒，i=1,2表示不同经验年数的学徒，i=3表示3年及以上的师傅）。关于递推关系，以下哪个是错误的？题目描述：
刺绣（如苏绣、湘绣等）是珍贵的非物质文化遗产，其技艺通过"师傅带徒弟"的方式代代相传。假设某刺绣流派的传承规律如下：
- 第1年：只有1位创始师傅（经验 >= 3年）
- 每年年末统计一次人员变化
- 每位拥有3年及以上经验的艺人（师傅），每年培养 1 名新学徒（经验 = 0年）
- 学徒每年积累1年经验：0年经验 → 1年经验 → 2年经验 → 3年及以上经验（成为师傅）
- 艺人终身从事该技艺，不会退出
请使用递推算法，计算第 n 年时该流派的总从业人数。
输入格式：
输出格式：
示例输入1：
1
示例输出1：
1
示例输入2：
7
示例输出2：
10
示例输入3：
10
示例输出3：
26
递推提示：
定义四个数组：m0（新学徒）、m1（1年经验）、m2（2年经验）、m3（3年及以上经验/师傅）。
递推关系：
- m0[n] = m3[n-1]（新学徒由师傅培养）
- m1[n] = m0[n-1]（去年新学徒晋升）
- m2[n] = m1[n-1]（1年学徒晋升）
- m3[n] = m3[n-1] + m2[n-1]（师傅保留 + 2年学徒晋升为师傅）
- 总人数 = m0[n] + m1[n] + m2[n] + m3[n]
示例输入：
示例输出：
n = int(input())
# 初始化第1年的数据（索引从1开始）
m0 = [0] * (n + 1) # 新学徒（0年经验）
m1 = [0] * (n + 1) # 1年经验
m2 = [0] * (n + 1) # 2年经验
m3 = [0] * (n + 1) # 3年及以上经验（师傅）
# 第1年：只有1位创始师傅
m0[1] = 0
m1[1] = 0
m2[1] = 0
m3[1] = 1
# 递推计算第2年到第n年
for year in range(2, n + 1):
m0[year] = m3[year - 1] # 师傅培养新学徒
m1[year] = m0[year - 1] # 新学徒变为1年学徒
m2[year] = m1[year - 1] # 1年学徒变为2年学徒
m3[year] = m3[year - 1] + m2[year - 1] # 师傅保留 + 2年学徒晋升
# 计算总人数
total = m0[n] + m1[n] + m2[n] + m3[n]
print(total)
题目描述：
风筝制作是国家级非物质文化遗产。某风筝工坊准备制作一批风筝，工匠有三种材料库存：竹条、纸张、颜料。工坊有 n 种风筝设计方案，每种方案需要消耗一定数量的材料，并带来相应的"艺术评分"。每种方案最多制作 1 个风筝。请使用枚举算法，在材料总量允许的前提下，找出总艺术评分最高的方案组合。
输入格式：
- 第一行：四个整数，空格分隔，依次为 n（方案数量，1 <= n <= 12）以及三种材料的库存量 A、B、C
- 接下来 n 行：每行四个整数，空格分隔，依次为该方案需要的竹条数、纸张数、颜料数和艺术评分
输出格式：
- 第一行：最大总评分：{评分}
- 第二行：选择方案编号：{编号列表，空格分隔}（编号从1开始，按升序排列）
- 如果有多种方案组合得到相同的最大评分，输出编号列表字典序最小的那个
示例输入：
示例输出：
# 读取输入
data = list(map(int, input().split()))
n, stock_a, stock_b, stock_c = data[0], data[1], data[2], data[3]
plans = []
for i in range(n):
a, b, c, score = map(int, input().split())
plans.append((a, b, c, score))
max_score = -1
best_combo = []
# 枚举所有方案组合（2^n 种）
for mask in range(1 << n):
total_a = 0
total_b = 0
total_c = 0
total_score = 0
selected = []
# 检查每位是否被选中
for i in range(n):
if mask & (1 << i):
a, b, c, score = plans[i]
total_a += a
total_b += b
total_c += c
total_score += score
selected.append(i + 1)
# 检查材料是否足够
if total_a <= stock_a and total_b <= stock_b and total_c <= stock_c:
if total_score > max_score:
max_score = total_score
best_combo = selected
# 输出结果
print(f"最大总评分：{max_score}")
print(f"选择方案编号：{' '.join(map(str, best_combo))}")
题目描述：
木雕艺术是中华民族的传统手工艺。一位木雕艺人创作了 n 块风格各异的木雕作品，编号为 1 到 n，每块木雕有一个"风格值"，其数值即为其编号（即木雕 i 的风格值为 i）。现要将这 n 块木雕排列成一行展示，要求相邻两块木雕的风格值之和必须为质数。
请使用DFS回溯算法，找出所有满足条件的排列方案，并输出方案总数和所有方案（按字典序升序排列）。
输入格式：
输出格式：
- 第一行：共{方案数}种排列方案
- 接下来每行输出一种方案，格式为数字空格分隔（如 1 4 3 2 5）
- 方案按字典序升序排列
示例输入：
示例输出：
used[] 数组标记哪些数字已被使用，path 列表存储当前排列path 长度等于 n 时，记录一个有效方案path 中最后一个数字的和是否为质数n = int(input())
# 预处理：生成 2 到 2n 范围内的质数集合
def is_prime(x):
if x < 2:
return False
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
primes = set()
for num in range(2, 2 * n + 1):
if is_prime(num):
primes.add(num)
# 回溯搜索
solutions = [] # 存储所有有效方案
used = [False] * (n + 1) # used[i] 表示数字 i 是否已被使用
def backtrack(path):
# 终止条件：已排列完所有 n 块木雕
if len(path) == n:
solutions.append(path[:]) # 保存当前排列的副本
return
# 尝试每个未使用的数字
for i in range(1, n + 1):
if used[i]:
continue
# 剪枝：如果 path 非空，检查与最后一个数字的和是否为质数
if len(path) > 0:
if (path[-1] + i) not in primes:
continue
# 选择数字 i
used[i] = True
path.append(i)
# 递归搜索
backtrack(path)
# 回溯：撤销选择
path.pop()
used[i] = False
# 启动回溯
backtrack([])
# 输出结果
print(f"共{len(solutions)}种排列方案")
for sol in solutions:
print(' '.join(map(str, sol)))
题目描述：
某非遗文化节设有 m 个互动体验摊位，编号为 1 到 m。第 i 号摊位的体验时长为 t[i] 分钟（体验一旦开始不可中断）。每个摊位同一时间只能容纳 1 位游客体验。
共有 n 位报名游客，按报名顺序编号为 1 到 n。游客 j 在时刻 arrive[j] 分钟到达文化节现场，希望体验编号为 want[j] 的摊位。
请编写模拟程序，模拟文化节的运行过程，规则如下：
1. 游客到达后，如果其心仪的摊位处于空闲状态，且该摊位的等待队列为空，则立即开始体验
2. 游客到达后，如果其心仪的摊位正被占用或等待队列非空，则该游客加入该摊位的等待队列（按到达时间先后排队）
3. 当摊位完成一次体验时，立即检查等待队列：如果队列非空，选择队列中最早到达的游客开始体验；如果队列为空，摊位恢复空闲状态
4. 所有游客都不会中途离开，最终所有游客都会完成体验
输入格式：
- 第一行：两个整数 m 和 n（1 <= m <= 10, 1 <= n <= 100），空格分隔
- 第二行：m 个整数，表示每个摊位的体验时长（单位：分钟），空格分隔
- 接下来 n 行：每行两个整数，表示游客的到达时刻 arrive[j] 和心仪摊位编号 want[j]，空格分隔。到达时刻按非递减顺序给出（即 arrive[1] <= arrive[2] <= ... <= arrive[n]）
输出格式：
- 每位游客一行信息：游客{j}：到达{到达时刻} 摊位{摊位号} 开始{开始时刻} 结束{结束时刻}（j 从1开始）
- 一个空行
- 每个摊位一行：摊位{i}服务人次：{人次}（i 从1开始）
示例输入：
示例输出：
# 读取输入
m, n = map(int, input().split())
times = list(map(int, input().split())) # 各摊位体验时长
arrive = []
want = []
for j in range(n):
a, w = map(int, input().split())
arrive.append(a)
want.append(w)
# 初始化：每个摊位的下一个空闲时间和等待队列
# 使用 1-indexed 方便处理
free_time = [0] * (m + 1)
wait_queue = [[] for _ in range(m + 1)] # 每个元素为 (游客编号, 到达时刻)
# 存储每位游客的开始和结束时间
start_time = [0] * (n + 1)
end_time = [0] * (n + 1)
# 模拟主循环：按到达顺序处理每位游客
for j in range(n):
arr_j = arrive[j]
booth = want[j]
# 关键步骤：先处理该摊位的等待队列
# 如果摊位在游客到达前已空闲且队列中有等待者，先让他们开始体验
while wait_queue[booth]:
# 队列不为空，且摊位已空闲（空闲时间 <= 当前到达时刻）
if free_time[booth] <= arr_j:
guest_id, guest_arr = wait_queue[booth].pop(0)
start_t = max(guest_arr, free_time[booth])
start_time[guest_id] = start_t
end_time[guest_id] = start_t + times[booth - 1]
free_time[booth] = end_time[guest_id]
else:
# 摊位还未空闲，等下次再处理
break
# 现在处理当前到达的游客
if free_time[booth] <= arr_j and len(wait_queue[booth]) == 0:
# 摊位空闲且队列为空 → 立即开始体验
start_time[j + 1] = arr_j
end_time[j + 1] = arr_j + times[booth - 1]
free_time[booth] = end_time[j + 1]
else:
# 摊位被占用或队列非空 → 加入等待队列
wait_queue[booth].append((j + 1, arr_j))
# 处理所有摊位剩余的等待队列
for i in range(1, m + 1):
while wait_queue[i]:
guest_id, guest_arr = wait_queue[i].pop(0)
start_t = max(guest_arr, free_time[i])
start_time[guest_id] = start_t
end_time[guest_id] = start_t + times[i - 1]
free_time[i] = end_time[guest_id]
# 统计每个摊位的服务人次
service_count = [0] * (m + 1)
for j in range(n):
service_count[want[j]] += 1
# 输出游客信息
for j in range(1, n + 1):
print(f"游客{j}：到达{arrive[j-1]} 摊位{want[j-1]} 开始{start_time[j]} 结束{end_time[j]}")
print()
# 输出摊位服务人次
for i in range(1, m + 1):
print(f"摊位{i}服务人次：{service_count[i]}")