2025年信息学奥赛学生选拔试题及答案

2025年信息学奥赛学生选拔试题及答案一、单项选择题（每题3分，共30分）1.在C++中，若定义inta=3,b=4;，则表达式(a^b)<<2的值为A.28  B.56  C.14  D.7答案：A解析：a^b为7，7<<2即7×4=28。2.一棵有n个节点的二叉树，其最小高度为A.⌊log₂n⌋  B.⌈log₂(n+1)⌉−1  C.n−1  D.⌈log₂n⌉答案：B解析：完全二叉树高度公式。3.对长度为10的数组进行归并排序，最坏情况下比较次数为A.34  B.36  C.38  D.40答案：B解析：归并排序比较次数递推式C(n)=2C(n/2)+n−1，C(10)=36。4.以下哪个算法不能在线性时间内求解无向图的双连通分量A.Tarjan  B.Kosaraju  C.DFS一次遍历  D.基于low数组的算法答案：B解析：Kosaraju用于强连通分量，不适用于无向图。5.给定模数m=1e9+7，求(1e9+6)^(1e9+7)modmA.0  B.1  C.m−1  D.2答案：C解析：由费马小定理，a^(m−1)≡1，故a^(m)≡a，a=m−1时得m−1。6.若哈希表大小为16，采用二次探测，则第4次探测的偏移量为A.9  B.16  C.25  D.36答案：A解析：二次探测序列h(k)+i²，i=3时偏移9。7.在32位系统中，以下结构体sizeof值为structS{chara;intb;charc;};A.6  B.8  C.9  D.12答案：D解析：对齐到4字节，总大小12。8.对序列{5,2,7,4,3}进行基数排序（LSD，基数10），第一趟后序列为A.{2,3,4,5,7}  B.{5,2,7,4,3}  C.{2,5,7,4,3}  D.{5,2,3,4,7}答案：B解析：第一趟按个位，原序已按个位有序。9.若FFT长度为2^m，则复数乘法次数为A.O(nlogn)  B.O(n²)  C.O(n)  D.O(logn)答案：A解析：FFT标准复杂度。10.在C++20中，以下哪个关键字用于约束模板参数A.concept  B.requires  C.constraint  D.restrict答案：A解析：concept定义概念。二、程序阅读题（每题6分，共30分）11.```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){intn=15,k=1;while(n){if(n&1)k=2;n>>=1;}cout<<k;}```输出：16解析：统计n二进制中1的个数m，答案为2^m。12.```cppintf(intx){staticintcnt=0;cnt++;returnx>1?f(x/2)+f(x/2):1;}intmain(){cout<<f(8);}```输出：17解析：递归树节点数，f(8)=2f(4)+1=2(2f(2)+1)+1=2(2(2f(1)+1)+1)+1=17。13.```cppinta[10]={0};int&g(intx){returna[x];}intmain(){g(3)=5;g(g(3))=7;cout<<a[5];}```输出：7解析：g(3)返回a[3]引用，a[3]=5；g(g(3))即g(5)，a[5]=7。14.```cpptemplate<intN>structFib{staticconstintv=Fib<N-1>::v+Fib<N-2>::v;};template<>structFib<0>{staticconstintv=0;};template<>structFib<1>{staticconstintv=1;};intmain(){cout<<Fib<10>::v;}```输出：55解析：编译期计算第10项斐波那契数。15.```cppintmain(){vector<int>v={1,2,3,4,5};autoit=find(v.begin(),v.end(),3);rotate(v.begin(),it,v.end());for(intx:v)cout<<x;}```输出：34512解析：rotate将以3为首，原序列循环左移。三、程序填空题（每空4分，共40分）16.给定n×m矩阵，求从(1,1)到(n,m)路径数，只能右或下走，部分格子障碍。```cppinclude<bits/stdc++.h>usingnamespacestd;constintMOD=1e9+7;intn,m,dp[1005][1005];charg[1005][1005];intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>(g[i]+1);dp[1][1]=(g[1][1]=='.');for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){if(g[i][j]==''){dp[i][j]=0;continue;}if(i>1)(dp[i][j]+=dp[i-1][j])%=MOD;if(j>1)(dp[i][j]+=dp[i][j-1])%=MOD;}cout<<dp[n][m];}```空1：dp[1][1]=(g[1][1]=='.');空2：if(g[i][j]==''){dp[i][j]=0;continue;}17.单调栈求柱形图最大矩形面积```cppinclude<bits/stdc++.h>usingnamespacestd;longlongsolve(vector<int>&h){stack<int>st;longlongans=0;h.push_back(0);for(inti=0;i<h.size();i++){while(!st.empty()&&h[st.top()]>h[i]){intH=h[st.top()];st.pop();intL=st.empty()?-1:st.top();ans=max(ans,1LLH(i-L-1));}st.push(i);}returnans;}```空3：h.push_back(0);空4：ans=max(ans,1LLH(i-L-1));18.线段树区间加，区间求和```cppstructNode{longlongsum,add;}tr[1<<20];voidbuild(intp,intl,intr){tr[p].add=0;if(l==r){cin>>tr[p].sum;return;}intmid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;}voidpush_down(intp,intl,intr){if(tr[p].add==0)return;intmid=(l+r)>>1;tr[p<<1].sum+=tr[p].add(mid-l+1);tr[p<<1|1].sum+=tr[p].add(r-mid);tr[p<<1].add+=tr[p].add;tr[p<<1|1].add+=tr[p].add;tr[p].add=0;}```空5：tr[p<<1].sum+=tr[p].add(mid-l+1);空6：tr[p].add=0;19.网络流Dinic算法BFS分层```cppboolbfs(){memset(level,-1,sizeoflevel);queue<int>q;level[S]=0;q.push(S);while(!q.empty()){intu=q.front();q.pop();for(auto&[v,c]:G[u]){if(c&&level[v]==-1){level[v]=level[u]+1;q.push(v);}}}returnlevel[T]!=-1;}```空7：level[v]==-1空8：level[T]!=-120.后缀数组求LCP```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=1e6+6;intn,rk[N],sa[N],oldrk[N],cnt[N],ht[N];boolcmp(inti,intj,intw){returnoldrk[i]==oldrk[j]&&oldrk[i+w]==oldrk[j+w];}voidbuild(string&s){n=s.size();for(inti=0;i<n;i++)sa[i]=i,rk[i]=s[i];for(intw=1;w<n;w<<=1){memcpy(oldrk,rk,sizeofrk);intp=0;for(inti=n-w;i<n;i++)sa[p++]=i;for(inti=0;i<n;i++)if(sa[i]>=w)sa[p++]=sa[i]-w;memset(cnt,0,sizeofcnt);for(inti=0;i<n;i++)cnt[rk[i]]++;for(inti=1;i<max(256,n);i++)cnt[i]+=cnt[i-1];for(inti=n-1;i>=0;i--)rk[sa[--cnt[oldrk[sa[i]]]]]=i;for(inti=0;i<n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?rk[sa[i-1]]:i;}intk=0;for(inti=0;i<n;i++){if(k)k--;while(s[i+k]==s[sa[rk[i]-1]+k])k++;ht[rk[i]]=k;}}```空9：memcpy(oldrk,rk,sizeofrk);空10：ht[rk[i]]=k;四、算法设计题（共100分）21.树链剖分与可持久化线段树（25分）给定一棵n个节点的树，边权为1，q次操作：1.将路径(u,v)上所有点权加c；2.查询路径(u,v)上点权最大值。n,q≤1e5，强制在线。要求：时间O(nlog²n)，空间O(nlogn)。答案：1.树链剖分重链，每条重链建立线段树；2.区间加采用延迟标记，区间最值维护；3.路径跳链时分段查询，合并结果；4.为支持可持久化，对每条重链建立主席树，标记永久化；5.复杂度分析：剖分后链长O(logn)，线段树操作O(logn)，总O(log²n)每次。22.最小费用循环流（25分）给定有向图，边有容量与单位费用，部分节点有供需b_i，求满足供需的最小费用循环。n≤500，m≤5000，费用绝对值≤100。答案：1.建立超级源S汇T，连接供需边；2.转换为最小费用最大流，采用SuccessiveShortestPath；3.使用potentials与Dijkstra找最短增广路；4.复杂度：O(F·(m+nlogn))，F为总流量，可过。23.长回文子串分治+FFT（25分）给定长度n≤1e6的小写字符串，求最长回文子串长度。答案：1.Manacher算法O(n)即可，但题目要求分治+FFT；2.将问题转化为求最大d，使得s[i−d+1..i]与s[j..j+d−1]互为反转；3.定义多项式A(x)=Σs[i]·x^i，B(x)=Σs[n−1−i]·x^i；4.利用FFT计算A与B的卷积，得到所有对齐点的匹配长度；5.分治区间，合并时利用卷积结果，取最大奇偶回文；6.复杂度O(nlogn)。24.三维偏序CDQ分治（25分）给定n个点(x_i,y_i,z_i)，求对于每个点，x_j≤x_i,y_j≤y_i,z_j≤z_i的j个数。n≤1e5，坐标1≤x,y,z≤1e9。答案：1.按x排序，CDQ分治处理y,z；2.分治区间[l,r]，先递归[l,mid]，再处理左对右贡献，再递归[mid+1,r]；3.处理贡献时，将左右按y排序，用树状数组维护z坐标；4.复杂度O(nlog²n)。五、代码实现题（共100分）25.动态树LCT维护子树信息（50分）给定n个节点的森林，支持：1.加边（保证无环）；2.删边；3.查询以u为根的子树节点权值和。n,q≤1e5，权值可修改。参考实现：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,q,op,u,v,w;longlongaux[N],val[N],sum[N];structNode{intch[2],fa,rev;}t[N];definelst[x].ch[0]definerst[x].ch[1]boolisroot(intx){returnt[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}voidpush_up(intx){sum[x]=sum[ls]+sum[rs]+val[x]+aux[x];}voidpush_rev(intx){swap(ls,rs);t[x].rev^=1;}voidpush_down(intx){if(t[x].rev){if(ls)push_rev(ls);if(rs)push_rev(rs);t[x].rev=0;}}voidrotate(intx){inty=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x;if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].fa=z;t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].fa=y;t[x].ch[k^1]=y;t[y].fa=x;push_up(y);push_up(x);}voidsplay(intx){vector<int>stk;inty=x;while(!isroot(y)){stk.push_back(y);y=t[y].fa;}stk.push_back(y);while(stk.size()){push_down(stk.back());stk.pop_back();}while(!isroot(x)){y=t[x].fa;if(!isroot(y))rotate((t[t[y].fa].ch[1]==y)==(t[y].ch[1]==x)?y:x);rotate(x);}}voidaccess(intx){for(inty=0;x;y=x,x=t[x].fa){splay(x);aux[x]+=sum[rs]-sum[y];rs=y;push_up(x);}}voidmakeroot(intx){access(x);splay(x);push_rev(x);}voidsplit(intx,inty){makeroot(x);access(y);splay(y);}voidlink(intx,inty){makeroot(x);access(y);splay(y);t[x].fa=y;aux[y]+=sum[x];push_up(y);}voidcut(intx,inty){split(x,y);t[y].ch[0]=t[x].fa=0;push_up(y);}longlongquery(intx){access(x);splay(x);returnsum[x];}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>q;for(inti=1;i<=n;i++)cin>>val[i],sum[i]=val[i];while(q--){cin>>op;if(op==1){cin>>u>>v;link(u,v);}elseif(op==2){cin>>u>>v;cut(u,v);}