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

2024年信奥赛C提高组csp-s初赛真题及答案解析阅读程序第3题第 3 题#includeiostream#includecstring#includealgorithmusingnamespacestd;constintmaxn10000005;constintP1998244353,P21000000007;constintB12,B231;constintK10,K213;typedeflonglongll;intn;boolp[maxn];intp1[maxn],p2[maxn];structH{inth1,h2,l;H(boolbfalse){h1bK1;h2bK2;l1;}Hoperator(constHh)const{H hh;hh.llh.l;hh.h1(1ll*h1*p1[h.l]h.h1)%P1;hh.h2(1ll*h2*p2[h.l]h.h2)%P2;returnhh;}booloperator(constHh)const{returnlh.lh1h.h1h2h.h2;}booloperator(constHh)const{if(l!h.l)returnlh.l;elseif(h1!h.h1)returnh1h.h1;elsereturnh2h.h2;}}h[maxn];voidinit(){memset(p,1,sizeof(p));p[0]p[1]false;p1[0]p2[0]1;for(inti1;in;i){p1[i](1ll*B1*p1[i-1])%P1;p2[i](1ll*B2*p2[i-1])%P2;if(!p[i])continue;for(intj2*i;jn;ji){p[j]false;}}}intsolve(){for(intin;i;--i){h[i]H(p[i]);if(2*i1n){h[i]h[2*i]h[i]h[2*i1];}elseif(2*in){h[i]h[2*i]h[i];}}couth[1].h1endl;sort(h1,hn1);intmunique(h1,hn1)-(h1);returnm;}intmain(){cinn;init();coutsolve()endl;}判断题假设程序运行前能自动将maxn改为n1所实现的算法的时间复杂度是 O(nlog⁡n)。 A. 正确 B. 错误时间开销的瓶颈是init()函数。 A. 正确 B. 错误若修改常数B1或K1的值该程序可能会输出不同的结果。 A. 正确 B. 错误选择题在solve()函数中h[]的合并顺序可以看作是 A. 二叉树的 BFS 序 B. 二叉树的先序遍历 C. 二叉树的中序遍历 D. 二叉树的后序遍历输入 10输出的第一行是 A. 83 B. 424 C. 54 D. 110101000输入 16输出的第二行是 A. 7 B. 9 C. 10 D. 12题解程序分析该程序实现了一个基于双哈希的子树哈希计算算法主要步骤包括初始化使用筛法标记1到n中的质数并预计算两个基数的幂模P1和P2。子树哈希计算从n到1逆序遍历节点将每个节点视为一棵二叉树的根左子为2*i右子为2*i1计算该子树的中序遍历字符串的双哈希值。输出第一行输出根节点h[1]的第一个哈希分量h1第二行输出所有子树哈希值中不同值的个数。判断题解析时间复杂度程序包含三部分init()筛法复杂度为O(n log log n)预计算幂为O(n)。solve()遍历和合并哈希为O(n)。排序h数组为O(n log n)。总时间复杂度由排序主导为O(n log n)故正确。对于较大的n排序的O(n log n)远大于init()的O(n log log n)因此瓶颈在排序而非init()故错误。B1和K1直接影响哈希值的计算改变它们可能导致不同的哈希结果从而影响输出故正确。选择题解析对于节点i合并操作为h[2*i] h[i] h[2*i1]对应二叉树的中序遍历左子树 → 根 → 右子树故选C。模拟计算得h[1].h1 83故选A。所有子树的中序遍历字符串共有 10 种不同的值故不同哈希值的个数为 10故选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 点击跳转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;}