首页 › 试卷 › C/C++编程考级 › C/C++编程四级 › 2025年3月电子学会青少年软件编程(C/C++)4级等级考试真题试卷

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

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

一、简答题

1. 简答题

两枚硬币

伊娃喜欢收集全宇宙的硬币,包括火星币等等。一天她到了一家宇宙商店,这家商店可以接受任何星球的货币,但有一个条件,无论什么价格,都必须用 2 枚硬币一次付清,不能多也不能少。而她有多达 105 个硬币,于是求助于你。给定任一价格,请帮她找出可以付款的 2 枚硬币。

时间限制:1000

内存限制:65536

输入

第 1 行给出 2 个正整数:n (≤ 105)为硬币枚数、m(≤ 103)为伊娃要付清的价格; 第 2 行给出 n 枚硬币的面值,均为不超过 500 的正整数。同行数字间以空格分隔。

输出

在一行中输出两枚硬币的面值 v1 和 v2 ,以 1 个空格分隔,满足条件 v1+v2=m,并且 v1 ≤ v2。如果这样的解不唯一,输出 v1 最小的那个解。如果解不存在,则输出 `No Solution`。


样例输入

样例#1:

8 15
1 2 8 7 2 4 11 15

样例#2:

7 14
1 8 7 2 4 11 15

样例输出

样例#1:

4 11

样例#2:

No Solution
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int main() {     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;int&gt; coins(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; coins[i];     }     if (n &lt; 2) {         cout &lt;&lt; "No Solution" &lt;&lt; endl;         return 0;     }     sort(coins.begin(), coins.end());     int left = 0, right = n - 1;     while (left &lt; right) {         int sum = coins[left] + coins[right];         if (sum == m) {             cout &lt;&lt; coins[left] &lt;&lt; " " &lt;&lt; coins[right] &lt;&lt; endl;             return 0;         } else if (sum &lt; m) {             ++left;         } else {             --right;         }     }     cout &lt;&lt; "No Solution" &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
2. 简答题

完美数列

给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

时间限制:1000

内存限制:65536

输入

输入第一行给出两个正整数 n 和 p,其中 n(≤ 105)是输入的正整数的个数,p(≤ 109)是给定的参数。第二行给出 n 个正整数,每个数不超过 109。

输出

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。


样例输入

10 8
2 3 20 4 5 1 6 7 8 9

样例输出

8
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int main() {     int n, p;     cin &gt;&gt; n &gt;&gt; p;     vector&lt;int&gt; nums(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; nums[i];     }     sort(nums.begin(), nums.end());     int max_len = 0;     for (int i = 0; i &lt; n; ++i) {         long long target = (long long)nums[i] * p;         auto it = upper_bound(nums.begin() + i, nums.end(), target);         int cnt = it - (nums.begin() + i);         if (cnt &gt; max_len) {             max_len = cnt;         }     }     cout &lt;&lt; max_len &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
3. 简答题

多样解码

将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`,也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的,不能被解码为 `H`。

本题就请你计算一下,给定的数字串有多少种不同的解码结果。

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个不超过 104 位的数字串,串非空且不包含空格。

输出

输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大,你只需要输出其对 1000000007 取模后的结果。


样例输入

1213407

样例输出

5
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1000000007; int main() { string s; cin &gt;&gt; s; int n = s.size(); vector&lt;long long&gt; dp(n + 1, 0); dp[0] = 1; // 空字符串有一种解码方式 for (int i = 1; i &lt;= n; ++i) { // 单独处理当前字符,总是允许 dp[i] = dp[i-1]; // 处理两位的情况 if (i &gt;= 2) { // 提取前两位字符并转换为整数 int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0'); if (two_digit &gt;= 10 &amp;&amp; two_digit &lt;= 25) { dp[i] += dp[i-2]; } } dp[i] %= MOD; } cout &lt;&lt; dp[n] % MOD &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。
4. 简答题

二进制串的评分

对于一个给定的二进制串 s(即仅由字符 0 和 1 组成的串),其评分是这样计算的:将原串切分为若干段,使得每段包含的字符是一样的,且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值(如果只有一段,评分就是这段的长度)。

异或(Exclusive OR,简称 XOR)是一种数学运算符,用于计算机中的位运算。当且仅当两个输入值不同时,异或运算输出为真(1),否则输出为假(0)。

例如,串 "10001100001" 可以切分为 5 段,即 "1"、"000"、"11"、"0000"、"1",其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。

假设每一步我们可以交换 2 个相邻的字符,并且可以这样执行任意多步(当然也可以执行 0 步)。对每个可能的评分 x,你能得到多少个不同的串?将原串 s 通过交换操作变成评分为 x 的串,所用的最少步骤是多少次?

时间限制:1000

内存限制:65536

输入

输入在一行中给出非空的原始二进制串 s,其长度不超过 64。

输出

对每个可能的评分,在一行中输出 3 个空格分隔的整数,依次为:评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。


样例输入

010

样例输出

1 1 0
3 2 1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;unordered_map&gt; #include &lt;queue&gt; // 计算二进制串的评分 int calcScore(const std::string&amp; s) {     int score = 0, count = 1;     for (int i = 1; i &lt;= s.size(); ++i) {         if (i == s.size() || s[i] != s[i - 1]) {             score ^= count;             count = 1;         } else {             ++count;         }     }     return score; } // 广度优先搜索 void bfs(const std::string&amp; start, std::unordered_map&lt;int, std::pair&lt;int, int&gt;&gt;&amp; res) {     std::unordered_map&lt;std::string, int&gt; minSteps;     std::queue&lt;std::string&gt; q;     q.push(start);     minSteps[start] = 0;     while (!q.empty()) {         std::string s = q.front();         q.pop();         int score = calcScore(s);         int steps = minSteps[s];         if (res.find(score) == res.end()) {             res[score] = {1, steps};         } else {             res[score].first++;             res[score].second = std::min(res[score].second, steps);         }         for (int i = 0; i &lt; s.size() - 1; ++i) {             std::string newStr = s;             std::swap(newStr[i], newStr[i + 1]);             if (minSteps.find(newStr) == minSteps.end()) {                 minSteps[newStr] = steps + 1;                 q.push(newStr);             }         }     } } int main() {     std::string s;     std::cin &gt;&gt; s;     std::unordered_map&lt;int, std::pair&lt;int, int&gt;&gt; res;     bfs(s, res);     std::vector&lt;int&gt; scores;     for (const auto&amp; p : res) {         scores.push_back(p.first);     }     std::sort(scores.begin(), scores.end());     for (int score : scores) {         std::cout &lt;&lt; score &lt;&lt; " " &lt;&lt; res[score].first &lt;&lt; " " &lt;&lt; res[score].second &lt;&lt; std::endl;     }     return 0; }</pre>
这道题暂未补解析。