2022年CSP-J初赛真题及答案解析(阅读程序2)
2022年CSP-J初赛真题及答案解析(阅读程序2)
第 2 题
1#include<algorithm>2#include<iostream>3#include<limits>45usingnamespacestd;67constintMAXN=105;8constintMAXK=105;910inth[MAXN][MAXK];1112intf(intn,intm)13{14if(m==1)returnn;15if(n==0)return0;1617intret=numeric_limits<int>::max();18for(inti=1;i<=n;i++)19ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);20returnret;21}2223intg(intn,intm)24{25for(inti=1;i<=n;i++)26h[i][1]=i;27for(intj=1;j<=m;j++)28h[0][j]=0;2930for(inti=1;i<=n;i++){31for(intj=2;j<=m;j++){32h[i][j]=numeric_limits<int>::max();33for(intk=1;k<=i;k++)34h[i][j]=min(35h[i][j],36max(h[i-k][j],h[k-1][j-1])+1);37}38}3940returnh[n][m];41}4243intmain()44{45intn,m;46cin>>n>>m;47cout<<f(n,m)<<endl<<g(n,m)<<endl;48return0;49}假设输入的 n、m 均是不超过 100 的正整数，完成下面的判断题和单选题：
判断题
- 当输入为 7 3 时，第 19 行用来取最小值的 min 函数执行了 449 次。
- 输出的两行整数总是相同的。
- 当 m 为 1 时，输出的第一行总为 n。
单选题 - 算法 g(n,m) 最为准确的时间复杂度分析结果为（ ）。
A.O ( n 3 / 2 m ) O(n^{3/2}m)O(n3/2m)
B. O(nm)
C. O(n²m)
D. O(nm²) - 当输入为 20 2 时，输出的第一行为（ ）。
A. 4
B. 5
C. 6
D. 20
6.（4分）当输入 100 100 时，输出的第一行为（ ）。
A. 6
B. 7
C. 8
D. 9
答案：
- B（错误）
- A（正确）
- A（正确）
- C（O(n²m)）
- C（6）
- B（7）
解析：
该程序计算鸡蛋掉落问题（n个楼层，m个鸡蛋，最坏情况下最少测试次数）。f和g均实现同一递推。第19行min执行次数为Σ i = 1.. n i = n ( n + 1 ) / 2 Σ_{i=1..n} i = n(n+1)/2Σi=1..ni=n(n+1)/2，当 n=7 时为 28，不是449，故1错。g有三重循环（i,j,k）时间复杂度 O(n²m)。已知鸡蛋掉落经典结果：m=2时，测试次数为 ceil((√(8n+1)-1)/2)，n=20 时结果6。n=100,m=100时，由于鸡蛋数大于 log₂(n+1)，最少次数为 ceil(log₂(n+1)) = 7。
更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}