算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
torch = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]
]tower(5)的返回值是？def tower(n):
if n == 1:
return 1
return n + tower(n - 1)try:
data = {"苗族": "银饰", "藏族": "藏袍"}
print(data["蒙古族"])
except KeyError:
print("键不存在")
except:
print("其他错误")costumes = {
"苗族": {"上衣": "绣花衣", "下装": "百褶裙", "银饰": ["银角", "银项圈", "银手镯"]},
"藏族": {"上衣": "藏袍", "配饰": ["哈达", "嘎乌"]}
}global关键字。以下关于global的说法，哪些是正确的？题目描述：
苗族银匠有若干件银饰，每件银饰的重量（克）已知。银匠需要从中选择恰好2件银饰，使其总重量恰好等于目标重量S（克）。请编写程序，找出所有满足条件的组合，并按第一件银饰的重量从小到大输出。若没有满足条件的组合，输出"无合适组合"。
输入格式：
第一行输入两个整数n和S，分别表示银饰总数和目标重量，用空格分隔（2 ≤ n ≤ 100，1 ≤ S ≤ 1000）。
第二行输入n个正整数，表示每件银饰的重量，用空格分隔。
输出格式：
每行输出一组满足条件的组合（两个整数，用空格分隔，较小的在前）。若没有满足条件的组合，输出"无合适组合"。
示例输入：
示例输出：
n, S = map(int, input().split())
weights = list(map(int, input().split()))
# 用于存储结果
results = []
# 枚举所有两两组合
for i in range(n):
for j in range(i + 1, n):
if weights[i] + weights[j] == S:
a, b = weights[i], weights[j]
if a > b:
a, b = b, a
results.append((a, b))
# 排序：先按第一个数，再按第二个数
results.sort()
if len(results) == 0:
print("无合适组合")
else:
for a, b in results:
print(a, b)
题目描述：
蒙古族牧民在迁徙时需要携带尽可能高价值的物品，但马匹的负重有限。有n件物品，每件物品有重量w_i和价值v_i（均为正整数）。牧民希望选择若干件物品，使得总重量不超过马匹最大负重M，且总价值最大。
请使用性价比贪心策略（优先选择单位重量价值最高的物品；若单位重量价值相同，优先选择重量小的）来解决此问题。按选择的顺序输出每件物品的编号（从1开始编号）。
注意：本题中的物品是可分割的（连续型），即可以选择物品的一部分。请按所选顺序输出物品编号，若某个物品只取了一部分，则在编号后加上"（部分）"。
输入格式：
第一行输入两个整数n和M，表示物品数量和最大负重，用空格分隔（1 ≤ n ≤ 100，1 ≤ M ≤ 1000）。
接下来n行，每行输入两个整数w_i和v_i，表示第i件物品的重量和价值。
输出格式：
每行输出一件被选中物品的信息：
- 若整件取走：输出"物品X: 全部"
- 若部分取走：输出"物品X: 部分(Y单位)"，其中Y为取走的重量
最后一行输出"总价值: Z"，Z保留2位小数。
示例输入：
示例输出：
n, M = map(int, input().split())
items = []
for i in range(n):
w, v = map(int, input().split())
ratio = v / w
items.append([i + 1, w, v, ratio])
# 排序：性价比降序，性价比相同按重量升序
items.sort(key=lambda x: (-x[3], x[1]))
remaining = M
total_value = 0.0
for idx, w, v, ratio in items:
if remaining <= 0:
break
if w <= remaining:
# 全部取走
print(f"物品{idx}: 全部")
remaining -= w
total_value += v
else:
# 部分取走
taken = remaining
print(f"物品{idx}: 部分({taken}单位)")
total_value += ratio * taken
remaining = 0
print(f"总价值: {total_value:.2f}")
题目描述：
在藏族传统中，经幡有5种颜色：蓝、白、红、绿、黄（分别象征天、云、火、水、土）。现在要用这5种颜色的经幡排成一列，要求：相邻的经幡颜色不能相同。请编写程序，计算长度为n的经幡排列方案有多少种，结果对1000000007取模。
输入格式：
输入一个整数n（1 ≤ n ≤ 1000），表示经幡的长度（面数）。
输出格式：
输出一个整数，表示满足条件的排列方案数（对1000000007取模）。
示例输入：
示例输出：
n = int(input())
MOD = 1000000007
# 递推：f(n) = 5 * 4^(n-1)
# 第一面有5种选择，之后每面都有4种选择（不能与前面相同）
result = 5
for i in range(1, n):
result = (result * 4) % MOD
print(result)
```
**递归版本参考代码**：
```python
n = int(input())
MOD = 1000000007
def count_arrangements(length):
if length == 1:
return 5
return (count_arrangements(length - 1) * 4) % MOD
print(count_arrangements(n))
题目描述：
哈尼梯田分布在一个矩形区域内，可以用一个 m 行 n 列的二维网格表示。每个格子的值表示该处梯田的海拔高度（正整数）。水只能从海拔高的梯田流向海拔严格低于它的相邻梯田（上下左右四个方向，不能斜向流动）。
请编写程序，找出最长的连续递减灌溉路径（即从某个梯田出发，每次流向相邻且海拔严格更低的梯田，可以经过的最多梯田数），并输出该最长路径的长度。
输入格式：
第一行输入两个整数m和n，表示梯田区域的行数和列数，用空格分隔（1 ≤ m, n ≤ 50）。
接下来m行，每行输入n个整数，表示该位置的海拔高度，用空格分隔（1 ≤ 海拔 ≤ 10000）。
输出格式：
输出一个整数，表示最长递减灌溉路径经过的梯田数。
示例输入：
示例输出：
# 使用DFS + 记忆化搜索
m, n = map(int, input().split())
grid = []
for i in range(m):
grid.append(list(map(int, input().split())))
# 记忆化数组，memo[i][j]表示从(i,j)出发的最长路径长度
memo = [[0] * n for _ in range(m)]
# 四个方向：上、下、左、右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
# 如果已经计算过，直接返回
if memo[x][y] != 0:
return memo[x][y]
max_len = 1 # 至少包含当前格子
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 检查边界
if 0 <= nx < m and 0 <= ny < n:
# 只能流向海拔严格更低的位置
if grid[nx][ny] < grid[x][y]:
max_len = max(max_len, 1 + dfs(nx, ny))
memo[x][y] = max_len
return max_len
# 从每个位置出发计算最长路径
answer = 0
for i in range(m):
for j in range(n):
answer = max(answer, dfs(i, j))
print(answer)