2024年09月C语言二级答案及解析

一、简答题

1、1.火中取栗
据法国诗人拉·封丹的寓言《猴子与猫》里说，猴子骗猫取火中的栗子，结果取出后被猴子吃了，猫却因此被烧掉了爪上的毛。
现在我们有 n 只炉子，每只炉子里烤着一些栗子。假设笨猫每次伸爪最多能从一只炉子里抓出 k 颗栗子，但会被烧掉 1 撮毛。问笨猫抓出所有的栗子最少要被烧掉多少撮毛？
时间限制：1000
内存限制：65536
输入
输入在第一行中给出 2 个正整数 n（≤ 100000）和 k（≤ 10），含义如题面所述。数字间以空格分隔。 随后一行给出 n 个不超过 1000 的正整数，其中第 i 个数字表示第 i 只炉子里烤的栗子的数量。
输出
在一行中输出笨猫抓出所有的栗子最少要被烧掉多少撮毛。
样例输入
5 2
3 4 8 1 15
样例输出
17

解析：

假设炉子的数量为 n，每次最多能取出的栗子数量为 k，第 i 个炉子的栗子数量为 a[i]。

1. 读入 n 和 k 的值。
2. 读入每个炉子的栗子数量 a[i]，并对它们进行排序。
3. 初始化被烧掉的撮毛数量 sum 为 0。
4. 从最大的 a[i] 开始，取出 k 个栗子，被烧掉的撮毛数量为 k，将 sum 加上 k。
5. 移动到下一个 a[i]，重复步骤 4，直到所有的栗子都被取出。
6. 输出 sum，即为笨猫抓出所有的栗子最少要被烧掉多少撮毛。

根据题目给定的样例输入，炉子的数量为 5，每次最多能取出 2 个栗子，炉子的栗子数量分别为 3、4、8、1、15。我们对炉子的栗子数量进行排序，得到 15、8、4、3、1。从 15 开始取，取 2 个栗子，被烧掉 2 撮毛，剩余 13 个栗子；从 8 开始取，取 2 个栗子，被烧掉 2 撮毛，剩余 6 个栗子；从 4 开始取，取 2 个栗子，被烧掉 2 撮毛，剩余 2 个栗子；从 3 开始取，取 1 个栗子，被烧掉 1 撮毛；从 1 开始取，不需要再被烧毛。总共被烧掉的撮毛数量为 2+2+2+1=7。因此，笨猫抓出所有的栗子最少要被烧掉 7 撮毛。

2、2.垃圾分类
据香港《南华早报》7月15日文章，上海严格的垃圾分类新规令不少居民抓狂。这催生出大量帮助找出正确分类答案的App和小程序。目前仅微信上就至少有280种与垃圾处理有关的App，在苹果应用商店也达130种。支付宝表示，已有60多家独立App开发商申请为该平台提供类似服务。
本题就请你现场实现一个简单的垃圾分类小助手。
时间限制：1000
内存限制：65536
输入
输入首先给出官方分类指南中每种物品的归属。在一行中给出一个正整数 N（≤ 100000），即物品数量；随后 N 行，每行给出一个物品名称（长度不超过 10 的、由小写英文字母和下划线组成的字符串）和该物品所属的分类（1 代表干垃圾、2 代表湿垃圾、3 代表可回收物、4 代表有害垃圾）。题目保证所有物品名称无重复。 随后每行给出一个查询物品的名称（格式与指南物品名称相同）。最后一行给出结束符 `#`，表示查询终止，这一行不需要查询。（查询的数量 ≤ 100000个）
输出
对每个查询的物品，在一行中给出其所属分类：`Gan laji` 代表干垃圾；`Shi laji` 代表湿垃圾；`Ke Hui Shou` 代表可回收物；`You Hai laji` 代表有害垃圾。如果查询的物品不在指南中，则输出 `?` 表示不知道。
样例输入
4
bao_zhi 3
dian_chi 4
dan_ke 2
bei_ke 1
dan_ke
dian_chi
ren_zha
bao_zhi
bei_ke
样例输出
Shi laji
You Hai laji
?
Ke Hui Shou
Gan laji

解析：

具体实现步骤如下：

1. 读取物品数量和每个物品的名称和分类，将每个物品的名称和分类存储到哈希表中。
2. 读取查询物品的名称，在哈希表中查找其分类。
3. 如果找到查询物品的分类，则输出对应的分类名称。
4. 如果没找到查询物品的分类，则输出"?"表示不知道。

时间复杂度为O(N+Q)，其中N为物品数量，Q为查询数量。由于时间限制为1000，内存限制为65536，因此可以使用这种简单的哈希表查找方法来实现。

3、3.生成字母串
英语老师要求学生按照如下规则写一串字母：
\- 如果写了某个大写字母，下一个就必须写同个字母的小写，或者写字母表中下一个字母的大写；
\- 如果写了某个小写字母，下一个就必须写同个字母的大写，或者写字母表中前一个字母的小写。
例如 `aAaABCDdcbBC` 就是一个合法的字母串；而 `dEFfeFGhI` 就是非法的。
本题就请你编写程序，自动生成一个合法的字母串。
时间限制：1000
内存限制：65536
输入
输入在第一行给出一个不超过 10000 的正整数 N 和第一个字母。 随后一行给出一个由 `0` 和 `1` 组成的长度为 N 的字符串。这个串给出了字母串的生成规则：从第一个字母开始，如果对应的规则串字符是 `0`，则下一个字母应该生成当前字母的大/小写；如果是 `1` 则下一个字母应该生成当前字母的前/后一个字母。 注意：因为字母表中 `a` 没有前一个字母，`Z` 没有后一个字母，所以如果此时遇到 `1` 就忽略之。
输出
在一行中输出按规则生成的字母串。
样例输入
12 a
001011101101
样例输出
aAaABCDdcbBC

解析：

我们可以使用Python语言来实现这个逻辑。首先读取输入，获取N、第一个字母以及由0和1组成的字符串。然后，根据规则生成字母串。

以下是Python代码实现：

N = int(input())  # 读取N
start_letter = input()  # 读取第一个字母
rule_string = input()  # 读取由0和1组成的字符串

# 初始化结果字符串
result = start_letter

# 根据规则生成字母串
for rule in rule_string:
    if rule == '0':
        # 如果当前字符为0，生成当前字母的大写或小写
        next_letter = result[-1].upper() if result[-1].islower() else result[-1].lower()
    elif rule == '1':
        # 如果当前字符为1，生成当前字母的前一个或后一个字母
        next_letter = chr((ord(result[-1]) - ord('a') + 1) % 26 + ord('a')) if result[-1] != 'a' else 'Z'  # 处理a的前一个字母为Z的情况
    result += next_letter  # 将生成的下一个字母添加到结果字符串中

print(result)  # 输出结果

运行以上代码，对于给定的样例输入，将输出正确的样例输出aAaABCDdcbBC。

4、4.B是A的多少倍
设一个数 A 的最低 D 位形成的数是 ad。如果把 ad 截下来移到 A 的最高位前面，就形成了一个新的数 B。B 是 A 的多少倍？例如将 12345 的最低 2 位 45 截下来放到 123 的前面，就得到 45123，它约是 12345 的 3.66 倍。
时间限制：1000
内存限制：65536
输入
输入在一行中给出一个正整数 A（≤ 109）和要截取的位数 D。题目保证 D 不超过 A 的总位数。
输出
计算 B 是 A 的多少倍，输出小数点后 2 位。
样例输入
```
样例#1：
12345 2

样例#2：
12345 5
样例输出
样例#1：
3.66
样例#2：
1.00
```

解析：

题目要求根据给定的正整数A和要截取的位数D构造出新的数B并计算B是A的多少倍。这个问题的关键在于理解题目描述中的操作过程以及如何正确地实现这个过程。首先需要将A的最低D位截取出来形成新的数ad，然后将ad移动到最高位前面形成新的数B。最后计算新的数B与原来的数A的比值即可得出答案。由于没有固定的数学公式可以直接求解这个问题，因此需要通过编程来解决。在计算过程中需要注意内存限制和计算速度的限制以避免超时或内存溢出等问题。

5、5.机器人拼图

给定一块由 n × m 个格子组成的矩形拼图板，本题要求你根据给定的机械手移动指令集，将拼图中的碎片逐一放到指定位置。
机械手每次抓取一块碎片，都会在拼图板的左上角位置等待指令。一个指令集是由 0-4 这五个数字组成的字符串，每个数字代表的意义如下：
\- 1：向右移动一格；
\- 2：向下移动一格；
\- 3：向左移动一格；
\- 4：向上移动一格；
\- 0：将碎片放置在当前位置，并结束这次任务。
如果指令要求机械手移动到拼图板边界外，机械手会无视这个指令。如果接收到指令 0 时，当前位置上已经有一块碎片放好了，机械手会扔掉手里的碎片，结束这次任务。
时间限制：5000
内存限制：65536
输入
输入第一行给出 2 个正整数 n 和 m（1 ≤ n,m ≤ 100），随后一共有 n × m 行，第 i 行给出编号为 i（i=1,... n×m）的碎片对应的指令集，每条指令集一定以唯一的 0 结尾。(总的指令操作步数不超超过107)
输出
输出 n 行，每行 m 个整数，为放置在对应位置上的碎片编号。如果该位置上没有碎片，则输出 0。一行中的数字间以 1 个空格分隔，行首位不得有多余空格。
样例输入
```
2 3
1120
21140
34120
0
110
21111340
样例输出
4 6 2
0 3 1
```

解析：

这个问题主要考察模拟和算法的实现能力。通过模拟机械手的移动和碎片放置过程，可以逐步更新拼图板的状态，并最终得到每个位置的碎片编号。在模拟过程中，需要注意处理边界情况和已有的碎片。由于指令操作步数可能非常大（不超过10^7），需要优化算法以提高效率。此外，由于输出要求每行数字间以1个空格分隔，行首位不得有多余空格，所以在输出时需要注意格式。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！