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

2019年信奥赛C提高组csp-s初赛真题及答案解析阅读程序第3题第3题t是 s的子序列的意思是从 s中删去若干个字符可以得到 t特别的如果 st那么 t也是 s 的子序列空串是任何串的子序列。例如acd 是 abcde 的子序列acd 是 acd 的子序列但 adc 不是 abcde 的子序列。s[x…y] 表示 s[x]⋯s[y]共 y−x1个字符构成的字符串若 xy 则 s[x…y] 是空串。t[x…y] 同理。01#includeiostream02#includestring03usingnamespacestd;04constintmax1202;05string s,t;06intpre[max1],suf[max1];0708intmain(){09cinst;10intslens.length(),tlent.length();1112for(inti0,j0;islen;i){13if(jtlens[i]t[j])j;14pre[i]j;// t[0..j-1] 是 s[0..i] 的子序列15}1617for(intislen-1,jtlen-1;i0;--i){18if(j0s[i]t[j])--j;19suf[i]j;// t[j1..tlen-1] 是 s[i..slen-1] 的子序列20}2122suf[slen]tlen-1;23intans0;24for(inti0,j0,tmp0;islen;i){25while(jslentmpsuf[j]1)j;26ansmax(ans,j-i-1);27tmppre[i];28}29coutansendl;30return0;31}提示t[0…pre[i]−1] 是 s[0…i] 的子序列t[suf[i]1…tlen−1]是 s[i…slen−1] 的子序列。判断题1分程序输出时suf数组满足对任意 0≤islen , suf[i] ≤ suf[i1]。 A. 正确 B. 错误2分当 t是 s的子序列时输出一定不为 0。A. 正确 B. 错误2分程序运行到第 23 行时j−i−1一定不小于 0。A. 正确 B. 错误2分当 t是 s的子序列时pre数组和suf数组满足对任意 0≤islen , pre[i] suf[i1]1。 A. 正确 B. 错误选择题若tlen10输出为 0则 slen最小为。A. 10B. 12C. 0D. 1若tlen10输出为 2则 slen最小为。A. 0B. 10C. 12D. 1判断题答案及解析A. 正确suf数组从右向左计算随着索引i增大j只减不增因此suf[i]单调非递减即对任意0≤islen有suf[i] ≤ suf[i1]。B. 错误当t是s的子序列时例如s t此时可删除长度为0输出为0因此输出不一定非零。B. 错误循环中j - i - 1可能为负如i0, j0时得-1虽然最终ans取最大值非负但表达式本身可能小于0。B. 错误反例s t a时pre[0]1suf[1]0有pre[0] suf[1]1不满足严格大于。选择题答案及解析C. 0tlen10输出为0时slen最小可为0空串此时pre和suf计算后ans0。C. 12输出为2表示可删除长度为2的连续子串后剩下部分包含t剩余长度至少为10故slen至少为12且可构造出这样的字符串。专栏推荐信奥赛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 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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;}