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

青少年软件编程(C/C++)4级等级考试真题试卷(2024年9月) VIP

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

一、简答题

1. 简答题

有几个PAT

字符串 APPAPT 中包含了两个单词 PAT,其中第一个 PAT 是第 2 位(P),第 4 位(A),第 6 位(T);第二个 PAT 是第 3 位(P),第 4 位(A),第 6 位(T)。

现给定字符串,问一共可以形成多少个 PAT?

时间限制:1000

内存限制:262144

输入

输入只有一行,包含一个字符串,长度不超过105,只包含 P、A、T 三种字母。

输出

在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大,只输出对 1000000007 取余数的结果。


样例输入

APPAPT

样例输出

2
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;string&gt; using namespace std; int main() {     long long sum = 0;     string list;     getline(cin, list);     for (int i = 0,p=0,a=0; i &lt; list.size(); ++i)     {         if (list[i] == 'P')         {             ++p;         }         if (list[i] == 'A')         {             a += p;         }         if (list[i] == 'T')         {             sum += a;         }        }     sum %= 1000000007;     cout &lt;&lt; sum &lt;&lt; endl;     system("pause");     return 0; }</pre>
这道题暂未补解析。
2. 简答题

彩带

织女要织一条自己最爱的彩带,方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色,裁掉不要的部分,把留下的缝制在一起,就制成了她最喜欢的彩带。

一般肉眼能分辨的颜色不超过 200 种,所以织女的彩带颜色是有限的。但原始的彩带可是非常长,并且织女想最后形成的彩带也尽可能长,所以她需要你的帮助来得到一个最佳的结果。

注意到解可能是不唯一的,但你只需要告诉她结果的长度即可。例如,给定原始的彩带为 { 2 2 4 1 5 5 6 3 1 1 5 6 },其中数字代表颜色的编号。如果织女喜欢的颜色和顺序是 { 2 3 1 5 6 },则她可以得到 4 个不同的最优解:{ 2 2 1 1 1 5 6 }、{ 2 2 1 5 5 5 6 }、{ 2 2 1 5 5 6 6 } 和 { 2 2 3 1 1 5 6 },长度都是 7。

时间限制:1000

内存限制:262144

输入

输入第一行给出一个正整数 N(≤ 200),为颜色种类的数量(即颜色从 1 到 N 编号)。下一行先给出一个正整数 M(≤ 200),随后是织女喜欢的 M个颜色,按她喜欢的顺序给出。第三行也是先给出一个正整数 L(≤ 104),即原始彩带的长度,随后是 L 个颜色值。一行中的所有数字以空格分隔。

输出

只需要输出织女最喜欢的彩带的最大长度值。


样例输入

6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6

样例输出

7
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_map&gt; using namespace std; int main() {     int N, M, L;     cin &gt;&gt; N; // 颜色总数,此处可忽略     // 读取织女喜欢的颜色序列     cin &gt;&gt; M;     vector&lt;int&gt; favorite(M);     for (int i = 0; i &lt; M; ++i) {         cin &gt;&gt; favorite[i];     }     // 建立颜色到位置的映射,记录每个颜色最后出现的位置     unordered_map&lt;int, int&gt; colorToPos;     for (int i = 0; i &lt; M; ++i) {         colorToPos[favorite[i]] = i + 1; // 位置从1开始     }     // 读取原始彩带并转换为有效的位置列表     cin &gt;&gt; L;     vector&lt;int&gt; positions;     for (int i = 0; i &lt; L; ++i) {         int color;         cin &gt;&gt; color;         if (colorToPos.count(color)) {             positions.push_back(colorToPos[color]);         }     }     // 动态规划处理     vector&lt;int&gt; currentMax(M + 1, 0); // currentMax[i]表示以位置i结尾的最长子序列长度     vector&lt;int&gt; prefixMax(M + 1, 0);  // prefixMax[i]表示前i个位置的最大长度     for (int p : positions) {         int newLen = prefixMax[p] + 1;         if (newLen &gt; currentMax[p]) {             currentMax[p] = newLen;             // 更新prefixMax数组             for (int i = 1; i &lt;= M; ++i) {                 if (i == 1) {                     prefixMax[i] = currentMax[i];                 } else {                     prefixMax[i] = max(prefixMax[i - 1], currentMax[i]);                 }             }         }     }     cout &lt;&lt; prefixMax[M] &lt;&lt; endl;     return 0; }</pre><p><br/></p>
解析:

方法思路:

预处理织女喜欢的颜色序列:建立一个颜色到位置的映射,记录每个颜色在织女喜欢的序列中最后出现的位置。

过滤原始彩带:将原始彩带中的颜色转换为对应的位置,过滤掉不在织女喜欢的颜色序列中的颜色。

动态规划:维护两个数组,current_max 和 prefix_max。current_max 数组记录以每个位置结尾的最长子序列长度,prefix_max 数组记录前缀最大值。遍历处理后的位置列表,更新这两个数组,最终得到最长子序列的长度。


3. 简答题

最长峰形线

在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”,是指 L 个数字组成的有序序列 { D1, …, DL },满足条件:存在下标 i(1 < i < L)使得 D1 < … < Di-1 < Di > Di+1 > … > DL。

顺次给出 n 个数字,你可以从中删掉部分数字,使得剩下的数字能构成峰形线。要求构造出来的峰形线是最长的。当最长峰形线不唯一时,你要输出最对称(即升序和降序两部分长度之差为最小)的那条。

时间限制:7000

内存限制:262144

输入

输入第一行给出一个正个整数 n (3 ≤ n ≤ 104),随后一行给出 n 个在区间 [-10000, 10000] 内的整数,以空格分隔。

输出

首先在一行中输出最长峰形线的长度、峰顶数字的序号(从 1 开始)和它的值,数字间以 1 个空格分隔。如果解不存在,则在一行中输出 `No peak shape`。裁判数据保证输出是唯一的。


样例输入

样例#1:

20

1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1

样例#2:

5

-1 3 8 10 20

样例输出

样例#1:

10 14 25

样例#2:

No peak shape

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;climits&gt; using namespace std;   int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; arr(n);     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; arr[i];     }       if (n &lt; 3) {         cout &lt;&lt; "No peak shape" &lt;&lt; endl;         return 0;     }       // LIS dp (Longest Increasing Subsequence from the left)     vector&lt;int&gt; lis(n, 1);  // lis[i] 表示以 arr[i] 为结尾的最长上升子序列长度     for (int i = 0; i &lt; n; i++) {         for (int j = 0; j &lt; i; j++) {             if (arr[i] &gt; arr[j]) {                 lis[i] = max(lis[i], lis[j] + 1);             }         }     }       // LDS dp (Longest Decreasing Subsequence from the right)     vector&lt;int&gt; lds(n, 1);  // lds[i] 表示以 arr[i] 为开始的最长下降子序列长度     for (int i = n - 1; i &gt;= 0; i--) {         for (int j = n - 1; j &gt; i; j--) {             if (arr[i] &gt; arr[j]) {                 lds[i] = max(lds[i], lds[j] + 1);             }         }     }       int maxLength = 0;     int bestIndex = -1;     int bestValue = INT_MIN;     int bestDiff = INT_MAX;       // 查找峰形线     for (int i = 1; i &lt; n - 1; i++) {         // 如果 arr[i] 是峰顶         if (lis[i] &gt; 1 &amp;&amp; lds[i] &gt; 1) {             int length = lis[i] + lds[i] - 1;  // 总长度             int diff = abs(lis[i] - lds[i]);   // 升降长度差               if (length &gt; maxLength || (length == maxLength &amp;&amp; diff &lt; bestDiff)) {                 maxLength = length;                 bestIndex = i;                 bestValue = arr[i];                 bestDiff = diff;             }         }     }       // 输出结果     if (maxLength == 0) {         cout &lt;&lt; "No peak shape" &lt;&lt; endl;     } else {         cout &lt;&lt; maxLength &lt;&lt; " " &lt;&lt; bestIndex + 1 &lt;&lt; " " &lt;&lt; bestValue &lt;&lt; endl;     }       return 0; }</pre>
这道题暂未补解析。
4. 简答题

红蓝串

小红有两条珠串,一条有 A 只红色珠子,另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串:

- 她会从两条珠串上一步一步地取下珠子。

- 第 i 步时,她会从一条珠串上取下 i 颗珠子,穿到结果串上。

- 她最后要得到一条有 n 颗珠子的串。

小红有可能得到多少种不同的结果呢?

如果小红在至少某一步中选择了不同颜色的串来取珠子,那么两条结果串就被认为是不同的。

时间限制:6000

内存限制:262144

输入

输入在一行中给出 3 个整数:n (0 < n ≤ 2 × 105)、A、B (0≤ A, B ≤ 105),其定义如题面所述。

输出

在一行中输出小红有可能得到多少条有 n 颗珠子的串。因为结果可能是很大的数字,所以你要输出对 1000000007 (109 + 7) 取模后的结果。


样例输入

10 4 7

样例输出

4

提示

小红能得到的 4 种不同的结果如下图所示。 

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include <iostream> #include <vector> #include <cmath> using namespace std; const int MOD = 1000000007; int main() {     long long n, A, B;     cin >> n >> A >> B;          long long D = 8 * n + 1;     long long m = sqrt(D);     if (m * m != D || m % 2 == 0) {         cout << 0 << endl;         return 0;     }     long long k = (m - 1) / 2;          long long low = max(n - B, 0LL);     long long high = min(A, n);          if (low > high) {         cout << 0 << endl;         return 0;     }          vector<long long> dp(n + 1, 0);     dp[0] = 1;     for (int i = 1; i <= k; ++i) {         for (int s = n; s >= i; --s) {             dp[s] = (dp[s] + dp[s - i]) % MOD;         }     }          long long ans = 0;     for (int s = low; s <= high; ++s) {         ans = (ans + dp[s]) % MOD;     }          cout << ans << endl;     return 0; }</pre>
这道题暂未补解析。