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

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

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

一、简答题

1. 简答题

问题求解

给定一个正整数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">//解法1 #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #include&lt;algorithm&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>
这道题暂未补解析。
2. 简答题

算24

给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。

时间限制:6000

内存限制:65536

输入

输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。

输出

对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。

样例输入

5 5 5 1
1 1 4 2
0 0 0 0

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:as3;toolbar:false">//解法1 //青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include &lt;iostream&gt; #include&lt;cmath&gt; #include&lt;bits/stdc++.h&gt; #define EPS  1e-6 using namespace std; bool iszero(double c){     if(fabs(c) &lt;= EPS) return 1;     else return 0; } bool suan24(double* a,int k){     if(k==1 &amp;&amp; iszero(a[0]-24)) return 1;     double b[5];     for(int i=0;i&lt;k-1;i++)         for(int j=i+1;j&lt;k;j++) {             int z = 0;             for (int xx = 0; xx &lt; k; xx++)                 if (xx != i &amp;&amp; xx != j) b[z++] = a[xx];             b[z] = a[i] + a[j];             if (suan24(b, k - 1)) return 1;             b[z] = a[i] - a[j];             if (suan24(b, k - 1)) return 1;             b[z] = a[j] - a[i];             if (suan24(b, k - 1)) return 1;             b[z] = a[i] * a[j];             if (suan24(b, k - 1)) return 1;             if (a[j] != 0) {                 b[z] = a[i] / a[j];                 if (suan24(b, k - 1)) return 1;             }             if (!iszero(a[i])) {                 b[z] = a[j] / a[i];                 if (suan24(b, k - 1)) return 1;             }     }     return 0; } int main() {     while(1)     {         double a[6];         int sum=0;         for(int i=0;i&lt;4;++i)         {             cin&gt;&gt;a[i];             sum+=a[i];         }         if(sum==0)break;         bool flag=suan24(a,4);         if(flag==1)cout&lt;&lt;"YES"&lt;&lt;endl;         else cout&lt;&lt;"NO"&lt;&lt;endl; //        cout&lt;&lt;flag&lt;&lt;endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2  深搜 #include &lt;bits/stdc++.h&gt;   using namespace std;  double a[5]; bool fig(double a[],int n){ double b[5]; int i,j,k,m; if(fabs(a[0]-24)&lt;1e-6 &amp;&amp; n==1) return 1; if(n==1) return 0; for(i=0;i&lt;n-1;i++) for(j=i+1;j&lt;n;j++){ m=0; for(k=0;k&lt;n;k++) if(k!=i&amp;&amp;k!=j) b[++m]=a[k]; b[0]=a[i]+a[j];if(fig(b,n-1)) return 1; b[0]=a[i]-a[j];if(fig(b,n-1)) return 1; b[0]=a[j]-a[i];if(fig(b,n-1)) return 1; b[0]=a[i]*a[j];if(fig(b,n-1)) return 1; b[0]=a[i]/a[j];if(fig(b,n-1)) return 1; b[0]=a[j]/a[i];if(fig(b,n-1)) return 1; } return 0; } int main() { while(1){ for(int i=0;i&lt;4;i++) cin&gt;&gt;a[i]; if(a[0]==0&amp;&amp;a[1]==0&amp;&amp;a[2]==0&amp;&amp;a[3]==0) break; if(fig(a,4)) cout&lt;&lt;"YES"&lt;&lt;endl; else cout&lt;&lt;"NO"&lt;&lt;endl; } 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">//解法1 //青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #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><p><br/></p><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. 简答题

泳池

小C在一个排水系统不太好的学校上学。又是一个下雨天,学校里高低不平积了很多水。小C突发奇想:如果大雨一直下,多久以后我可以在学校里游泳呢?

学校是 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">//动规+广搜+二分 //从(0,0)到(N-1,N-1)的各条路径最大值中的最小值。 //直接深搜和广搜会超时   #include &lt;bits/stdc++.h&gt; using namespace std; int n,m[305][305];// n 是矩阵的大小,m 存储矩阵元素 bool v[305][305];// v 记录矩阵中点是否被访问过 int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct Point{ int x,y; Point(int a,int b):x(a),y(b){} }; bool is_reach(int t){// 判断是否在时间t内到达右下角坐标 if(m[0][0]&gt;t) return false;// 左上角大于t无法到达 memset(v,0,sizeof(v)); v[0][0]=1; queue&lt;Point&gt; myq;// 创建一个队列存储待访问的点 myq.push(Point(0,0)); while(!myq.empty()){ Point top=myq.front(); myq.pop(); // 到达右下角坐标,返回true if((top.x==n-1)&amp;&amp;(top.y==n-1)) return true; for(int i=0;i&lt;4;i++){ int xx=top.x+dx[i]; int yy=top.y+dy[i]; // 如果已访问过或元素大于t,则无法继续前进 if(xx&lt;0||xx&gt;=n||yy&lt;0||yy&gt;=n||v[xx][yy]||(m[xx][yy]&gt;t)) continue; v[xx][yy]=1;// 标记坐标访问状态 myq.push(Point(xx,yy));// 将可继续访问的坐标加入队 } } return false;// 无法到达右下角坐标,返回false } int main() { memset(m,0,sizeof(m)); cin&gt;&gt;n; int L=1e7,R=0; for(int i=0;i&lt;n;i++) for(int j=0;j&lt;n;j++){ cin&gt;&gt;m[i][j]; L=min(L,m[i][j]); R=max(R,m[i][j]); } int result=1e7; while(L&lt;R){// 二分查找 int mid=(L+R+1)/2; if(is_reach(mid)){// mid值能到达右下角坐标 R=mid-1; result=min(result,mid);// 更新结果 } else  L=mid; } cout&lt;&lt;result;     return 0; }</pre>
这道题暂未补解析。