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

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

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

一、简答题

1. 简答题

人以群分

社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(outgoing,即活跃度高的)和内向型(introverted,即活跃度低的)。要求两类人群的规模尽可能接近,而他们的总活跃度差距尽可能拉开。

时间限制:5000

内存限制:65536

输入

输入第一行给出一个正整数 N(2 ≤ N ≤ 105)。随后一行给出 N 个正整数,分别是每个人的活跃度,其间以空格分隔。题目保证这些数字以及它们的和都不会超过 231。

输出

按下列格式输出: Outgoing #: N1 Introverted #: N2 Diff = N3 其中 N1 是外向型人的个数;N2 是内向型人的个数;N3 是两群人总活跃度之差的绝对值。

样例输入

样例1:

10
23 8 10 99 46 2333 46 1 666 555

样例2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

样例输出

样例1:

Outgoing #: 5
Introverted #: 5
Diff = 3611

样例2:

Outgoing #: 7
Introverted #: 6
Diff = 9359
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include&lt;iostream&gt; #include&lt;algorithm&gt; using namespace std; int sum[100005]; int main(){ int n; cin&gt;&gt;n; int s=0; for(int i=0;i&lt;n;i++){ cin&gt;&gt;sum[i]; s+=sum[i]; } sort(sum+0,sum+n); int out=0,in=0; for(int i=0;i&lt;n/2;i++){ in+=sum[i]; } for(int i=n-1;i&gt;=n/2;i--){ out+=sum[i]; } printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n%2==0? n/2:n/2+1,n/2,out-in); return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; int main() {     int sum[100005];     int n;     int s = 0;          scanf("%d", &amp;n);          for (int i = 0; i &lt; n; i++) {         scanf("%d", &amp;sum[i]);         s += sum[i];     }          // Sorting the array     for (int i = 0; i &lt; n - 1; i++) {         for (int j = 0; j &lt; n - i - 1; j++) {             if (sum[j] &gt; sum[j + 1]) {                 int temp = sum[j];                 sum[j] = sum[j + 1];                 sum[j + 1] = temp;             }         }     }          int out = 0, in = 0;          for (int i = 0; i &lt; n / 2; i++) {         in += sum[i];     }          for (int i = n - 1; i &gt;= n / 2; i--) {         out += sum[i];     }          printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d", n % 2 == 0 ? n / 2 : n / 2 + 1, n / 2, out - in);          return 0; }</pre>
这道题暂未补解析。
2. 简答题

那就别担心了

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。

时间限制:7000

内存限制:65536

输入

输入首先在一行中给出两个正整数 N(1 < N ≤ 500)和 M,分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。 接下来 M 行,每行给出一对命题之间的推理关系,即两个命题的编号 S1 S2,表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系,且任一命题不能循环自证(即从该命题出发推出该命题自己)。 最后一行给出待检验的两个命题的编号 A B。

输出

在一行中首先输出从 A 到 B 有多少种不同的推理路径,然后输出 Yes 如果推理是“逻辑自洽”的,或 No 如果不是。 题目保证输出数据不超过 109。

样例输入

样例1:

7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1

样例2:

7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1

样例输出

样例1:

3 Yes

样例2:

3 No
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include <iostream> using namespace std; const int N = 510;   int n, m; int way[N][N]; int cnt[N], st, en; bool st1[N], flag = false; void dfs(int u) {     if (u == en) {         cnt[en] ++;         return;     }     if (way[u][0] == 0) flag = true;     for (int i = 1; i <= way[u][0]; i ++ ) {         int j = way[u][i];         if (!st1[j]) {             dfs(j);             st1[j] = true;         }         cnt[u] += cnt[j];     } }   int main() {     cin >> n >> m;     for (int i = 0; i < m; i ++ ) {         int a, b;         cin >> a >> b;         way[a][0] ++;         way[a][way[a][0]] = b;     }     cin >> st >> en;     dfs(st);     if (flag) cout << cnt[st] << " No";     else cout << cnt[st] << " Yes"; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include <stdio.h> #include <stdlib.h> #define MAX_NODES 502 int N, M, S1, S2, A, B, consistency, laneNum[MAX_NODES]; int Edge[MAX_NODES][MAX_NODES]; int dfs(int index) {     if (laneNum[index] != 0) return laneNum[index];          for (int i = 0; i < MAX_NODES; i++) {         if (Edge[index][i] != 0) {             if (laneNum[i] == 0) dfs(i);             laneNum[index] += laneNum[i];         }     }          if (laneNum[index] == 0) consistency = 1;     return laneNum[index]; } int main() {     scanf("%d %d", &N, &M);          for (int i = 0; i < M; ++i) {         scanf("%d %d", &S1, &S2);         Edge[S1][S2] = 1;     }          scanf("%d %d", &A, &B);     laneNum[B] = 1;     dfs(A);          printf("%d %s", laneNum[A], (consistency ? "No" : "Yes"));     return 0; }</pre>
这道题暂未补解析。
3. 简答题

凑零钱

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。

时间限制:7000

内存限制:65535

输入

输入第一行给出两个正整数:N(≤104)是硬币的总个数,M(≤102)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出

在一行中输出硬币的面值V1≤V2≤…≤Vk,满足条件V1+V2+...+Vk=M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution。

注:我们说序列{ A[1], A[2], … }比{ B[1], B[2], … }“小”,是指存在 k ≥ 1 使得 A[i]=B[i] 对所有 i < k 成立,并且 A[k] < B[k]。

样例输入

样例1:

8 9
5 9 8 7 2 3 4 1

样例2:

4 8
7 2 4 3

样例输出

样例1:

1 3 5

样例2:

No Solution
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;memory.h&gt; using namespace std; #define inf 0x3f3f3f3f int n,money,a[20000],dp[20000]; struct node { int parent;  int data; }path[20000]; int main() { int i,j; cin&gt;&gt;n&gt;&gt;money; for(i=0;i&lt;n;i++) cin&gt;&gt;a[i]; sort(a,a+n); memset(dp,-inf,sizeof(dp));//初始化为负无穷 for(i=0;i&lt;20000;i++) path[i].parent=-1; dp[0]=0; for(i=0;i&lt;n;i++) { for(j=money;j&gt;=a[i];j--)//次数越多,序列越小,所以我们dp求能构成序列的需要的最多的数  { if(dp[j]&lt;=dp[j-a[i]]+1) { dp[j]=dp[j-a[i]]+1; path[j].parent=j-a[i];//记录路径  path[j].data=a[i];//记录路径元素  }   } } if(dp[money]&gt;0) {    int r[2000],k=0; int temp=money; while(temp!=-1) { r[k++]=path[temp].data; temp=path[temp].parent; } for(i=k-2;i&gt;0;i--)//输出会多一个0,主要是应为dp[0]=0,输出时单独去掉就可以啦  cout&lt;&lt;r[i]&lt;&lt;" "; cout&lt;&lt;r[0]&lt;&lt;endl; } else { cout&lt;&lt;"No Solution"&lt;&lt;endl; } }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define N 10010 int dp[N], w[N]; int vis[N][N]; void solve() {     int n, m;     scanf("%d %d", &amp;n, &amp;m);     for (int i = 1; i &lt;= n; ++i) scanf("%d", &amp;w[i]);     for (int i = 1; i &lt;= n; ++i)         for (int j = m; j &gt;= w[i]; --j)             if (dp[j] &lt;= dp[j - w[i]] + w[i]) {                 vis[i][j] = 1;                 dp[j] = dp[j - w[i]] + w[i];             }     if (dp[m] != m) printf("No Solution\n");     else {         int a[N];         int v = m, idx = n, count = 0;         while (v &gt; 0) {             if (vis[idx][v]) {                 a[count++] = w[idx];                 v -= w[idx];             }             idx--;         }         for (int i = 0; i &lt; count; ++i) {             printf("%d%s", a[i], (i == count - 1) ? "" : " ");         }     } } int main() {     solve();     return 0; }</pre>
这道题暂未补解析。
4. 简答题

拼题A打卡奖励

拼题 A 的教超搞打卡活动,指定了 N 张打卡卷,第 i 张打卡卷需要 mi 分钟做完,完成后可获得 ci 枚奖励的金币。活动规定每张打卡卷最多只能做一次。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币?

时间限制:7000

内存限制:524288

输入

输入首先在第一行中给出两个正整数 N(≤ 103) 和 M(≤ 365×24×60),分别对应打卡卷的数量和以“分钟”为单位的活动总时长(不超过一年)。随后一行给出 N 张打卡卷要花费的时间 mi(≤ 600),最后一行给出 N 张打卡卷对应的奖励金币数量 ci(≤ 30)。上述均为正整数,一行内的数字以空格分隔。

输出

在一行中输出最多可以赢得的金币数量。

样例输入

5 110
70 10 20 50 60
28 1 6 18 22

样例输出

40

提示

样例解释: 选择最后两张卷子,可以在 50+60=110 分钟内获得 18+22=40 枚金币。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include &lt;iostream&gt;   using namespace std;   const int N = 1e3 + 10, M = 365 * 24 * 60 + 10;   int n, m; int v[N], w[N]; int dp[M];   int gcd(int a, int b) {     return b ? gcd(b, a % b) : a; }   int main() {     cin &gt;&gt; n &gt;&gt; m;     cin &gt;&gt; v[0];     int yuanzi = v[0];     for (int i = 1; i &lt; n; i ++ ) {         cin &gt;&gt; v[i];         yuanzi = gcd(v[i], yuanzi);     }     for (int i = 0; i &lt; n; i ++ ) cin &gt;&gt; w[i];     for (int i = 0; i &lt; n; i ++ ) {         int cnt = 0;         for (int j = m; j &gt;= v[i]; j -= yuanzi ) {             if (dp[j - v[i]] + w[i] &gt; dp[j]) dp[j] = dp[j - v[i]] + w[i];             else cnt ++;             if (cnt == 10) break;         }     }     cout &lt;&lt; dp[m] &lt;&lt; endl; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #define N 1004 #define INF 0x3f3f3f3f int n, m; int w[N], v[N]; int dp[30005]; int mv = 0; int min(int a, int b) {     return a &lt; b ? a : b; } int main() {     scanf("%d %d", &amp;n, &amp;m);          for (int i = 1; i &lt;= n; ++i) {         scanf("%d", &amp;w[i]);     }          for (int i = 1; i &lt;= n; ++i) {         scanf("%d", &amp;v[i]);         mv += v[i];     }     for (int j = 0; j &lt;= mv; ++j) {         dp[j] = INF;     }     dp[0] = 0;     for (int i = 1; i &lt;= n; ++i) {         for (int j = mv; j &gt;= 0; --j) {             if (j &gt;= v[i]) {                 dp[j] = min(dp[j - v[i]] + w[i], dp[j]);             } else {                 dp[j] = dp[j];             }         }     }     for (int j = mv; j &gt;= 0; j--) {         if (dp[j] &lt;= m) {             printf("%d", j);             break;         }     }     return 0; }</pre>
这道题暂未补解析。