2024年信奥赛C提高组csp-s初赛真题及答案解析阅读程序第2题第 2 题#includeiostream#includestringusingnamespacestd;constintP998244353,N1e410,M20;intn,m;string s;intdp[1M];intsolve(){dp[0]1;for(inti0;in;i){for(intj(1(m-1))-1;j0;--j){intk(j1)|(s[i]-0);if(j!0||s[i]1)dp[k](dp[k]dp[j])%P;}}intans0;for(inti0;i(1m);i){ans(ans1ll*i*dp[i])%P;}returnans;}intsolve2(){intans0;for(inti0;i(1n);i){intcnt0;intnum0;for(intj0;jn;j){if(i(1j)){numnum*2(s[j]-0);cnt;}}if(cntm)(ansnum)%P;}returnans;}intmain(){cinnm;cins;if(n20){coutsolve2()endl;}coutsolve()endl;return0;}假设输入的 s是包含 n个字符的 01 串完成下面的判断题和单选题。判断题假设数组 dp 长度无限制函数solve()所实现的算法的时间复杂度是 O(n×2 m 2^m2m)。 A. 正确 B. 错误输入11 2 10000000001时程序输出两个数 32 和 23。 A. 正确 B. 错误2 分在 n≤10 时solve()的返回值始终小于 410 ^{10}10。 A. 正确 B. 错误选择题当 n10 且 m10 时有多少种输入使得两行的结果完全一致 A. 1024 B. 11 C. 10 D. 0当 n≤6时solve()的最大可能返回值为 A. 65 B. 211 C. 665 D. 2059若 n8,m8solve和solve2的返回值的最大可能的差值为 A. 1477 B. 1995 C. 2059 D. 2187判断题答案与解析正确solve()中外层循环遍历n次内层循环遍历2^(m-1)次总时间复杂度为O(n × 2^m)。正确对于输入11 2 10000000001计算得solve2()返回 32solve()返回 23程序依次输出这两个数。正确当n ≤ 10时solve()返回值最大不超过(2^n - 1) × (2^n - 1) 1023 × 1023 1046529小于4^10 1048576。选择题答案与解析B. 11两函数结果一致当且仅当字符串s单调不增所有1在前0在后。对于n 10这样的字符串有11种1的个数可以是0到10。C. 665当n ≤ 6时solve()的最大返回值在s全为1且m n时取得。n 6时最大值为3^6 - 2^6 729 - 64 665。C. 2059差值D solve2() - solve()的最大值在s为0后跟7个1时取得此时D (3^7 - 2^7) × (2^1 - 1) 2059。专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、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.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}