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

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

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

一、简答题

1. 简答题

兔子不吃窝边草

有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?

时间限制:10000

内存限制:65536

输入

输入第一行给出两个正整数,即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103),以空格分隔,依次表示每块草皮的含草量。

输出

首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔,行首尾不得有多余空格。 注意:我们必须假设兔子只朝一个方向跳着吃草,否则如果它可以来回跳,就能吃掉所有的草了。如果朝左右两个方向得到的结果一样,则兔子总是喜欢向左边跳;并且如果有多块草皮都可以得到同样的结果,兔子总是选择跳到离自己最近的那块。


样例输入

样例1:

10 4
2 1 4 3 1 1 5 2 3 1

样例2:

10 8
2 1 4 3 1 1 5 2 3 1


样例输出

样例1:

11
4 7 9

样例2:

9
8 6 3 1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; pair&lt;int, vector&lt;int&gt;&gt; solve_dp(const vector&lt;int&gt;&amp; vals) { int n = vals.size(); if (n == 0) return {0, {}}; vector&lt;int&gt; dp(n, 0); dp[0] = vals[0]; if (n &gt;= 1) { dp[1] = max(vals[0], vals[1]); } for (int j = 2; j &lt; n; ++j) { dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]); } vector&lt;int&gt; selected; int j = n - 1; while (j &gt;= 0) { if (j == 0) { selected.push_back(j); break; } if (dp[j] == dp[j - 1]) { --j; } else { selected.push_back(j); j -= 2; } } reverse(selected.begin(), selected.end()); return {dp.back(), selected}; } int main() { int N, i; cin &gt;&gt; N &gt;&gt; i; vector&lt;int&gt; arr(N); for (int j = 0; j &lt; N; ++j) { cin &gt;&gt; arr[j]; } vector&lt;int&gt; left_pos, left_vals; for (int pos = i - 2; pos &gt;= 1; --pos) { left_pos.push_back(pos); left_vals.push_back(arr[pos - 1]); } auto [left_sum, left_idx] = solve_dp(left_vals); int total_left = arr[i - 1] + left_sum; vector&lt;int&gt; left_path; for (int idx : left_idx) { left_path.push_back(left_pos[idx]); } vector&lt;int&gt; right_pos, right_vals; for (int pos = i + 2; pos &lt;= N; ++pos) { right_pos.push_back(pos); right_vals.push_back(arr[pos - 1]); } auto [right_sum, right_idx] = solve_dp(right_vals); int total_right = arr[i - 1] + right_sum; vector&lt;int&gt; right_path; for (int idx : right_idx) { right_path.push_back(right_pos[idx]); } bool choose_left = false; if (total_left &gt; total_right) { choose_left = true; } else if (total_left == total_right) { choose_left = true; } else { choose_left = false; } vector&lt;int&gt; path; path.push_back(i); if (choose_left) { for (int pos : left_path) { path.push_back(pos); } } else { for (int pos : right_path) { path.push_back(pos); } } cout &lt;&lt; (choose_left ? total_left : total_right) &lt;&lt; endl; for (size_t k = 0; k &lt; path.size(); ++k) { if (k &gt; 0) cout &lt;&lt; " "; cout &lt;&lt; path[k]; } cout &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。
2. 简答题

漂亮的序列

对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中,有多少个子序列是漂亮的。

时间限制:6000

内存限制:65536

输入

输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103),随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。

输出

输出原始序列中漂亮子序列的个数。因为答案可能非常大,所以你需要输出对 1000000007 (109 + 7) 取模后的结果。


样例输入

4 2
5 3 8 6

样例输出

8

提示

样例解释:

1、子序列下标为 {1, 2}, 对应值为 {5, 3};

2、子序列下标为 {1, 4}, 对应值为 {5, 6};

3、子序列下标为 {3, 4}, 对应值为 {8, 6};

4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8};

5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6};

6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6};

7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6};

8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。

查看答案与解析
答案:<p>参考代码<br/></p><pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MOD = 1000000007; class FenwickTree { private:     vector&lt;int&gt; tree;     int n; public:     FenwickTree(int size) : n(size) {         tree.assign(n + 2, 0); // 索引从1到n+1     }     void update(int idx, int val) {         idx++; // 树状数组从1开始         if (idx &gt; n) return; // 超出范围的不处理         while (idx &lt;= n) {             tree[idx] = (tree[idx] + val) % MOD;             idx += idx &amp; -idx;         }     }     int query(int idx) {         idx++; // 转换为树状数组的索引         if (idx &lt; 0) return 0;         int res = 0;         while (idx &gt; 0) {             res = (res + tree[idx]) % MOD;             idx -= idx &amp; -idx;         }         return res;     } }; int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;int&gt; a(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; a[i];     }     int max_a = *max_element(a.begin(), a.end());     int max_val = max_a + m;     FenwickTree bit(max_val);     long long sum_dp = 0;     int total_sum = 0;     for (int ai : a) {         int left = ai - m - 1;         int sum_left = bit.query(left);         int right = ai + m;         int sum_right = (total_sum - bit.query(right) + MOD) % MOD;         int dp_i = (sum_left + sum_right + 1) % MOD;         sum_dp = (sum_dp + dp_i) % MOD;         bit.update(ai, dp_i);         total_sum = (total_sum + dp_i) % MOD;     }     long long S = (sum_dp - n + MOD) % MOD;     // 计算2^n mod MOD     auto powmod = [](long long a, int b, int mod) {         long long res = 1;         while (b &gt; 0) {             if (b &amp; 1) res = res * a % mod;             a = a * a % mod;             b &gt;&gt;= 1;         }         return res;     };     long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;     long long ans = (T - S + MOD) % MOD;     cout &lt;&lt; ans &lt;&lt; '\n';     return 0; }</pre>
这道题暂未补解析。
3. 简答题

园林修整

园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。

时间限制:10000

内存限制:65536

输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000),随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内,同行数字间以空格分隔。

输出

首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号(从 1 开始)。如果解不唯一,输出那个需要最少替换树木的解,题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔,行首尾不得有多余空格。 如果没有树需要调整,则根据树高的升降性质,在一行中输出 Non-ascending(表示“非递增”)或 Non-descending(表示非递减)。


样例输入

样例1:

10
2 3 8 2 4 5 10 1 7 11

样例2:

3
1 2 3


样例输出

样例1:

4
2 3 7 8

样例2:

Non-descending

提示

样例1解释: 

首先,要将树木修整成按高度非递减的样式,我们需要调整 4 棵树;而要修整成非递增样式,则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次,存在 4 种不同的递增序列解:

1、保持树高为 2、3、4、5、10、11 的树不变,我们需要替换掉高度为 2、1、7 的 3 棵树,因为它们太矮了;

2、保持树高为 2、3、4、5、7、11 的树不变,我们需要替换掉高度为 2、1 的 2 棵树;

3、保持树高为 2、2、4、5、10、11 的树不变,我们需要替换掉高度为 1、7 的 2 棵树;

4、保持树高为 2、2、4、5、7、11 的树不变,我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解,即裁剪编号为 2、3、7(对应高度为 3、8、10)的树,替换掉第 8 棵高度为 1 的树。

查看答案与解析
答案:<p>参考代码:<br/></p><pre class="brush:cpp;toolbar:false">#include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;set&gt; using namespace std; struct Result {     int changes;     int replaces;     vector&lt;int&gt; removed; }; Result processDirection(const vector&lt;int&gt;&amp; a, bool nonDecreasing) {     int n = a.size();     vector&lt;int&gt; dp(n, 1);     vector&lt;int&gt; prev(n, -1);     for (int i = 0; i &lt; n; ++i) {         for (int j = 0; j &lt; i; ++j) {             bool valid = nonDecreasing ? (a[j] &lt;= a[i]) : (a[j] &gt;= a[i]);             if (valid &amp;&amp; dp[j] + 1 &gt; dp[i]) {                 dp[i] = dp[j] + 1;                 prev[i] = j;             }         }     }     int maxLen = *max_element(dp.begin(), dp.end());     vector&lt;int&gt; candidates;     for (int i = 0; i &lt; n; ++i) {         if (dp[i] == maxLen) {             candidates.push_back(i);         }     }     int bestReplace = 1e9;     vector&lt;int&gt; bestIndices;     for (int candidate : candidates) {         vector&lt;int&gt; path;         int current = candidate;         while (current != -1) {             path.push_back(current);             current = prev[current];         }         reverse(path.begin(), path.end());         set&lt;int&gt; pathSet(path.begin(), path.end());         vector&lt;int&gt; sortedPath(path.begin(), path.end());         sort(sortedPath.begin(), sortedPath.end());         int replace = 0;         for (int k = 0; k &lt; n; ++k) {             if (pathSet.count(k)) continue;             auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);             if (it != sortedPath.begin()) {                 int leftIdx = *(--it);                 if (a[k] &lt; a[leftIdx]) {                     replace++;                 }             }         }         if (replace &lt; bestReplace || (replace == bestReplace &amp;&amp; path.size() &gt; bestIndices.size())) {             bestReplace = replace;             bestIndices = sortedPath;         }     }     set&lt;int&gt; reserved(bestIndices.begin(), bestIndices.end());     vector&lt;int&gt; removed;     for (int i = 0; i &lt; n; ++i) {         if (!reserved.count(i)) {             removed.push_back(i + 1);         }     }     sort(removed.begin(), removed.end());     return { n - maxLen, bestReplace, removed }; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     int N;     cin &gt;&gt; N;     vector&lt;int&gt; a(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; a[i];     }     bool isNonDescending = true;     for (int i = 1; i &lt; N; ++i) {         if (a[i] &lt; a[i-1]) {             isNonDescending = false;             break;         }     }     if (isNonDescending) {         cout &lt;&lt; "Non-descending\n";         return 0;     }     bool isNonAscending = true;     for (int i = 1; i &lt; N; ++i) {         if (a[i] &gt; a[i-1]) {             isNonAscending = false;             break;         }     }     if (isNonAscending) {         cout &lt;&lt; "Non-ascending\n";         return 0;     }     Result asc = processDirection(a, true);     Result desc = processDirection(a, false);     bool useAsc;     if (asc.changes &lt; desc.changes) {         useAsc = true;     } else if (asc.changes &gt; desc.changes) {         useAsc = false;     } else {         useAsc = (asc.replaces &lt;= desc.replaces);     }     Result res = useAsc ? asc : desc;     cout &lt;&lt; res.changes &lt;&lt; '\n';     for (size_t i = 0; i &lt; res.removed.size(); ++i) {         if (i &gt; 0) cout &lt;&lt; ' ';         cout &lt;&lt; res.removed[i];     }     cout &lt;&lt; '\n';     return 0; }</pre>
这道题暂未补解析。
4. 简答题

字母游戏

一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的字母重排顺序就可以得到 T。游戏的每一步,我们可以将 S 中的任一字母移动到串头或串尾,问将 S 变换成 T 至少需要多少步?

时间限制:6000

内存限制:65536

输入

输入分两行,先后给出字母串 S 和 T。如题面所描述的,两者包含同样的小写英文字母,只是顺序不同。每个字母串的长度不超过 1000。

输出

在一行中输出将 S 变换成 T 至少需要的步骤数。


样例输入

iononmrogdg
goodmorning

样例输出

8

提示

样例解释:

1、 从 iononmrogdg 开始;

2、 将最后一个 g 移动到串头: giononmrogd;

3、 将 m 移动到串尾: giononrogdm;

4、 将第一个 o 移动到串尾: ginonrogdmo;

5、 将 r 移动到串尾: ginonogdmor;

6、 将第一个 n 移动到串尾: gionogdmorn;

7、 将 i 移动到串尾: gonogdmorni;

8、 将第一个 n 移动到串尾: googdmornin;

9、 将第二个 g 移动到串尾: goodmorning。

查看答案与解析
答案:<p>参考代码</p><pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int main() {     string s, t;     cin &gt;&gt; s &gt;&gt; t;     int n = s.size();          unordered_map&lt;char, vector&lt;int&gt;&gt; pos_map;     for (int i = 0; i &lt; n; ++i) {         pos_map[s[i]].push_back(i);     }          int max_len = 0;     for (int i = 0; i &lt; n; ++i) {         int current_pos = -1;         int count = 0;         for (int j = i; j &lt; n; ++j) {             char c = t[j];             if (pos_map.find(c) == pos_map.end()) {                 break;             }             vector&lt;int&gt;&amp; v = pos_map[c];             auto it = upper_bound(v.begin(), v.end(), current_pos);             if (it == v.end()) {                 break;             }             current_pos = *it;             count++;         }         if (count &gt; max_len) {             max_len = count;         }     }          cout &lt;&lt; n - max_len &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。