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

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

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

一、简答题

1. 简答题

怪盗基德的滑翔翼

怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已,怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。初始时,怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?

时间限制:1000

内存限制:65536

输入

输入数据第一行是一个整数K(K < 100),代表有K组测试数据。 每组测试数据包含两行:第一行是一个整数N(N < 100),代表有N幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度h(0 < h < 10000),按照建筑的排列顺序给出。

输出

对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。

样例输入

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

样例输出

6
6
9
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 105 int a[N], dpu[N], dpd[N]; int main() {     int k, n, mxu, mxd;     cin &gt;&gt; k;     while(k--)     {         mxu = mxd = 0;         cin &gt;&gt; n;         for(int i = 1; i &lt;= n; ++i)             cin &gt;&gt; a[i];         for(int i = 1; i &lt;= n; ++i)//求最长上升子序列          {             dpu[i] = 1;             for(int j = 1; j &lt; i; ++j)                 if(a[i] &gt; a[j])                     dpu[i] = max(dpu[i], dpu[j]+1);             mxu = max(mxu, dpu[i]);         }            for(int i = 1; i &lt;= n; ++i)//求最长下降子序列          {             dpd[i] = 1;             for(int j = 1; j &lt; i; ++j)                 if(a[i] &lt; a[j])                     dpd[i] = max(dpd[i], dpd[j]+1);             mxd = max(mxd, dpd[i]);         }         cout &lt;&lt; max(mxu, mxd) &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 105 int a[N], dpu[N], dpd[N]; int main() {     int k, n, mx;     cin &gt;&gt; k;     while(k--)     {         mx = 0;         cin &gt;&gt; n;         for(int i = 1; i &lt;= n; ++i)             cin &gt;&gt; a[i];         for(int i = 1; i &lt;= n; ++i)//求最长上升子序列          {             dpu[i] = dpd[i] = 1;             for(int j = 1; j &lt; i; ++j)             {                  if(a[i] &gt; a[j])                     dpu[i] = max(dpu[i], dpu[j]+1);                 if(a[i] &lt; a[j])                     dpd[i] = max(dpd[i], dpd[j]+1);             }             mx = max(max(dpd[i], dpu[i]), mx);          }         cout &lt;&lt; mx &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3 #include &lt;bits/stdc++.h&gt;   using namespace std;   int k, n   int a[105][3], ans;  int main() { cin &gt;&gt; k;  // 从标准输入读取一个整数 k while (k--)  // 循环执行 k 次 { cin &gt;&gt; n;  // 从标准输入读取一个整数 n memset(a, 0, sizeof(a));  // 将数组 a 的所有元素置为 0 ans = 0;  // 将变量 ans 置为 0 // 动态规划计算最长上升子序列 for (int i = 1; i &lt;= n; i++)  // 从第 1 个位置到第 n 个位置遍历 { cin &gt;&gt; a[i][0];  // 从标准输入读取一个整数到数组 a 中的第 i 行第 0 列 a[i][1] = 1;  // 将数组 a 中的第 i 行第 1 列置为 1 for (int j = 1; j &lt;= i - 1; j++)  // 从第 1 个位置到第 i-1 个位置遍历 if (a[j][0] &gt; a[i][0] &amp;&amp; a[j][1] + 1 &gt; a[i][1])  // 如果数组 a 中第 j 行第 0 列的元素大于数组 a 中第 i 行第 0 列的元素,并且数组 a 中第 j 行第 1 列的元素加 1 大于数组 a 中第 i 行第 1 列的元素 a[i][1] = a[j][1] + 1;  // 将数组 a 中第 i 行第 1 列置为数组 a 中第 j 行第 1 列的元素加 1 ans = max(ans, a[i][1]);  // 更新变量 ans,取 ans 和数组 a 中第 i 行第 1 列的元素的较大值 } // 动态规划计算最长下降子序列 for (int i = n; i &gt;= 1; i--)  // 从第 n 个位置到第 1 个位置遍历 { a[i][2] = 1;  // 将数组 a 中的第 i 行第 2 列置为 1 for (int j = n; j &gt;= i + 1; j--)  // 从第 n 个位置到第 i+1 个位置遍历 if (a[j][0] &gt; a[i][0] &amp;&amp; a[i][2] &lt; a[j][2] + 1)  // 如果数组 a 中第 j 行第 0 列的元素大于数组 a 中第 i 行第 0 列的元素,并且数组 a 中第 i 行第 2 列的元素小于数组 a 中第 j 行第 2 列的元素加 1 a[i][2] = a[j][2] + 1;  // 将数组 a 中第 i 行第 2 列置为数组 a 中第 j 行第 2 列的元素加 1 ans = max(ans, a[i][2]);  // 更新变量 ans,取 ans 和数组 a 中第 i 行第 2 列的元素的较大值 } cout &lt;&lt; ans &lt;&lt; endl;  // 输出变量 ans 到标准输出 } return 0;  // 返回 0,表示程序正常结束 }</pre>
这道题暂未补解析。
2. 简答题

数字组合

有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如: n=5,5个数分别为1,2,3,4,5,t=5; 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。

时间限制:1000

内存限制:65536

输入

输入的第一行是两个正整数n和t,用空格隔开,其中1<=n<=20,表示正整数的个数,t为要求的和(1<=t<=1000) 接下来的一行是n个正整数,用空格隔开。

输出

和为t的不同的组合方式的数目。

样例输入

5 5
1 2 3 4 5

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1 #include &lt;bits/stdc++.h&gt; using namespace std; int a[25],n,t,ans; void dfs(int i,int sum){ if(i==n){ if(t==sum){ ans++; } return; } i++; dfs(i,sum+a[i]); dfs(i,sum); } int main(){ cin&gt;&gt;n&gt;&gt;t; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; } dfs(0,0); cout&lt;&lt;ans; return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 背包问题 #include &lt;bits/stdc++.h&gt; using namespace std; int n,t; int a[22],f[1005]; int main() { cin &gt;&gt; n &gt;&gt; t;  // 从标准输入读取两个整数 n 和 t for (int i = 1; i &lt;= n; i++) cin &gt;&gt; a[i];  // 从标准输入读取 n 个整数,并存储到数组 a 中 f[0] = 1;  // 将数组 的第 0 个元素置为 1,表示容积为 0 时的方式数量为 1 for (int i = 1; i &lt;= n; i++) { for (int j = t; j &gt;= a[i]; j--) f[j] += f[j - a[i]];  // 动态规划转移方程,累加之前容积 j 和当前物品体积之差的容积的方式数量 } cout &lt;&lt; f[t];  // 输出数组 f 中第 t 个元素,表示容积为 t 时的方式数量 return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3 递归求解 #include &lt;bits/stdc++.h&gt;   using namespace std;  int n, t;  int a[22];   int f(int sum, int p) { if (sum == t) return 1;  // 如果当前总和等于目标值 t,则返回1 表示找到一种组合方式。 if (sum &gt; t || p &gt; n) return 0;  // 如果当前总和大于目标值 t 或已经遍历完所有物品,则返回 0 表示没有合适的组合方式。 // 递归调用 f 函数,分别尝试选取下一个物品和不选取下一个物品两种情况,并累加它们的结果 return f(sum + a[p], p + 1) + f(sum, p + 1); } int main() { cin &gt;&gt; n &gt;&gt; t;  // 从标准输入读取两个整数 n 和 t for (int i = 1; i &lt;= n; i++) cin &gt;&gt; a[i];  // 从标准输入读取 n 个整数,并存储到数组 a 中 cout &lt;&lt;f(0, 1);  // 调用函数 f,初始总和为 0,从第一个物品开始选取 return 0; }</pre>
这道题暂未补解析。
3. 简答题

带通配符的字符串匹配

 通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。

你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。

例如,1?456 可以匹配 12456、13456、1a456,但是却不能够匹配23456、1aa456;

2*77?8可以匹配 24457798、237708、27798。

时间限制:1000

内存限制:65536

输入

输入有两行,每行为一个不超过20个字符的字符串,第一行带通配符,第二行不带通配符

输出

如果两者可以匹配,就输出“matched”,否则输出“not matched”

样例输入

1*456?
11111114567

样例输出

matched
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1 #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #include&lt;string&gt; #include&lt;cstring&gt; using namespace std; int f[3005][3005]={0},q[3005]={0},prt[3005][3005]={0}; string st1,st2; int gcd(int a,int b) {   if(b==0)return a;     return gcd(b,a%b);} void Get(int x,int y) {   if(x==0&amp;&amp;y==0)return;     int lx=x-1,ly=prt[x][y];     if(st1[x]=='*'&amp;&amp;y!=ly){q[++q[0]]=y-ly;}     Get(lx,ly);} int main() {   cin&gt;&gt;st1&gt;&gt;st2;     int i,j,k,bj,div,ans=0,len1=st1.length(),len2=st2.length();     st1=' '+st1;st2=' '+st2;     f[0][0]=1;     for(i=1;i&lt;=len1;i++)        for(j=0;j&lt;=len2;j++)          {if(st1[i]=='?'||st1[i]==st2[j])             {f[i][j]=f[i-1][j-1];              if(f[i][j])prt[i][j]=j-1;}           else if(st1[i]=='*')             {for(k=j,bj=0;k&gt;=0;k--)                 if(f[i-1][k]){bj=1;break;}              if(bj){f[i][j]=1;prt[i][j]=k;}}}     if(f[len1][len2])       {cout&lt;&lt;"matched\n";}     else cout&lt;&lt;"not matched";     return 0;}</pre><pre class="brush:cpp;toolbar:false">//解法2 动态规划 #include &lt;bits/stdc++.h&gt;   using namespace std;  string s1,s2; bool dp[30][30];//dp[i][j] 表示模式串s1的前i个字符和字符串s2的前j个字符是否匹配 int main() { cin&gt;&gt;s1&gt;&gt;s2; int l1=s1.size(); int l2=s2.size(); dp[0][0]=true;//将dp[0][0]置为 true,表示空字符串匹配 for(int i=1;i&lt;=l1;i++) for(int j=0;j&lt;=l2;j++){ //如果s1[i-1]是*,则在dp[i-1][k]中寻找最后一个为true的位置(其中k&gt;=j), //如果找到,则将dp[i][j]置为true。 if(s1[i-1]=='*'){ for(int k=j;k&gt;=0;k--){ if(dp[i-1][k]){ dp[i][j]=true; break; } } }else { //如果当前字符可以匹配(即s1[i-1]==s2[j-1]或者s1[i-1]=='?') //且前面的子问题匹配成功(dp[i-1][j-1] 为 true),则将dp[i][j]置为true。 if((s1[i-1]==s2[j-1]||s1[i-1]=='?') &amp;&amp; (j &amp;&amp; dp[i-1][j-1])) dp[i][j]=true; } } if(dp[l1][l2]) cout&lt;&lt;"matched"; else cout&lt;&lt;"not matched"; return 0; }</pre>
这道题暂未补解析。
4. 简答题

股票买卖

最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。

假设阿福已经准确预测出了某只股票在未来 N 天的价格,他希望买卖两次,使得获得的利润最高。为了计算简单起见,利润的计算方式为卖出的价格减去买入的价格。

同一天可以进行多次买卖。但是在第一次买入之后,必须要先卖出,然后才可以第二次买入。

现在,阿福想知道他最多可以获得多少利润。

时间限制:1000

内存限制:65536

输入

输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。 接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 天。第二行是 N 个被空格分开的整数,表示每天该股票的价格。该股票每天的价格的绝对值均不会超过 1,000,000 。

输出

对于每组数据,输出一行。该行包含一个整数,表示阿福能够获得的最大的利润。

样例输入

3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2

样例输出

28
2
0

提示

对于第一组样例,阿福可以第 1 次在第 1 天买入(价格为 5 ),然后在第 2 天卖出(价格为 14 )。第 2 次在第 3 天买入(价格为 -2 ),然后在第 7 天卖出(价格为 17 )。一共获得的利润是 (14 - 5) + (17 - (-2)) = 28 对于第二组样例,阿福可以第 1 次在第 1 天买入(价格为 6 ),然后在第 2 天卖出(价格为 8 )。第 2 次仍然在第 2 天买入,然后在第 2 天卖出。一共获得的利润是 8 - 6 = 2 对于第三组样例,由于价格一直在下跌,阿福可以随便选择一天买入之后迅速卖出。获得的最大利润为 0

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1: //基本解法 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, ans, a[N], de[N], db[N], dpe[N], dpb[N]; int main() {     int mn, mx;     scanf("%d", &amp;t);     while(t--)     {         memset(dpe, 0, sizeof(dpe));         memset(dpb, 0, sizeof(dpb));         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。             dpe[i] = max(dpe[i-1], de[i]);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。             dpb[i] = max(dpb[i+1], db[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点             ans = max(ans, dpe[i]+dpb[i+1]);         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//优化:变递推为迭代 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, ans, mn, mx, a[N], dpe[N], dpb[N]; int main() {     scanf("%d", &amp;t);     while(t--)     {         memset(dpe, 0, sizeof(dpe));         memset(dpb, 0, sizeof(dpb));         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             dpe[i] = max(dpe[i-1], a[i] - mn);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             dpb[i] = max(dpb[i+1], mx - a[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。         }         ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点             ans = max(ans, dpe[i]+dpb[i+1]);         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2: #include&lt;bits/stdc++.h&gt; using namespace std; #define N 100005 #define INF 0x3f3f3f3f int t, n, mn, mx, mxde, ans, a[N], de[N], db[N]; int main() {     scanf("%d", &amp;t);     while(t--)     {         scanf("%d", &amp;n);         for(int i = 1; i &lt;= n; ++i)             scanf("%d", &amp;a[i]);         mn = a[1];         for(int i = 1; i &lt;= n; ++i)         {             mn = min(mn, a[i]);             de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。         }         mx = a[n];         for(int i = n; i &gt;= 1; --i)         {             mx = max(mx, a[i]);             db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。         }         mxde = ans = -INF;//ans:原序列中不相交的两个区间的区间差值加和的最大值          for(int i = 1; i &lt; n; ++i)//枚举分割点         {             mxde = max(mxde, de[i]);//mxde为第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。              ans = max(ans, mxde + db[i+1]);         }         printf("%d\n", ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;string&gt; #include&lt;cstdlib&gt; #include&lt;queue&gt; #include&lt;vector&gt; #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 100001 #define MOD 100001 #define E 1e-12 using namespace std; int a[N],f1[N],f2[N]; int main() {     int t,ans;     scanf("%d",&amp;t);     while(t--)     {         int n;         scanf("%d",&amp;n);         for(int i=1;i&lt;=n;i++)             scanf("%d",&amp;a[i]);           int minn=INF,maxx=-INF;         f1[0]=0;         f2[n+1]=0;         for(int i=1;i&lt;=n;i++)         {             minn=min(minn,a[i]);             f1[i]=max(f1[i-1],a[i]-minn);         }         for(int i=n;i&gt;=1;i--)         {             maxx=max(maxx,a[i]);             f2[i]=max(f2[n+1],maxx-a[i]);         }           int ans=-INF;         for(int i=1;i&lt;=n;i++)             ans=max(ans,f1[i]+f2[i]);         printf("%d\n",ans);     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法4 动态规划 #include &lt;bits/stdc++.h&gt;   using namespace std;  int t,n,w[100005],dp[1000005][2]; int main() { cin&gt;&gt;t;//测试案例的数量 int k=2;//最大买卖次数 while(t--){ cin&gt;&gt;n; for(int i=1;i&lt;=n;i++) cin&gt;&gt;w[i]; memset(dp,0,sizeof(dp));//将f数组的所有元素置为0 for(int i=0;i&lt;=k;i++) dp[i][1]=-1e6;//将f[j][1]列中的所有元素置为负无穷大 for(int i=1;i&lt;=n;i++) for(int j=1;j&lt;=k;j++){ //第j次购入股票 dp[j][0]=max(dp[j][0],dp[j][1]+w[i]); //第j次抛售股票 dp[j][1]=max(dp[j][1],dp[j-1][0]-w[i]); } cout&lt;&lt;dp[k][0]&lt;&lt;endl; } return 0; }</pre>
这道题暂未补解析。