2022年CSP-J初赛真题及答案解析(阅读程序2)第 2 题1#includealgorithm2#includeiostream3#includelimits45usingnamespacestd;67constintMAXN105;8constintMAXK105;910inth[MAXN][MAXK];1112intf(intn,intm)13{14if(m1)returnn;15if(n0)return0;1617intretnumeric_limitsint::max();18for(inti1;in;i)19retmin(ret,max(f(n-i,m),f(i-1,m-1))1);20returnret;21}2223intg(intn,intm)24{25for(inti1;in;i)26h[i][1]i;27for(intj1;jm;j)28h[0][j]0;2930for(inti1;in;i){31for(intj2;jm;j){32h[i][j]numeric_limitsint::max();33for(intk1;ki;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;46cinnm;47coutf(n,m)endlg(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. 4B. 5C. 6D. 206.4分当输入 100 100 时输出的第一行为 。A. 6B. 7C. 8D. 9答案B错误A正确A正确CO(n²m)C6B7解析该程序计算鸡蛋掉落问题n个楼层m个鸡蛋最坏情况下最少测试次数。f和g均实现同一递推。第19行min执行次数为Σ i 1.. n i n ( n 1 ) / 2 Σ_{i1..n} i n(n1)/2Σi1..nin(n1)/2当 n7 时为 28不是449故1错。g有三重循环i,j,k时间复杂度 O(n²m)。已知鸡蛋掉落经典结果m2时测试次数为 ceil((√(8n1)-1)/2)n20 时结果6。n100,m100时由于鸡蛋数大于 log₂(n1)最少次数为 ceil(log₂(n1)) 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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}