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

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

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

一、简答题

1. 简答题

拯救007

在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去!(据说当年替身演员被最后一条鳄鱼咬住了脚,幸好穿的是特别加厚的靴子才逃过一劫。)

设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。

时间限制:6000

内存限制:262144

输入

首先第一行给出两个正整数:鳄鱼数量 N(≤ 100)和007一次能跳跃的最大距离 D。随后 N 行,每行给出一条鳄鱼的 (x, y) 坐标。注意:不会有两条鳄鱼待在同一个点上。

输出

如果007有可能逃脱,就在一行中输出"Yes",否则输出"No"。

样例输入

样例#1:

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

样例#2:

4 13
-12 12
12 12
-12 -12
12 -12

样例输出

样例#1:

Yes

样例#2:

No
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; using namespace std;   const int N = 110;   struct Node { int x, y; }; Node v[N];   int n, d; bool st[N], flag = false;   vector&lt;int&gt; firststep;   bool check(int a, int b) { int dx, dy; dx = pow(v[a].x - v[b].x, 2); dy = pow(v[a].y - v[b].y, 2); if (dx + dy &lt;= d * d) return true; return false; }   void DFS(int x) {   st[x] = true;   if (v[x].x - d &lt;= -50 || v[x].x + d &gt;= 50 || v[x].y - d &lt;= -50 || v[x].y + d &gt;= 50) { flag = true; return; }   for (int i = 0; i &lt; n; i++) { if (!st[i] &amp;&amp; check(x, i)) DFS(i); }   }   int main() {   cin &gt;&gt; n &gt;&gt; d;   for (int i = 0; i &lt; n; i++) {   int a, b; cin &gt;&gt; a &gt;&gt; b;   v[i].x = a, v[i].y = b;   if (pow(a, 2) + pow(b, 2) &lt;= pow(7.5 + d, 2)) firststep.push_back(i); }   if (d &gt;= 50) { puts("Yes"); return 0; }   for (int i = 0; i &lt; firststep.size(); i++) DFS(firststep[i]); if (flag) puts("Yes"); else puts("No");   return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; #include &lt;queue&gt; using namespace std; // 计算两点之间的距离 double distance(double x1, double y1, double x2, double y2) {     return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); } // 判断是否能从当前位置跳到岸边 bool canEscape(double x, double y, double D) {     return abs(x) &gt;= 50 - D || abs(y) &gt;= 50 - D; } // 判断能否从一个鳄鱼位置跳到另一个鳄鱼位置或岸边 bool canReach(double x1, double y1, double x2, double y2, double D) {     return distance(x1, y1, x2, y2) &lt;= D; } // 广度优先搜索判断是否能逃出生天 bool bfs(int N, double D, vector&lt;pair&lt;double, double&gt;&gt;&amp; crocodiles) {     vector&lt;bool&gt; visited(N, false);     queue&lt;int&gt; q;     // 先将起始位置(小岛)加入队列     q.push(0);     while (!q.empty()) {         int cur = q.front();         q.pop();         if (!visited[cur]) {             visited[cur] = true;             // 判断当前位置能否直接跳到岸边             if (cur == 0) {                 for (int i = 0; i &lt; N; ++i) {                     if (canReach(0, 0, crocodiles[i].first, crocodiles[i].second, D)) {                         q.push(i);                     }                 }             } else {                 if (canEscape(crocodiles[cur].first, crocodiles[cur].second, D)) {                     return true;                 }                 // 尝试跳到其他鳄鱼位置                 for (int i = 0; i &lt; N; ++i) {                     if (!visited[i] &amp;&amp; canReach(crocodiles[cur].first, crocodiles[cur].second, crocodiles[i].first, crocodiles[i].second, D)) {                         q.push(i);                     }                 }             }         }     }     return false; } int main() {     int N;     double D;     cin &gt;&gt; N &gt;&gt; D;     vector&lt;pair&lt;double, double&gt;&gt; crocodiles(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; crocodiles[i].first &gt;&gt; crocodiles[i].second;     }     if (bfs(N, D, crocodiles)) {         cout &lt;&lt; "Yes" &lt;&lt; endl;     } else {         cout &lt;&lt; "No" &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。
2. 简答题

月饼

月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。

注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 3 种月饼,其库存量分别为 18、15、10 万吨,总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨,那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼,获得 72 + 45/2 = 94.5(亿元)。

时间限制:5000

内存限制:262144

输入

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500(以万吨为单位)的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量(以万吨为单位);最后一行给出 N 个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。

输出

对每组测试用例,在一行中输出最大收益,以亿元为单位并精确到小数点后 2 位。

样例输入

3 20
18 15 10
75 72 45

样例输出

94.50
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; int n,m; double a[1005]; double v[1005]; double sum[1005]; double ans; double dp[1005]; int main() { cin&gt;&gt;n&gt;&gt;m; for(int i=1;i&lt;=n;i++) { cin&gt;&gt;a[i];//这是数量 } for(int i=1;i&lt;=n;i++) { cin&gt;&gt;sum[i]; v[i]=sum[i]/a[i];//这是价值 }     //价格为1     //多重背包模板 for(int i=1;i&lt;=n;i++) { for(int j=m;j&gt;=0;j--) { for(int k=1;k&lt;=a[i];k++) { if(j&gt;=k) { dp[j]=max(dp[j],dp[j-k]+v[i]*k); } } } }     //记得输出的时候要保留两位小数 cout&lt;&lt;fixed&lt;&lt;setprecision(2)&lt;&lt;dp[m]&lt;&lt;endl; return 0; }</pre>
这道题暂未补解析。
3. 简答题

整数分解

正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、K、P,写出 N 的 K-P 分解。

时间限制:8000

内存限制:262144

输入

输入在一行给出 3 个正整数 N (≤ 400)、K (≤ N)、P (1 < P ≤ 7),以空格分隔。

输出

如果存在解,则按下列格式输出: N = n[1]^P + ... n[K]^P 其中 n[i] (i = 1, ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。 注意:解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解,如 12^2 + 4^2 + 2^2 + 2^2 + 1^2 或 11^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一,则输出具有最大的分解因子序列的解 —— 我们称序列 { a1, a2, … , aK } 比序列 { b1, b2, … , bK } 大,如果存在 1 ≤ L ≤ K 使得 ai=bi 对于 i < L 成立,并且有 aL > bL。 如果解不存在,则输出 `Impossible`。

样例输入

样例#1:

169 5 2

样例#2:

169 167 3

样例输出

样例#1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

样例#2:

Impossible
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 410; int n, k, p; int f[21][N][N]; //计算a的b次方 int power(int a, int b) {     int res = 1;     for (int i = 0; i &lt; b; i++)    res *= a;     return res; } int main() {     cin &gt;&gt; n &gt;&gt; k &gt;&gt; p;     //初始化     memset(f, -0x3f, sizeof f);     f[0][0][0] = 0;     //开始dp     int m;     for (m = 1;; m++)   //从1开始向后枚举     {         int v = power(m, p);   //计算m的p次方         if (v &gt; n) break;  //如果当前枚举的数已经超过n,则dp结束         //更新数据         for (int i = 0; i &lt;= n; i++)             for (int j = 0; j &lt;= k; j++)             {                 //不选当前数                 f[m][i][j] = f[m - 1][i][j];                 //选当前数                 if (i &gt;= v &amp;&amp; j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);             }     }     m--;     //从得到的集合中开始拆分出答案     if (f[m][n][k] &lt; 0)    puts("Impossible");     else     {         printf("%d = ", n);         bool is_first = true;         while (m)         {             int v = power(m, p);             //判断答案集合中是否有m             while (n &gt;= v &amp;&amp; k &amp;&amp; f[m][n - v][k - 1] + m == f[m][n][k])             {                 if (is_first)    is_first = false;                 else    printf(" + ");                 printf("%d^%d", m, p);                 n -= v, k--;             }             m--;         }     }     return 0; }</pre>
这道题暂未补解析。
4. 简答题

森森快递

森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N-1)编号。由于道路限制,第i号城市(i=0, … , N-2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。

公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。

为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。

时间限制:5000

内存限制:262144

输入

输入在第一行给出两个正整数N和Q(2 ≤ N ≤ 105, 1 ≤ Q ≤ 105),表示总共的城市数以及订单数量。 第二行给出(N-1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci(i=0, … , N-2)。题目保证每个Ci是不超过231的非负整数。 接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。

输出

在一行中输出可运输货物的最大重量。

样例输入

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

样例输出

7

提示

样例提示: 我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;algorithm&gt;   #define inf 0x3f3f3f3f3f using namespace std; typedef pair&lt;int,int&gt; pa; typedef long long ll; int n,q; ll ans; int v[100005]; pa p[100005]; int tree[400005],lazy[400005]; bool cmp(const pa &amp;a,const pa &amp;b) {     if(a.second == b.second) return a.first &lt; b.first;     return a.second &lt; b.second; } void build(int l,int r,int t) {     lazy[t] = 0;     if(l == r) tree[t] = v[l];     else {         int mid = (l + r) &gt;&gt; 1;         build(l,mid,t &lt;&lt; 1);         build(mid + 1,r,t &lt;&lt; 1 | 1);         tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     } } void pushdown(int t) {     if(lazy[t] == 0) return;     lazy[t &lt;&lt; 1] += lazy[t];     lazy[t &lt;&lt; 1 | 1] += lazy[t];     tree[t &lt;&lt; 1] -= lazy[t];     tree[t &lt;&lt; 1 | 1] -= lazy[t];     lazy[t] = 0; } void update(int l,int r,int t,int L,int R,int d) {     if(l &gt;= L &amp;&amp; r &lt;= R) tree[t] -= d,lazy[t] += d;     else {         pushdown(t);         int mid = (l + r) &gt;&gt; 1;         if(mid &gt;= L) update(l,mid,t &lt;&lt; 1,L,R,d);         if(mid &lt; R) update(mid + 1,r,t &lt;&lt; 1 | 1,L,R,d);         tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     } } ll query(int l,int r,int t,int L,int R) {     if(l &gt;= L &amp;&amp; r &lt;= R) return tree[t];     if(l &gt; R || r &lt; L) return inf;     int mid = (l + r) &gt;&gt; 1;     ll d = inf;     pushdown(t);     if(mid &gt;= L) d = min(d,query(l,mid,t &lt;&lt; 1,L,R));     if(mid &lt; R) d = min(d,query(mid + 1,r,t &lt;&lt; 1 | 1,L,R));     tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     return d; } int main() {     scanf("%d%d",&amp;n,&amp;q);     for(int i = 0;i &lt; n - 1;i ++) {         scanf("%d",&amp;v[i]);     }     build(0,n - 2,1);     for(int i = 0;i &lt; q;i ++) {         scanf("%d%d",&amp;p[i].first,&amp;p[i].second);         if(p[i].first &gt; p[i].second) swap(p[i].first,p[i].second);         p[i].second --;     }     sort(p,p + q,cmp);     for(int i = 0;i &lt; q;i ++) {         ll d = query(0,n - 2,1,p[i].first,p[i].second);         ans += d;         update(0,n - 2,1,p[i].first,p[i].second,d);     }     printf("%lld",ans); }</pre>
这道题暂未补解析。