首页 › 试卷 › C/C++编程考级 › C/C++编程五级 › 青少年软件编程(C语言五级)等级考试真题试卷(2021年6月)

青少年软件编程(C语言五级)等级考试真题试卷(2021年6月) VIP

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

一、简答题

1. 简答题

数字变换

给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换 

1. 交换相邻的两个数字 

2. 将一个数字加1。如果加1后大于9,则变为0 

3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。 

最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。

时间限制:1000

内存限制:65536

输入

有最多 100,000 组数据 每组数据就是包含5个数字的字符串

输出

对每组数据,输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1

样例输入

12435
99999
12374

样例输出

1
-1
3

提示

由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; #define _init(x, v) memset(x, v, sizeof(x)) int rcd[100000]; bool vis[100000][5][5]; struct node {   int a[5], d, o2, o3; }; queue&lt;node&gt; q; void in() {   _init(rcd, -1);   node s = {1, 2, 3, 4, 5, 0, 3, 2};   q.push(s);   vis[12345][3][2] = 1;   rcd[12345] = 0; } int toNum(node &amp;n) {   int t = 0;   for (int i = 0; i &lt; 5; ++i) {     t *= 10;     t += n.a[i];   }   return t; } void bfs() {   while (!q.empty()) {     node s = q.front();     int t = toNum(s);     if (rcd[t] == -1 || rcd[t] &gt; s.d)       rcd[t] = s.d;     // printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);     ++s.d;     q.pop();     for (int i = 0; i &lt; 5; ++i) {       // o1       if (i &lt; 4 &amp;&amp; s.a[i] != s.a[i + 1]) {         swap(s.a[i], s.a[i + 1]);         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         swap(s.a[i], s.a[i + 1]);       }       // o2       if (s.o2 &gt; 0) {         --s.o2;         s.a[i] = (s.a[i] + 1) % 10;         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         s.a[i] = (s.a[i] + 10 - 1) % 10;         ++s.o2;       }       // o3       if (s.o3 &gt; 0) {         --s.o3;         int bak = s.a[i];         s.a[i] = (2 * s.a[i]) % 10;         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         s.a[i] = bak;         ++s.o3;       }     }   } } int main() {   in();   bfs();   int n;   while (cin &gt;&gt; n) {     cout &lt;&lt; rcd[n] &lt;&lt; endl;   }   system("pause");   return 0; }</pre>
这道题暂未补解析。
2. 简答题

圣诞老人的礼物

圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果,请问圣诞老人最多能带走多大价值的糖果。

时间限制:1000

内存限制:65536

输入

第一行由两个部分组成,分别为糖果箱数正整数n(1 = n = 100),驯鹿能承受的最大重量正整数w(0<w<10000),两个数用空格隔开。其余n行每行对应一箱糖果,由两部分组成,分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开。

输出

输出圣诞老人能带走的糖果的最大总价值,保留1位小数。输出为一行,以换行符结束。

样例输入

4 15
100 4
412 8
266 7
591 2

样例输出

1193.0
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; using namespace std; struct gift {   int value;   int weight;   double density; } gf[101]; bool cmp(gift f1, gift f2) { // 按照单重价值从大到小排序   return f1.density &gt; f2.density; } int main() {   int n, w;   cin &gt;&gt; n &gt;&gt; w;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; gf[i].value &gt;&gt; gf[i].weight;     gf[i].density = 1.0 * gf[i].value / gf[i].weight;   }   sort(gf, gf + n, cmp);   double totw = 0, totv = 0; // 注意到w为int型,可拆分为double型   // 所以新建一个double型保存背包剩余重量   for (int i = 0; i &lt; n; i++) {     if (totw + gf[i].weight &lt;= w) {       totw += gf[i].weight;       totv += gf[i].value;     } else {       totv += gf[i].density * (w - totw);       totw = w;       break;     }   }   printf("%.1lf", totv);   return 0; }</pre>
这道题暂未补解析。
3. 简答题

忍者道具

忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?

时间限制:1000

内存限制:65536

输入

第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。

输出

输出一个整数,最少需要多少个工具包。

样例输入

5 1996
1
2
1994
12
29

样例输出

2

提示

对于100%的数据,1=N=18,1=Ci=W=10^8。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; const int MAXN = 18; int used[MAXN]; int W; int m, n, ans = (1 &lt;&lt; 30); int item[MAXN]; int bag[MAXN]; void dfs(int x, int sum) {   if (sum &gt;= ans)     return;   if (x == n) {     ans = min(ans, sum);     return;   }   for (int i = 0; i &lt; sum; ++i) {     if (bag[i] &gt;= item[x]) {       bag[i] -= item[x];       dfs(x + 1, sum);       bag[i] += item[x];     }   }   bag[sum] -= item[x];   dfs(x + 1, sum + 1);   bag[sum] += item[x]; } int main() {   cin &gt;&gt; n &gt;&gt; m;   for (int i = 0; i &lt; n; ++i) {     cin &gt;&gt; item[i];     bag[i] = m;   }   dfs(0, 1);   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2  深搜 #include &lt;bits/stdc++.h&gt;   using namespace std;  int n,w,ans=20; int a[20],bag[20]; void dfs(int x,int sum){//放第x个物品,已使用sum个包 if(sum&gt;=ans) return;//背包数量不够 if(x&gt;n) {ans=min(ans,sum);return;}//所有物品已放完 for(int i=1;i&lt;=sum;i++){//放入现有背包 if(bag[i]&gt;=a[x]){ bag[i]-=a[x]; dfs(x+1,sum); bag[i]+=a[x];//回溯 } } bag[sum+1]-=a[x];//放入新背包 dfs(x+1,sum+1); bag[sum+1]+=a[x];//回溯 } int main() { cin&gt;&gt;n&gt;&gt;w; for(int i=1;i&lt;=n;i++) { cin&gt;&gt;a[i]; bag[i]=w;//初始化n个背包的开始可用容量 } dfs(1,1); cout&lt;&lt;ans&lt;&lt;endl; return 0; }</pre>
这道题暂未补解析。
4. 简答题

求逆序对问题

给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

时间限制:1000

内存限制:256000

输入

本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。

输出

每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。

样例输入

10

0 9 8 7 6 5 4 3 2 1

0

样例输出

16

提示

请注意答案范围,如果使用printf输出long long类型,请用%lld

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; int arr[200005]; int tmp[200005]; int N; long long mergesort(int start, int end) {   long long cnt = 0, mid = (start + end) / 2;   if (start &gt;= end)     return 0;   cnt += mergesort(start, mid);   cnt += mergesort(mid + 1, end);   // find important reverse pair   int i = start, j = mid + 1;   while (i &lt;= mid &amp;&amp; j &lt;= end) {     if (arr[i] &gt; 2 * arr[j] &amp;&amp; j &lt;= end) {       cnt += (mid - i + 1);       j++;     } else {       i++;     }   }   // merge sort   i = start, j = mid + 1;   int idx = 0;   while (i &lt;= mid &amp;&amp; j &lt;= end) {     if (arr[i] &gt; arr[j]) {       tmp[idx++] = arr[j++];     } else {       tmp[idx++] = arr[i++];     }   }   while (i &lt;= mid)     tmp[idx++] = arr[i++];   while (j &lt;= end)     tmp[idx++] = arr[j++];   for (int k = 0; k &lt; idx; k++) {     arr[start + k] = tmp[k];   }   return cnt; } int main() {   while (cin &gt;&gt; N) {     if (N == 0)       break;     for (int i = 1; i &lt;= N; i++) {       cin &gt;&gt; arr[i];     }     cout &lt;&lt; mergesort(1, N) &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。