中国电子学会（CEIT）考评中心历届真题（含解析答案）
C语言软件编程等级考试四级 2021年03月
编程题四道 总分:100分
一、酒鬼（25分）
Santo刚刚与房东打赌赢得了一间在New Clondike的大客厅。今天，他来到这个大客厅欣赏他的奖品。
房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是，瓶子中的酒都有不同的味道。
房东说道:“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。”
现在可怜的Santo站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。
时间限制: 2000ms
内存限制: 131072kb
输入
第一行一个整数N，有N个酒瓶。N<=700。接下有N行，第i+1行的数字代表酒瓶i中酒的体积。
输出
一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。
样例输入
6
6
10
13
9
8
1
样例输出
33
#include <iostream> // 引入输入输出流库
using namespace std; // 使用标准命名空间
int n,a[10005],dp[10005][2]; // 定义全局变量：n为瓶子数量，a为瓶子中的酒量数组，dp为动态规划数组
int main() { // 主函数开始
cin>>n; // 从标准输入读取瓶子数量n
for(int i=1; i<=n; i++) // 循环读取每个瓶子中的酒量
cin>>a[i];
dp[1][0]=0; // 初始化第一瓶没喝时的最大酒量为0
dp[1][1]=a[1]; // 初始化第一瓶喝了时的最大酒量为该瓶的酒量
for(int i=2; i<=n; i++){ // 从第二瓶开始遍历每个瓶子
// 第i瓶没喝=max(i-1瓶没喝，i-1瓶喝了)
// 即第i瓶不喝的最大酒量是前面瓶子不喝或喝了的最大酒量的较大值
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
// 第i瓶喝了=max(i-1瓶没喝，i-2瓶没喝+i-1瓶喝了)
// 即第i瓶喝了的最大酒量是前面瓶子不喝的最大酒量或前两瓶不喝加上前一瓶喝了的最大酒量的较大值
dp[i][1]=a[i] + max(dp[i-1][0], dp[i-2][0] + a[i-1]);
}
cout<<max(dp[n][0],dp[n][1]); // 输出最后瓶子不喝和喝了的最大酒量的较大值
return 0; // 主函数结束，返回0表示程序正常退出
}
/*
该代码实现了一个关于瓶子喝酒的动态规划问题，
其中dp[i][0]表示第i瓶不喝时的最大酒量，
dp[i][1]表示第i瓶喝了时的最大酒量。通过遍历
每个瓶子，不断更新这两个值，最终得到不喝和
喝了的最大酒量的较大值。
*/
二、重启系统（25分）
小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。
计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。
重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量)。
小明有一次重启系统的权限（也可以不使用)，你能帮他算出最多能完成几个任务吗?
时间限制: 1000ms
内存限制: 65536kb
输入
第一行:N(2<=N<=1000)待处理的任务数。第二行:N个整数，每个任务的数据量。
输出
输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示:回想一下最长上升子序列问题
#include <iostream> // 引入输入输出流库
#include <algorithm> // 引入算法库（尽管在这段代码中似乎没有用到）
using namespace std; // 使用标准命名空间
int n, dpleft[10005], dpright[10005], a[10005]; // 定义变量n表示数组长度，dpleft和dpright分别表示从左到右和从右到左的最长递增子序列长度，a为输入数组
int main() { // 主函数开始
cin >> n; // 输入数组长度n
for (int i = 1; i <= n; i++){ // 循环读入数组a的元素
cin >> a[i];
dpleft[i] = dpright[i] = 1; // 初始化dpleft和dpright数组，每个位置的初始值为1（因为每个元素本身构成一个递增子序列）
}
reverse(a + 1, a + n + 1); // 反转数组a，以便后续处理从右到左的递增子序列
// 计算从左到右的最长递增子序列长度dpleft
for (int i = 1; i <= n; i++){
for (int j = 1; j < i; j++){
if (a[i] >= a[j]){ // 如果当前元素大于等于前面的某个元素
dpleft[i] = max(dpleft[i], dpleft[j] + 1); // 更新dpleft[i]为当前最大值加1
}
}
}
// 优化dpleft数组，使其保存以每个位置为结尾的最长递增子序列长度
for (int i = 2; i <= n; i++){
dpleft[i] = max(dpleft[i - 1], dpleft[i]);
}
// 重复上面的过程，但是这次是为了计算从右到左的最长递增子序列长度dpright
// 注意：这里有一个冗余的循环，下面的两个循环实际上是相同的
for (int i = 2; i <= n; i++){
dpleft[i] = max(dpleft[i - 1], dpleft[i]); // 这一行是冗余的，与上一循环重复
}
for (int i = n - 1; i >= 1; i--){
for (int j = n; j > i; j--){
if (a[i] <= a[j]){ // 如果当前元素小于等于后面的某个元素
dpright[i] = max(dpright[i], dpright[j] + 1); // 更新dpright[i]为当前最大值加1
}
}
}
// 优化dpright数组，使其保存以每个位置为起始的最长递增子序列长度
for (int i = n - 1; i >= 1; i--){
dpright[i] = max(dpright[i], dpright[i + 1]); // 注意这里的索引i+1可能会导致数组越界，这是一个bug
}
int ans = 0;
for (int x = 1; x <= n; x++){
ans = max(ans, dpleft[x] + dpright[x + 1]); // 计算最长递增子序列的长度，但这里同样存在数组越界的bug
}
cout << ans; // 输出结果
return 0; // 程序结束
}
/*
这段代码中在实际过程中需要注意：
在计算dpright数组的优化过程中，最后一个循环中的
dpright[i] = max(dpright[i], dpright[i + 1]);
会导致数组越界，因为当i为n-1时，i+1将等于n，
这超出了数组dpright的范围。在计算最终答案的循环中，
ans = max(ans, dpleft[x] + dpright[x + 1]);
同样存在数组越界的问题。为了修复这些问题，你可以将
上述两个循环中的i+1改为i+1当i<n-1时，
否则为n。同时，对于dpright的优化循环
*/
三、鸣人的影分身（25分）
在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——，就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为M，他影分身的个数为N，那么制造影分身时有多少种（用K表示)不同的分配方法?(影分身可以被分配到0点查克拉能量)
时间限制: 1000ms
内存限制: 65536kb
输入
第一行是测试数据的数目t (0<=t<=20)。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
1
7 3
样例输出
8
#include <iostream> // 引入C++标准输入输出库
using namespace std; // 使用标准命名空间
int m, n, t, res; // 定义全局变量 m（火影的能量值），n（需要分配的人数），t（测试用例的数量），res（结果）
// 定义函数f，用于递归计算能量值分配方案的数量
int f(int a, int b) {
if (a == 0) // 如果火影的能量值已经分完了，说明这条分配方案是可行的，返回1
return 1;
if (b == 0) // 如果需要分配的人数已经分完了，但火影还有剩余能量，说明这条路不通，返回0
return 0;
if (a < b) { // 如果火影的能量值不能满足当前需要分配的人数，那么只能让所有人的能量值都为0
return f(a, a); // 递归调用，让所有人的能量值都为a（火影当前剩余的能量值）
} else { // 如果火影的能量值足够分配
return f(a - b, b) + f(a, b - 1); // 递归调用，尝试两种分配方案：1) 给当前的人分配能量b，剩下的人继续分配；2) 当前的人不分配能量，剩下的人继续分配
}
}
int main() {
cin >> t; // 输入测试用例的数量
while (t--) { // 对于每个测试用例
cin >> m >> n; // 输入火影的能量值m和需要分配的人数n
res = f(m, n); // 调用函数f计算分配方案的数量，并将结果存储在res中
cout << res << endl; // 输出结果
}
return 0; // 程序结束
}
/*
注意：这段代码使用递归方式解决问题，
在能量值较大或需要分配的人数较多时可能会导致栈溢出。
如果在实际应用中遇到性能问题，可以考虑使用动态规划等优化方法。
*/
四、宠物小精灵之收服（25分）
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力)。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤)，而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害;
如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小(剩余体力越大)，因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢?
时间限制: 1000ms
内存限制: 65536kb
输入
输入数据的第一行包含三个整数:N(0<N <1000)，M(0<M<500)，K (0<K<100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数:收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出
输出为一行，包含两个整数:C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
样例输入
样例输入1:
10 100 5
7 10
2 40
2 50
1 20
4 20
样例输入2:
10 100 5
8110
12 10
20 10
5 200
1 110
样例输出样例输出1:
3 30
样例输出2:
0 100
提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20)这样小智一共收服了3个小精灵，皮卡丘受到了70点伤害，剩余100-70=30点体力。所以输出3 30。
对于样例输入2∶小智一个小精灵都没法收服，皮卡丘也不会收到任何伤害，所以输出0 100。
// 引入输入输出流库
#include <iostream>
// 使用标准命名空间
using namespace std;
// 定义常量N，表示数组的最大大小为5000
#define N 5000
// 定义二维数组f，用于存储动态规划的状态
int f[N][N];
// 定义三个整数变量n, m, k，分别用于存储输入的不同值
int n, m, k;
// 定义三个长度为N的整数数组a, b, c，其中c数组在代码中并未使用
int a[N], b[N], c[N];
// 主函数
int main() {
// 从标准输入读取n, m, k的值
cin >> n >> m >> k;
// 循环k次，每次读取a[i]和b[i]的值
for (int i = 1; i <= k; i++){
cin >> a[i] >> b[i];
}
// 使用动态规划计算f数组的值
// 外层循环遍历k次
for (int i = 1; i <= k; i++){
// 内层两个循环分别遍历n和m的值，并从大到小更新f数组
for (int j = n; j >= a[i]; j--){
for (int l = m; l >= b[i]; l--)
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
// 查找m中满足f[n][ans] == f[n][m]的最大ans值
int ans;
for (ans = 0; ans <= m; ans++){
if (f[n][ans] == f[n][m])
break;
}
// 输出结果，第一个值是f[n][m]，第二个值是m - ans
printf("%d %d\n", f[n][m], m - ans);
// 返回0，表示程序正常结束
return 0;
}
/*
这段代码的主要功能是通过动态规划计算一个二维数组f，
其中f[i][j]表示在不超过i和j的限制下，能够完成的最大
任务数量。然后，它找到在不超过总资源m的条件下，能够
完成的最大任务数量f[n][m]，并输出这个数量以及剩余的资源数量m - ans。
*/