🏆 全国青少年信息素养大赛

算法应用主题赛 — 智传民韵(民族文化)
难度:困难 | 时长:120 分钟 | 满分:100分
题型:5单选(10分) + 5多选(20分) + 4编程(70分)

算法应用主题赛 — 智传民韵(民族文化)(困难)
考生:— 第 1 / 14 题
--:--
第 1 题 单选题 2 分
彝族的火把节上,人们手持火把排成一个矩阵。以下是一个用二维列表表示的5行5列火把方阵,若想访问第3行第4列的元素(行列均从0开始计数),正确的索引方式是?
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]
]
第 2 题 单选题 2 分
以下是用递归方式计算藏族佛塔层数的代码。调用tower(5)的返回值是?
def tower(n):
    if n == 1:
        return 1
    return n + tower(n - 1)
第 3 题 单选题 2 分
在"蒙古族游牧路线规划"问题中,每到一个草场需要决定是停留还是继续前进,每次选择局部最优解(当前草场水草最丰美就停留)。这种算法思想属于?
第 4 题 单选题 2 分
壮族"三月三"歌节上有n首山歌,需要找出所有长度恰好为k的歌名组合。这种"列举所有可能组合并逐一检验"的算法思想被称为?
第 5 题 单选题 2 分
在从文件中读取民族服饰数据时,以下代码的输出结果是?
try:
    data = {"苗族": "银饰", "藏族": "藏袍"}
    print(data["蒙古族"])
except KeyError:
    print("键不存在")
except:
    print("其他错误")
第 6 题 多选题 4 分
以下是一个民族服饰信息的嵌套数据结构。关于该数据结构的访问方式,哪些是正确的?
costumes = {
    "苗族": {"上衣": "绣花衣", "下装": "百褶裙", "银饰": ["银角", "银项圈", "银手镯"]},
    "藏族": {"上衣": "藏袍", "配饰": ["哈达", "嘎乌"]}
}
第 7 题 多选题 4 分
以下关于递归算法的说法,哪些是正确的?
第 8 题 多选题 4 分
在"民族手工艺品组合"问题中,使用枚举算法从n件工艺品中选出恰好k件的所有组合。以下哪些优化策略可以有效减少枚举量?
第 9 题 多选题 4 分
在处理民族纹样去重问题时,使用了集合(set)。以下关于集合的说法,哪些是正确的?
第 10 题 多选题 4 分
在民族节日程序中使用了global关键字。以下关于global的说法,哪些是正确的?
第 11 题 编程操作题 0 分

题目描述:
苗族银匠有若干件银饰,每件银饰的重量(克)已知。银匠需要从中选择恰好2件银饰,使其总重量恰好等于目标重量S(克)。请编写程序,找出所有满足条件的组合,并按第一件银饰的重量从小到大输出。若没有满足条件的组合,输出"无合适组合"。

输入格式:
第一行输入两个整数n和S,分别表示银饰总数和目标重量,用空格分隔(2 ≤ n ≤ 100,1 ≤ S ≤ 1000)。
第二行输入n个正整数,表示每件银饰的重量,用空格分隔。

输出格式:
每行输出一组满足条件的组合(两个整数,用空格分隔,较小的在前)。若没有满足条件的组合,输出"无合适组合"。

示例输入:

5 100
30 50 70 20 80

示例输出:

20 80
30 70
第 12 题 编程操作题 0 分

题目描述:
蒙古族牧民在迁徙时需要携带尽可能高价值的物品,但马匹的负重有限。有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位小数。

示例输入:

4 50
10 60
30 150
20 100
40 120

示例输出:

物品2: 全部
物品3: 全部
物品1: 全部
物品4: 部分(10单位)
总价值: 340.00
说明:性价比分别为6、5、5、3。物品1性价比最高(6),全取(10重量);物品2和3性价比相同(5),重量小的优先,全取物品3(20重量)、物品2(30重量);剩余负重10,取物品4的10/40=0.25部分,价值30。
第 13 题 编程操作题 0 分

题目描述:
在藏族传统中,经幡有5种颜色:蓝、白、红、绿、黄(分别象征天、云、火、水、土)。现在要用这5种颜色的经幡排成一列,要求:相邻的经幡颜色不能相同。请编写程序,计算长度为n的经幡排列方案有多少种,结果对1000000007取模。

输入格式:
输入一个整数n(1 ≤ n ≤ 1000),表示经幡的长度(面数)。

输出格式:
输出一个整数,表示满足条件的排列方案数(对1000000007取模)。

示例输入:

2

示例输出:

20
说明:第1面有5种选择,第2面需与第1面不同颜色,有4种选择。总共5×4=20种。
示例输入2:
3
示例输出2:
80
说明:5×4×4=80。
第 14 题 编程操作题 0 分

题目描述:
哈尼梯田分布在一个矩形区域内,可以用一个 m 行 n 列的二维网格表示。每个格子的值表示该处梯田的海拔高度(正整数)。水只能从海拔高的梯田流向海拔严格低于它的相邻梯田(上下左右四个方向,不能斜向流动)。
请编写程序,找出最长的连续递减灌溉路径(即从某个梯田出发,每次流向相邻且海拔严格更低的梯田,可以经过的最多梯田数),并输出该最长路径的长度。

输入格式:
第一行输入两个整数m和n,表示梯田区域的行数和列数,用空格分隔(1 ≤ m, n ≤ 50)。
接下来m行,每行输入n个整数,表示该位置的海拔高度,用空格分隔(1 ≤ 海拔 ≤ 10000)。

输出格式:
输出一个整数,表示最长递减灌溉路径经过的梯田数。

示例输入:

3 3
9 8 7
4 5 6
3 2 1

示例输出:

5
说明:最长路径可以是 9 → 8 → 7 → 6 → 1(经过5个梯田),或 9 → 4 → 3 → 2 → 1(也是5个梯田)。