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

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

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

一、简答题

1. 简答题

逃离迷宫(2024-3-5级)

你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。

时间限制:1000

内存限制:65536

输入

输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。

输出

每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。


样例输入

2
4 7 
S...
###.
.#E.
..#.
3 4
S..
..#
.#E

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;stdbool.h&gt; #include &lt;string.h&gt; #define MAX_M 12   struct node {     int x, y;     int tcnt; };   int m, t; char mat[MAX_M][MAX_M];   int bfs(int x0, int y0, int x1, int y1) {     if (x0 == x1 &amp;&amp; y0 == y1) {         return 0;     }     struct node nd = {x0, y0, 0};     int x, y;     struct node q[MAX_M * MAX_M];     int front = 0, rear = 0;     q[rear++] = nd;     while (front &lt; rear) {         nd = q[front++];         x = nd.x;         y = nd.y;         if (x &lt; m - 1) {             if (mat[x + 1][y] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x + 1][y] == '.') {                 struct node newNode = {x + 1, y, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x + 1][y] = '*';             }         }         if (x &gt; 0) {             if (mat[x - 1][y] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x - 1][y] == '.') {                 struct node newNode = {x - 1, y, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x - 1][y] = '*';             }         }         if (y &lt; m - 1) {             if (mat[x][y + 1] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x][y + 1] == '.') {                 struct node newNode = {x, y + 1, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x][y + 1] = '*';             }         }         if (y &gt; 0) {             if (mat[x][y - 1] == 'E') {                 return nd.tcnt + 1;             } else if (mat[x][y - 1] == '.') {                 struct node newNode = {x, y - 1, nd.tcnt + 1};                 q[rear++] = newNode;                 mat[x][y - 1] = '*';             }         }     }     return -1; }   int main() {     int k, i, j, x0, y0, x1, y1, ans;     scanf("%d", &amp;k);     while (k--) {         scanf("%d %d", &amp;m, &amp;t);         for (i = 0; i &lt; m; i++) {             for (j = 0; j &lt; m; j++) {                 scanf(" %c", &amp;mat[i][j]);                 if (mat[i][j] == 'S') {                     x0 = i;                     y0 = j;                 } else if (mat[i][j] == 'E') {                     x1 = i;                     y1 = j;                 }             }         }         ans = bfs(x0, y0, x1, y1);         if (ans &lt;= t &amp;&amp; ans &gt;= 0) {             printf("YES\n");         } else {             printf("NO\n");         }     }     return 0; }</pre>
这道题暂未补解析。
2. 简答题

密室逃脱(2024-3-5级)

小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。

密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:

墙,以数字0标记

路,以数字1标记

隐藏线索处,以数字( > 1)标记, 代表该线索的难度

小Y需要按照难度递增的顺序解开各个线索,逃脱密室。

时间限制:1000

内存限制:65536

输入

第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。

输出

对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.


样例输入

2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5

样例输出

8
-1


提示

样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//示例代码1 条件+广搜 #include &lt;iostream&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #include &lt;queue&gt;   using namespace std; int m,n; int maze[104][104] = {};   int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; bool legal(int x, int y){     if(0 &lt;= x &amp;&amp; x&lt; m &amp;&amp; 0 &lt;= y &amp;&amp; y &lt; n &amp;&amp; maze[x][y] != 0)return 1;     return 0; } struct Node{     int x, y, k, t; }; int main() {     int T;     cin &gt;&gt; T;     while(T--){         memset(maze, 0, sizeof(maze));         int vis[104][104] = {};         memset(vis, 0xff, sizeof(vis));         int S[10050] = {};         int cnt = 0;         cin &gt;&gt; m &gt;&gt; n;         for(int i = 0; i &lt; m; ++i){             for(int j = 0; j &lt; n; ++j){                 cin &gt;&gt; maze[i][j];                 if (maze[i][j] &gt; 1) {                     S[cnt++] = maze[i][j];                 }             }         }         queue&lt;Node&gt; open;         sort(S, S + cnt);         if (maze[0][0] == S[0]) {             open.push({0, 0, 1, 0});             vis[0][0] = 1;         }         else {             open.push({0, 0, 0, 0});             vis[0][0] = 0;         }         bool flag = 0;                while (!open.empty()) {             Node temp = open.front();             open.pop();             if (temp.k == cnt) {                 flag = 1;                 cout &lt;&lt; temp.t &lt;&lt; endl;                 break;             }             for (int i = 0; i &lt; 4; i++) {                 int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;                 if (!legal(x,y)) continue;                 if (maze[x][y] == S[k]) k++;                 if (vis[x][y] &gt;= k) continue;                 vis[x][y] = k;                 open.push({x, y, k, temp.t + 1});             }         }         if (!flag) cout &lt;&lt; -1 &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;queue&gt; #include &lt;cstring&gt; using namespace std; int m,n; int maze[104][104] = {}; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; bool legal(int x, int y){     if(0 &lt;= x &amp;&amp; x&lt; m &amp;&amp; 0 &lt;= y &amp;&amp; y &lt; n &amp;&amp; maze[x][y] != 0)         return 1;     return 0; } struct Node{     int x, y, k, t; }; int main() {     int T;     cin &gt;&gt; T;     while(T--){         memset(maze, 0, sizeof(maze));         int vis[104][104] = {};         memset(vis, 0xff, sizeof(vis));         int S[10050] = {};         int cnt = 0;         cin &gt;&gt; m &gt;&gt; n;         for(int i = 0; i &lt; m; ++i){             for(int j = 0; j &lt; n; ++j){                 cin &gt;&gt; maze[i][j];                 if (maze[i][j] &gt; 1) {                     S[cnt++] = maze[i][j];                 }             }         }         queue&lt;Node&gt; open;         sort(S, S + cnt);         if (maze[0][0] == S[0]) {             open.push({0, 0, 1, 0});             vis[0][0] = 1;         }         else {             open.push({0, 0, 0, 0});             vis[0][0] = 0;         }         bool flag = 0;               while (!open.empty()) {             Node temp = open.front();             open.pop();             if (temp.k == cnt) {                 flag = 1;                 cout &lt;&lt; temp.t &lt;&lt; endl;                 break;             }             for (int i = 0; i &lt; 4; i++) {                 int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;                 if (!legal(x,y))                     continue;                 if (maze[x][y] == S[k])                     k++;                 if (vis[x][y] &gt;= k)                     continue;                 vis[x][y] = k;                 open.push({x, y, k, temp.t + 1});             }         }         if (!flag)             cout &lt;&lt; -1 &lt;&lt; endl;     }     return 0; }</pre><p></p>
这道题暂未补解析。
3. 简答题

交易市场(2024-3-5级)

市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。

时间限制:1000

内存限制:65536

输入

第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)

输出

一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000


样例输入

3 3
1 2 2
2 3 3
1 3 4

样例输出

5
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;vector&gt; #define INF 1000000000 using namespace std; struct exchangeTo {   int target;   int p;   exchangeTo(int a, int b) : target(a), p(b) {} }; struct path {   int pre;   int val; } dp[1005]; map&lt;int, vector&lt;exchangeTo&gt;&gt; tables; bool inPath(int n, int k) {   while (k != -1) {     if (n == k)       return true;     k = dp[k].pre;   }   return false; } int main() {   memset(dp, -1, sizeof(dp));   int n, m;   cin &gt;&gt; n &gt;&gt; m;   for (int i = 0; i &lt; m; i++) {     int x, y, z;     cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;     tables[x].push_back(exchangeTo(y, z));   }   dp[1].val = 0, dp[1].pre = 0;   bool done = false;   int result = 0;   queue&lt;int&gt; myqueues;   myqueues.push(1);   while (!myqueues.empty()) {     int top = myqueues.front();     myqueues.pop();     if (!tables[top].empty()) {       vector&lt;exchangeTo&gt;::iterator ii;       for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {         if (inPath(ii-&gt;target, top)) {           result = INF;           done = true;           break;         }         if (dp[top].val + ii-&gt;p &gt; dp[ii-&gt;target].val) {           dp[ii-&gt;target].val = dp[top].val + ii-&gt;p;           dp[ii-&gt;target].pre = top;           myqueues.push(ii-&gt;target); // 注意这里的更新         }         result = max(result, dp[ii-&gt;target].val);       }       if (done)         break;     }   }   cout &lt;&lt; result &lt;&lt; endl;   return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include &lt;set&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #include &lt;queue&gt; #define INF 1000000000 using namespace std; struct exchangeTo {     int target;     int p;     exchangeTo(int a, int b) :target(a), p(b) {} }; struct path {     int pre;     int val; }dp[1005]; map&lt;int, vector&lt;exchangeTo&gt; &gt;tables; bool inPath(int n, int k) {     while (k != -1) {         if (n == k)             return true;         k = dp[k].pre;     }     return false; } int main() {     memset(dp, -1, sizeof(dp));     int n, m;     cin &gt;&gt; n &gt;&gt; m;     for (int i = 0; i &lt; m; i++) {         int x, y, z;         cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;         tables[x].push_back(exchangeTo(y, z));     }     dp[1].val = 0, dp[1].pre = 0;     bool done = false;     int result = 0;     queue&lt;int&gt;myqueues;     myqueues.push(1);     while (!myqueues.empty()) {         int top = myqueues.front();         myqueues.pop();         if (!tables[top].empty()) {             vector&lt;exchangeTo&gt;::iterator ii;             for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {                 if (inPath(ii-&gt;target, top))                 {                     result = INF;                     done = true;                     break;                 }                 if (dp[top].val + ii-&gt;p &gt; dp[ii-&gt;target].val) {                     dp[ii-&gt;target].val = dp[top].val + ii-&gt;p;                     dp[ii-&gt;target].pre = top;                     myqueues.push(ii-&gt;target);                 }                 result = max(result, dp[ii-&gt;target].val);             }             if (done)break;         }     }     cout &lt;&lt; result &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

求逆序对问题(2024-3-5级)

给定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">//参考代码1 #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><pre class="brush:cpp;toolbar:false">//参考代码2 #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);     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++;         }     }     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><p><br/></p>
这道题暂未补解析。