2024年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

2024年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

第 2 题

#include<iostream>#include<string>usingnamespacestd;constintP=998244353,N=1e4+10,M=20;intn,m;string s;intdp[1<<M];intsolve(){dp[0]=1;for(inti=0;i<n;++i){for(intj=(1<<(m-1))-1;j>=0;--j){intk=(j<<1)|(s[i]-'0');if(j!=0||s[i]=='1')dp[k]=(dp[k]+dp[j])%P;}}intans=0;for(inti=0;i<(1<<m);++i){ans=(ans+1ll*i*dp[i])%P;}returnans;}intsolve2(){intans=0;for(inti=0;i<(1<<n);++i){intcnt=0;intnum=0;for(intj=0;j<n;++j){if(i&(1<<j)){num=num*2+(s[j]-'0');cnt++;}}if(cnt<=m)(ans+=num)%=P;}returnans;}intmain(){cin>>n>>m;cin>>s;if(n<=20){cout<<solve2()<<endl;}cout<<solve()<<endl;return0;}

假设输入的 s是包含 n个字符的 01 串，完成下面的判断题和单选题。

判断题

1. 假设数组 dp 长度无限制，函数solve()所实现的算法的时间复杂度是 O(n×2 m 2^m2m)。（ ）

   A. 正确 B. 错误

2. 输入11 2 10000000001时，程序输出两个数 32 和 23。（ ）

   A. 正确 B. 错误

3. （2 分）在 n≤10 时，solve()的返回值始终小于 410 ^{10}10。（ ）

   A. 正确 B. 错误

选择题

1. 当 n=10 且 m=10 时，有多少种输入使得两行的结果完全一致？（ ）

   A. 1024 B. 11 C. 10 D. 0

2. 当 n≤6时，solve()的最大可能返回值为（ ）？

   A. 65 B. 211 C. 665 D. 2059

3. 若 n=8,m=8，solve和solve2的返回值的最大可能的差值为（ ）？

   A. 1477 B. 1995 C. 2059 D. 2187

判断题答案与解析

1. 正确
   solve()中外层循环遍历n次，内层循环遍历2^(m-1)次，总时间复杂度为O(n × 2^m)。
2. 正确
   对于输入11 2 10000000001，计算得solve2()返回 32，solve()返回 23，程序依次输出这两个数。
3. 正确
   当n ≤ 10时，solve()返回值最大不超过(2^n - 1) × (2^n - 1) = 1023 × 1023 = 1046529，小于4^10 = 1048576。

选择题答案与解析

1. B. 11
   两函数结果一致当且仅当字符串s单调不增（所有'1'在前，'0'在后）。对于n = 10，这样的字符串有11种（'1'的个数可以是0到10）。
2. C. 665
   当n ≤ 6时，solve()的最大返回值在s全为'1'且m = n时取得。n = 6时，最大值为3^6 - 2^6 = 729 - 64 = 665。
3. 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

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、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

2、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.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}