2020年信奥赛C提高组csp-s初赛真题及答案解析阅读程序第3题第3题#includeiostream#includequeueusingnamespacestd;constintmaxl20000000;classMap{structitem{string key;intvalue;}d[maxl];intcnt;public:intfind(string x){for(inti0;icnt;i)if(d[i].keyx)returnd[i].value;return-1;}staticintend(){return-1;}voidinsert(string k,intv){d[cnt].keyk;d[cnt].valuev;}}s[2];classQueue{string q[maxl];inthead,tail;public:voidpop(){head;}stringfront(){returnq[head1];}boolempty(){returnheadtail;}voidpush(string x){q[tail]x;}}q[2];string st0,st1;intm;stringLtoR(string s,intL,intR){string ts;chartmpt[L];for(intiL;iR;i)t[i]t[i1];t[R]tmp;returnt;}stringRtoL(string s,intL,intR){string ts;chartmpt[R];for(intiR;iL;--i)t[i]t[i-1];t[L]tmp;returnt;}boolcheck(string st,intp,intstep){if(s[p].find(st)!s[p].end())returnfalse;step;if(s[p^1].find(st)s[p].end()){s[p].insert(st,step);q[p].push(st);returnfalse;}couts[p^1].find(st)stependl;returntrue;}intmain(){cinst0st1;intlenst0.length();if(len!st1.length()){cout-1endl;return0;}if(st0st1){cout0endl;return0;}cinm;s[0].insert(st0,0);s[1].insert(st1,0);q[0].push(st0);q[1].push(st1);for(intp0;!(q[0].empty()q[1].empty());p^1){string stq[p].front();q[p].pop();intsteps[p].find(st);if((p0(check(LtoR(st,m,len-1),p,step)||check(RtoL(st,0,m),p,step)))||(p1(check(LtoR(st,0,m),p,step)||check(RtoL(st,m,len-1),p,step))))return0;}cout-1endl;return0;}判断题输出可能为 0。 A. 正确 B. 错误若输入的两个字符串长度均为 101 时则 m0 时的输出与 m100时的输出是一样的。 A. 正确 B. 错误若两个字符串的长度均为 n则最坏情况下此程序的时间复杂度为 O(n!)。 A. 正确 B. 错误单选题2.5 分若输入的第一个字符串长度由 100 个不同的字符构成第二个字符串是第一个字符串的倒序输入的 m为 0则输出为 。A. 49B. 50C. 100D. -14 分己知当输入为0123\n3210\n1时输出为 4当输入为012345\n543210\n1时输出为 14当输入为01234567\n76543210\n1时输出为 28则当输入为0123456789ab\nba9876543210\nl输出为( )。其中\n为换行符。A. 56B. 84C. 102D. 684 分若两个字符串的长度均为 n且 0mn−1且两个字符串的构成相同即任何一个字符在两个字符串中出现的次数均相同则下列说法正确的是 。提示考虑输入与输出有多少对字符前后顺序不一样。A. 若 n,m 均为奇数则输出可能小于 0。B. 若 n,m 均为偶数则输出可能小于 0。C. 若 n 为奇数、m为偶数则输出可能小于 0。D. 若 n 为偶数、m为奇数则输出可能小于 0。题目分析本题程序实现了一个双向 BFS从起始字符串st0和目标字符串st1同时搜索每一步允许对固定区间进行循环左移或右移。两个区间由参数m决定正向p0对区间[m, len-1]左移和[0, m]右移反向p1对区间[0, m]左移和[m, len-1]右移。搜索直到两方向相遇或队列为空输出最短步数或 -1。判断题答案及解析输出可能为 0。程序首先判断st0 st1若相等则直接输出 0因此可能输出 0。选A。若输入的两个字符串长度均为 101则 m0 时的输出与 m100 时的输出是一样的。m0时正向只有整个串左移反向只有整个串右移m100时正向只有整个串右移反向只有整个串左移。对于长度为 101 的字符串若起点和终点互为循环移位则m0时的步数为左移次数km100时的步数为右移次数101-k两者一般不相等除非k 50.5不可能。因此输出不一定相同。选B。若两个字符串的长度均为 n则最坏情况下此程序的时间复杂度为 O(n!)。程序中Map的find操作为线性查找每次查找代价与当前状态数成正比。最坏情况下状态数可达n!例如取m1时可生成所有排列但每次扩展需线性查找总时间复杂度为O((n!)^2)而非O(n!)。选B。单选题答案及解析输入第一个字符串由 100 个不同字符构成第二个是其倒序m0。m0时只能对整个串进行循环移位而倒序一般不是循环移位除非回文但不同字符不可能故无解输出 -1。选D。已知规律输入0123\n3210\n1输出 4012345\n543210\n1输出 1401234567\n76543210\n1输出 28求0123456789ab\nba9876543210\n1的输出。观察得输出与长度n的关系为(n² - 8)/2n4: (16-8)/24n6: (36-8)/214n8: (64-8)/228n12: (144-8)/268选D。若两个字符串长度 n0mn-1字符构成相同则输出可能小于 0 的条件是每个操作为循环移位其奇偶性由区间长度决定区间长度为奇数时操作为偶置换偶数时为奇置换。正向两个操作区间长度分别为n-m和m1反向同理。所有操作均为偶置换的条件是n-m为奇数且m1为奇数即n为奇数、m为偶数。此时只能生成偶排列若起点与终点逆序对奇偶不同则无解。其他情况至少有一个奇操作可调整奇偶通常有解。故选C。专栏推荐信奥赛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;}