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

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

第 3 题

#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn=1000000+5;constintP1=998244353,P2=1000000007;constintB1=2,B2=31;constintK1=0,K2=13;typedeflonglongll;intn;boolp[maxn];intp1[maxn],p2[maxn];structH{inth1,h2,l;H(boolb=false){h1=b+K1;h2=b+K2;l=1;}Hoperator+(constH&h)const{H hh;hh.l=l+h.l;hh.h1=(1ll*h1*p1[h.l]+h.h1)%P1;hh.h2=(1ll*h2*p2[h.l]+h.h2)%P2;returnhh;}booloperator==(constH&h)const{returnl==h.l&&h1==h.h1&&h2==h.h2;}booloperator<(constH&h)const{if(l!=h.l)returnl<h.l;elseif(h1!=h.h1)returnh1<h.h1;elsereturnh2<h.h2;}}h[maxn];voidinit(){memset(p,1,sizeof(p));p[0]=p[1]=false;p1[0]=p2[0]=1;for(inti=1;i<=n;++i){p1[i]=(1ll*B1*p1[i-1])%P1;p2[i]=(1ll*B2*p2[i-1])%P2;if(!p[i])continue;for(intj=2*i;j<=n;j+=i){p[j]=false;}}}intsolve(){for(inti=n;i;--i){h[i]=H(p[i]);if(2*i+1<=n){h[i]=h[2*i]+h[i]+h[2*i+1];}elseif(2*i<=n){h[i]=h[2*i]+h[i];}}cout<<h[1].h1<<endl;sort(h+1,h+n+1);intm=unique(h+1,h+n+1)-(h+1);returnm;}intmain(){cin>>n;init();cout<<solve()<<endl;}

判断题

1. 假设程序运行前能自动将maxn改为n+1，所实现的算法的时间复杂度是 O(nlog⁡n)。（ ）

   A. 正确 B. 错误

2. 时间开销的瓶颈是init()函数。（ ）

   A. 正确 B. 错误

3. 若修改常数B1或K1的值，该程序可能会输出不同的结果。（ ）

   A. 正确 B. 错误

选择题

1. 在solve()函数中，h[]的合并顺序可以看作是（ ）？

   A. 二叉树的 BFS 序 B. 二叉树的先序遍历 C. 二叉树的中序遍历 D. 二叉树的后序遍历

2. 输入 10，输出的第一行是？（ ）

   A. 83 B. 424 C. 54 D. 110101000

3. 输入 16，输出的第二行是？（ ）

   A. 7 B. 9 C. 10 D. 12

题解

程序分析

该程序实现了一个基于双哈希的子树哈希计算算法，主要步骤包括：

1. 初始化：使用筛法标记1到n中的质数，并预计算两个基数的幂（模P1和P2）。
2. 子树哈希计算：从n到1逆序遍历节点，将每个节点视为一棵二叉树的根（左子为2*i，右子为2*i+1），计算该子树的中序遍历字符串的双哈希值。
3. 输出：第一行输出根节点h[1]的第一个哈希分量h1；第二行输出所有子树哈希值中不同值的个数。

判断题解析

1. 时间复杂度
   程序包含三部分：

   • init()：筛法复杂度为O(n log log n)，预计算幂为O(n)。
   • solve()：遍历和合并哈希为O(n)。
   • 排序h数组为O(n log n)。
     总时间复杂度由排序主导，为O(n log n)，故正确。

2. 对于较大的n，排序的O(n log n)远大于init()的O(n log log n)，因此瓶颈在排序而非init()，故错误。

3. B1和K1直接影响哈希值的计算，改变它们可能导致不同的哈希结果，从而影响输出，故正确。

选择题解析

1. 对于节点i，合并操作为h[2*i] + h[i] + h[2*i+1]，对应二叉树的中序遍历（左子树 → 根 → 右子树），故选C。

2. 模拟计算得h[1].h1 = 83，故选A。

3. 所有子树的中序遍历字符串共有 10 种不同的值，故不同哈希值的个数为 10，故选C。

---

专栏推荐：信奥赛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;}