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

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

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

一、简答题

1. 简答题

抓牛

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

1、从X移动到X-1或X+1,每次移动花费一分钟

2、从X移动到2*X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

时间限制:2000

内存限制:65536

输入

两个整数,N和K

输出

一个整数,农夫抓到牛所要花费的最小分钟数

样例输入

5 17

样例输出

4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int b[200100]; int a[10]; queue&lt;int&gt; q; int n, k; void bfs(int x) {   q.push(x);   b[x] = 1;   while (!q.empty()) {     int s = q.front();     a[1] = s - 1;     a[2] = s + 1;     a[3] = 2 * s;     for (int i = 1; i &lt; 4; i++) {       if (b[a[i]] == 0 &amp;&amp; a[i] &gt;= 0 &amp;&amp; a[i] &lt; 100100) {         b[a[i]] = b[s] + 1;         q.push(a[i]);         if (a[i] == k) {           cout &lt;&lt; b[k] - 1 &lt;&lt; endl;         }       }     }     q.pop();   } } int main() {   cin &gt;&gt; n &gt;&gt; k;   bfs(n);   return 0; }</pre>
这道题暂未补解析。
2. 简答题

泳池

学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。

现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?

时间限制:1000

内存限制:65536

输入

第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。 

输入范围:

2 ≤ N ≤ 300 

0 ≤ Height ≤ 10000000

输出

输出一个整数,代表最少等待时间T

样例输入

样例输入1:

2
0 2
1 3

样例输入2:

5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6

样例输出

样例输出1:

3

样例输出2:

16

提示

样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。

查看答案与解析
答案:<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; int maze[305][305]; bool reach[305][305]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int N; struct point {   int x, y;   point(int a, int b) : x(a), y(b) {} }; bool canreach(int t) {   if (maze[0][0] &gt; t)     return false;   memset(reach, 0, sizeof(reach));   reach[0][0] = 1;   queue&lt;point&gt; myqueues;   myqueues.push(point(0, 0));   while (!myqueues.empty()) {     point top = myqueues.front();     myqueues.pop();     if (top.x == N - 1 &amp;&amp; top.y == N - 1)       return true;     for (int i = 0; i &lt; 4; i++) {       int tx = top.x + dx[i];       int ty = top.y + dy[i];       if (tx &lt; 0 || tx &gt;= N || ty &lt; 0 || ty &gt;= N)         continue;       if (reach[tx][ty])         continue;       if (maze[tx][ty] &gt; t)         continue;       reach[tx][ty] = 1;       myqueues.push(point(tx, ty));     }   }   return false; } int main() {   memset(maze, 0, sizeof(maze));   cin &gt;&gt; N;   int L = 10000000, R = 0;   for (int i = 0; i &lt; N; i++) {     for (int j = 0; j &lt; N; j++) {       cin &gt;&gt; maze[i][j];       L = min(maze[i][j], L);       R = max(maze[i][j], R);     }   }   int result = 10000000;   while (L &lt;= R) {     int mid = (L + R) / 2;     if (canreach(mid)) {       R = mid - 1;       result = min(result, mid);     } else       L = mid + 1;   }   cout &lt;&lt; result &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。
3. 简答题

问题求解

给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。

举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。

时间限制:1000

内存限制:65536

输入

输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。

输出

对于每个N,输出对应的M。

样例输入

1
2
3
4
78
0

样例输出

2
4
5
8
83
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #define INF 999999999 #define N 1001 using namespace std; int main() {   int n;   while (scanf("%d", &amp;n) != EOF &amp;&amp; n) {     int cnt = 0;     int temp = n;     while (temp &gt; 0) {       if (temp % 2)         cnt++;       temp /= 2;     }     int sum = 0;     while (1) {       temp = ++n;       while (temp &gt; 0) {         if (temp % 2)           sum++;         temp /= 2;       }       if (cnt == sum) {         cout &lt;&lt; n &lt;&lt; endl;         break;       }       sum = 0;     }   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 样例代码  枚举 using namespace std; int n;  // 定义变量 n int tj(int x) {     int ans = 0;  // 定义变量 ans     while (x) {  // 当 x 不为0循环执行         if (x &amp;)             ans++;  // 如果 x 的最低位为1,则将 ans 加1         x &gt;&gt;= 1;  // 将 x 右移1位,即将 x 的二进制表示向右移动一位     }     return ans;  // 返回 ans } int main() {     while (1) {  // 无限循环         cin &gt;&gt; n;  // 从标准输入读取一个整数 n         if (!n)break;  如果 n 为0,则结束循环         int t = tj(n);  // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t         for (int i = n + 1;; i++) {  // 从 n+1 开始递增遍历整数 i             if (t == tj(i)) {                 cout &lt;&lt; i &lt;&lt; endl;  // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等                 break;  // 结束循环             }         }     }     return 0;  // 返回 0,表示程序正常结束 }</pre>
这道题暂未补解析。
4. 简答题

交易市场

市场里面一共有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">#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>
这道题暂未补解析。