首页 › 试卷 › C/C++编程考级 › C/C++编程五级 › 2024年12月电子学会青少年软件编程(C/C++)5级等级考试真题试卷

2024年12月电子学会青少年软件编程(C/C++)5级等级考试真题试卷 VIP

C/C++编程五级 共 4 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

小白兔拔萝卜

小白兔拔萝卜,但是它的力量有限,太大的萝卜它拔不动。于是它叫来了一群小伙伴……

本题就请你根据小白兔们的力量和拔出这个萝卜需要的力量,告诉小白兔,它最少需要哪些伙伴能拔出这只大萝卜。

时间限制:7000,内存限制:65536

输入描述

输入在第一行里给出两个不超过 1000 的正整数 n 和 T,分别是小白兔的数量和拔出这个萝卜需要的力量。

随后一行给出 n 个不超过 100 的正整数,其中第 i 个数对应编号为 i 的小白兔的力量(i=1, … , n)。

输出描述

如果兔子们有可能拔成功,则首先在第一行输出最少需要多少只兔子才能拔出这只萝卜,然后第二行从小到大输出参与拔萝卜的兔子们的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。 

如果所有兔子合力都不能拔出萝卜,则首先在第一行输出 0,随后在第二行中输出:Suan4 le ba, hai2 cha4 X. 其中 X 是小白兔们缺少的力量值。

注意:力量等于 T 是可以拔出萝卜的。 解可能不是唯一的,你只要随便输出一组就可以。

样例输入1

10 100
3 25 4 91 13 81 64 38 49 51

样例输出1

2
2 4

样例输入2

5 50
3 2 8 5 10

样例输出2

0
Suan4 le ba, hai2 cha4 22.
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;climits&gt; using namespace std; const int INF = 10000; int main() {     int n, T;     cin &gt;&gt; n &gt;&gt; T;     vector&lt;int&gt; powers(n);     long long total = 0;     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; powers[i];         total += powers[i];     }     // 处理总力量不足的情况     if (total &lt; T) {         cout &lt;&lt; "0" &lt;&lt; endl;         cout &lt;&lt; "Suan4 le ba, hai2 cha4 " &lt;&lt; T - total &lt;&lt; "." &lt;&lt; endl;         return 0;     }     // 动态规划数组,dp[j]表示达到力量j所需的最少兔子数     vector&lt;int&gt; dp(T + 1, INF);     // 记录状态转移路径     vector&lt;int&gt; prevState(T + 1, -1);     vector&lt;int&gt; lastId(T + 1, -1);          // 初始状态:0力量需要0只兔子     dp[0] = 0;     // 动态规划过程     for (int i = 0; i &lt; n; i++) {         int w = powers[i];         // 倒序遍历,避免重复计算         for (int j = T; j &gt;= 0; j--) {             if (dp[j] == INF) continue;  // 当前状态不可达                          int next = j + w;             if (next &gt; T) next = T;  // 力量超过T的都视为达到T                          // 更新新状态的最小兔子数             if (dp[next] &gt; dp[j] + 1) {                 dp[next] = dp[j] + 1;                 prevState[next] = j;  // 记录前一个状态                 lastId[next] = i;     // 记录最后加入的兔子索引             }         }     }     // 回溯求解方案     vector&lt;int&gt; selected;     int cur = T;     while (cur &gt; 0) {         selected.push_back(lastId[cur] + 1);  // 转换为1-indexed编号         cur = prevState[cur];     }     sort(selected.begin(), selected.end());     // 输出结果     cout &lt;&lt; dp[T] &lt;&lt; endl;     for (int i = 0; i &lt; selected.size(); i++) {         if (i &gt; 0) cout &lt;&lt; " ";         cout &lt;&lt; selected[i];     }     cout &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
2. 简答题

化学反应式

“化学反应式”是用元素符号表示化学反应的一种等式,等式左边给出参与反应的元素,右边给出反应的结果。例如 CH4+2O2= CO2+ 2H2O 的意思是,参与反应的元素是甲烷和氧气,即 CH4和 O2,反应结果产生二氧化碳和水,即 CO2和 H2O。

现给定一些反应元素和结果,请你编写程序推出我们怎样才能得到这些结果。注意每种反应元素只能被用一次。为简单起见,我们将等式右边的所有元素都当成是一个结果。

时间限制:6000,内存限制:65536

输入

每个输入包含一个测试用例。每个测试用例先给出一个整数 N(2 ≤ N ≤ 20),随后给出 N 个不同的反应元素的编号。

第二行给出一个整数 M(1 ≤ M ≤ 10),随后给出 M 个不同的结果编号。所有编号都是一个 2 位数字。

 随后给出正整数 K(≤ 50),接下来 K 行,每行给出一个化学反应式,格式为: reactant_1 + reactant_2 + ... + reactant_n -> product 其中所有的反应元素(reactant)编号都是不同的,并且按升序排列。 

 注意:题目保证以下规则 

 (1)一套反应元素不会产生多个不同的结果,即诸如 01 + 02 -> 03 且 01 + 02 -> 04 这种情况保证不会出现; 

 (2)一个反应元素不会同时还是等式右边的结果元素,除非等式左边只有这一个元素。例如 01 -> 01 总是成立的(无论这个等式是否给出),但 01 + 02 -> 01 是不可能的; 

 (3)对于列出的等式中的每个结果,得到它的反应方法不会超过 5 种。

输出

输出用给定的反应元素产生所有给定结果的化学反应式。注意每种反应元素只能被用一次。 每个反应式占一行,格式与输入格式相同。顺序必须与输入中的结果编号顺序一致。

对顺序产生的每个结果,如果反应方法不唯一,输出反应元素的最小序列 —— 序列 { a1, … , am} 比 { b1, … , bn} 小的意思是:存在 1 ≤ i ≤ min(m, n) 使得 aj= bj对所有 j < i 成立,且有 ai< bi。 题目保证至少存在一个解。

样例输入

8 09 05 03 04 02 01 16 10
3 08 03 04
6
03 + 09 -> 08
02 + 08 -> 04
02 + 04 -> 03
01 + 05 -> 03
01 + 09 + 16 -> 03
02 + 03 + 05 -> 08

样例输出

02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;set&gt; #include &lt;map&gt; #include &lt;algorithm&gt; #include &lt;sstream&gt; #include &lt;cctype&gt; using namespace std; // 去除字符串前后空格 void trim(string &amp;str) {     if (str.empty()) return;     size_t first = str.find_first_not_of(' ');     size_t last = str.find_last_not_of(' ');     if (first == string::npos) {         str = "";         return;     }     str = str.substr(first, (last - first + 1)); } // 反应式结构体 struct Reaction {     vector&lt;string&gt; reactants; // 反应物列表     string prod;              // 产物     string raw;               // 原始字符串     Reaction(const string&amp; s) : raw(s) {         size_t pos = s.find(" -&gt; ");         if (pos == string::npos) {             return;         }         string leftStr = s.substr(0, pos);         string rightStr = s.substr(pos + 4);         trim(rightStr);         prod = rightStr;         // 解析反应物         stringstream ss(leftStr);         string token;         while (getline(ss, token, '+')) {             trim(token);             if (!token.empty()) {                 reactants.push_back(token);             }         }     } }; int main() {     int n;     cin &gt;&gt; n;     vector&lt;string&gt; initVec;     set&lt;string&gt; availableSet;     for (int i = 0; i &lt; n; i++) {         string x;         cin &gt;&gt; x;         initVec.push_back(x);         availableSet.insert(x);     }     int m;     cin &gt;&gt; m;     vector&lt;string&gt; targets;     set&lt;string&gt; targetSet;     for (int i = 0; i &lt; m; i++) {         string x;         cin &gt;&gt; x;         targets.push_back(x);         targetSet.insert(x);     }     int k;     cin &gt;&gt; k;     cin.ignore(); // 忽略换行符     map&lt;string, vector&lt;Reaction&gt;&gt; reactionsMap;     for (int i = 0; i &lt; k; i++) {         string s;         getline(cin, s);         Reaction reac(s);         if (targetSet.count(reac.prod)) {             reactionsMap[reac.prod].push_back(reac);         }     }     for (string target : targets) {         if (availableSet.find(target) != availableSet.end()) {             cout &lt;&lt; target &lt;&lt; " -&gt; " &lt;&lt; target &lt;&lt; endl;             availableSet.erase(target);         } else {             vector&lt;Reaction&gt;&amp; candidates = reactionsMap[target];             vector&lt;Reaction&gt; validReactions;             for (Reaction&amp; reac : candidates) {                 bool valid = true;                 for (string r : reac.reactants) {                     if (availableSet.find(r) == availableSet.end()) {                         valid = false;                         break;                     }                 }                 if (valid) {                     validReactions.push_back(reac);                 }             }             Reaction best = validReactions[0];             for (int i = 1; i &lt; validReactions.size(); i++) {                 if (validReactions[i].reactants &lt; best.reactants) {                     best = validReactions[i];                 }             }             cout &lt;&lt; best.raw &lt;&lt; endl;             for (string r : best.reactants) {                 availableSet.erase(r);             }         }     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

赛场安排

比赛使用 OMS 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以便发放比赛账号。为了尽可能减少教练和监考的沟通负担,我们要求赛场的安排满足以下条件:

- 每位监考老师负责的赛场里,队员人数不得超过赛场规定容量 C;

- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练,且每个赛场的监考老师都不相同,为此我们设计了多轮次排座算法,按照尚未安排赛场的队员人数从大到小的顺序,每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n;

- 如果 n ≥ C,则将其中 C 人安排到当前为空的编号最小的赛场,剩下的人继续按人数规模排队,等待下一轮处理;

- 如果 n < C,则寻找剩余空位数大于等于 n 的编号最小的赛场,将队员安排进去;

- 如果 n < C,且找不到任何非空的、剩余空位数大于等于 n 的赛场了,则新开一个赛场,将队员安排进去。

由于近年来参赛人数快速增长,2023年超过了 410 所学校 1.6 万人,所以我们必须写个程序来处理赛场安排问题。

时间限制:6000,内存限制:65536

输入

输入第一行给出两个正整数 N 和 C,分别为参赛学校数量和每个赛场的规定容量,其中 0 < N ≤ 5000,10 ≤ C ≤ 50。

随后 N 行,每行给出一个学校的缩写(为长度不超过 6 的非空小写英文字母串)和该校参赛人数(不超过 500 的正整数),其间以空格分隔。题目保证每所学校只有一条记录。

输出

按照输入的顺序,对每一所参赛高校,在一行中输出学校缩写和该校需要联系的监考人数,其间以 1 空格分隔。 最后在一行中输出系统中应该开设多少个赛场。

样例输入

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

样例输出

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;algorithm&gt; #include &lt;cctype&gt; #include &lt;string&gt; using namespace std; struct School {     string name;     int total;     int remaining;     int supervisors;     School(string n, int t) : name(n), total(t), remaining(t), supervisors(0) {} }; int main() {     int N, C;     cin &gt;&gt; N &gt;&gt; C;     vector&lt;School&gt; schools;     for (int i = 0; i &lt; N; i++) {         string name;         int num;         cin &gt;&gt; name &gt;&gt; num;         schools.push_back(School(name, num));     }     auto cmp = [](const pair&lt;int, int&gt;&amp; a, const pair&lt;int, int&gt;&amp; b) {         if (a.first != b.first)              return a.first &lt; b.first;         else              return a.second &gt; b.second;     };     priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, decltype(cmp)&gt; pq(cmp);     for (int i = 0; i &lt; schools.size(); i++) {         pq.push({schools[i].remaining, i});     }     int totalRooms = 0;     vector&lt;set&lt;int&gt;&gt; buckets(51);     while (!pq.empty()) {         int remaining = pq.top().first;         int idx = pq.top().second;         pq.pop();         if (remaining &gt; schools[idx].remaining) {             continue;         }         if (remaining &gt;= C) {             totalRooms++;             schools[idx].supervisors++;             schools[idx].remaining -= C;             if (schools[idx].remaining &gt; 0) {                 pq.push({schools[idx].remaining, idx});             }         } else {             bool found = false;             for (int r = remaining; r &lt;= 50; r++) {                 if (!buckets[r].empty()) {                     found = true;                     int room_id = *buckets[r].begin();                     buckets[r].erase(room_id);                     int new_r = r - remaining;                     if (new_r &gt; 0) {                         buckets[new_r].insert(room_id);                     }                     schools[idx].supervisors++;                     break;                 }             }             if (!found) {                 totalRooms++;                 schools[idx].supervisors++;                 int new_r = C - remaining;                 if (new_r &gt; 0) {                     buckets[new_r].insert(totalRooms - 1);                 }             }         }     }     for (int i = 0; i &lt; N; i++) {         cout &lt;&lt; schools[i].name &lt;&lt; " " &lt;&lt; schools[i].supervisors &lt;&lt; endl;     }     cout &lt;&lt; totalRooms &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
4. 简答题

买还是不买

小红想用自己喜欢的彩色珠子做一条珠串,于是去一家小店买珠子。店里有很多条彩色的珠串,但店主只卖整串,不拆散零售珠子。于是小红为了得到自己喜欢颜色的珠子,就得买很多条现成的珠串,回家拆了自己拼。

由于店里有上百条珠串,小红只好求助于你,请你写个程序,帮她看看是否有可能买到所有她喜欢颜色的珠子,并且使得多余的珠子尽可能少。

为简单起见,我们用数字 0 到 9、以及英文的 26 个字母的大小写来表示珠子的颜色(即珠子最多有 62 种颜色)。

在样例 1 中,买第 2 条和最后两条珠串是最划算的,因为这样只有 3 颗珠子是多余的。

在样例 2 中,把全部三条珠串都买下也不行,因为还少三颗 R 珠。

时间限制:9000,内存限制:65536

输入

输入第一行给出小红想要的珠串。下一行给出正整数 N(≤ 100),随后 N 行,每行给出店里的一条珠串。所有珠串中的珠子不超过 1000 颗。

输出

如果能凑出小红想要的珠串,则在一行中输出 Yes、空格、最少的多余珠子的个数;否则输出 No、空格、凑不出来的珠子的个数。

样例输入1

RYg5
8
gY5Ybf
8R5
12346789
gRg8h
5Y37
pRgYgbR52
8Y
8g

样例输出1

Yes 3

样例输入2

YrRR8RRrY
3
ppRGrrYB225
8ppGrrB25
Zd6KrY

样例输出2

No 3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;climits&gt; using namespace std; const int MAX_COLOR = 62; int getIndex(char c) {     if (c &gt;= '0' &amp;&amp; c &lt;= '9')         return c - '0';     else if (c &gt;= 'A' &amp;&amp; c &lt;= 'Z')         return 10 + (c - 'A');     else if (c &gt;= 'a' &amp;&amp; c &lt;= 'z')         return 36 + (c - 'a');     return -1; } struct Bead {     int len;     vector&lt;int&gt; cnt;     string s;     Bead(string str) : s(str), len(str.size()), cnt(MAX_COLOR, 0) {         for (char c : str) {             int idx = getIndex(c);             if (idx != -1) {                 cnt[idx]++;             }         }     } }; vector&lt;Bead&gt; beads; vector&lt;int&gt; target(MAX_COLOR, 0); vector&lt;int&gt; total(MAX_COLOR, 0); vector&lt;vector&lt;int&gt;&gt; suffix; int best = INT_MAX; int total_target = 0; int N; void dfs(int idx, vector&lt;int&gt; need, int cur_len) {     if (cur_len &gt;= best) {         return;     }     int sum_need = 0;     bool all_zero = true;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (need[c] &gt; 0) {             all_zero = false;             sum_need += need[c];         }     }     if (all_zero) {         best = cur_len;         return;     }     if (idx &gt;= N) {         return;     }     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (need[c] &gt; suffix[idx][c]) {             return;         }     }     if (cur_len + sum_need &gt;= best) {         return;     }     dfs(idx + 1, need, cur_len);     bool useful = false;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (beads[idx].cnt[c] &gt; 0 &amp;&amp; need[c] &gt; 0) {             useful = true;             break;         }     }     if (useful) {         vector&lt;int&gt; new_need = need;         for (int c = 0; c &lt; MAX_COLOR; c++) {             if (new_need[c] &gt; 0) {                 new_need[c] = max(0, new_need[c] - beads[idx].cnt[c]);             }         }         dfs(idx + 1, new_need, cur_len + beads[idx].len);     } } int main() {     string target_str;     getline(cin, target_str);     total_target = target_str.size();     for (char c : target_str) {         int idx = getIndex(c);         if (idx != -1) {             target[idx]++;         }     }     cin &gt;&gt; N;     cin.ignore();     beads.reserve(N);     for (int i = 0; i &lt; N; i++) {         string s;         getline(cin, s);         beads.push_back(Bead(s));     }     for (int i = 0; i &lt; MAX_COLOR; i++) {         total[i] = 0;     }     for (int i = 0; i &lt; N; i++) {         for (int c = 0; c &lt; MAX_COLOR; c++) {             total[c] += beads[i].cnt[c];         }     }     int shortage = 0;     bool overall_meet = true;     for (int c = 0; c &lt; MAX_COLOR; c++) {         if (target[c] &gt; total[c]) {             overall_meet = false;             shortage += (target[c] - total[c]);         }     }     if (!overall_meet) {         cout &lt;&lt; "No " &lt;&lt; shortage &lt;&lt; endl;         return 0;     }     sort(beads.begin(), beads.end(), [](const Bead&amp; a, const Bead&amp; b) {         return a.len &lt; b.len;     });     suffix.resize(N, vector&lt;int&gt;(MAX_COLOR, 0));     for (int c = 0; c &lt; MAX_COLOR; c++) {         suffix[N - 1][c] = beads[N - 1].cnt[c];     }     for (int i = N - 2; i &gt;= 0; i--) {         for (int c = 0; c &lt; MAX_COLOR; c++) {             suffix[i][c] = beads[i].cnt[c] + suffix[i + 1][c];         }     }     best = INT_MAX;     dfs(0, target, 0);     cout &lt;&lt; "Yes " &lt;&lt; best - total_target &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。