2025年信息学能力竞赛题库及答案

2025年信息学能力竞赛题库及答案一、单项选择题（每题2分，共30分）1.在C++中，若定义inta=3,b=4;则表达式(a^b)<<2的值为A.12  B.28  C.56  D.20答案：B解析：a^b为7，7<<2即7×4=28。2.一棵有n个节点的二叉树，其最小高度为A.⌊log₂n⌋  B.⌈log₂(n+1)⌉−1  C.n−1  D.⌊log₂(n+1)⌋答案：B解析：完全二叉树高度公式。3.对长度为n的序列进行归并排序，最坏情况下时间复杂度为A.O(n)  B.O(nlogn)  C.O(n²)  D.O(logn)答案：B解析：归并排序始终O(nlogn)。4.在Linux下，将标准错误重定向到文件err.log，正确写法是A.2>err.log  B.1>err.log  C.&2>err.log  D.err.log2>答案：A解析：文件描述符2代表标准错误。5.以下哪个算法不能用于求解单源最短路径A.Dijkstra  B.Bellman-Ford  C.Floyd  D.SPFA答案：C解析：Floyd是多源最短路径算法。6.若哈希表长m=16，采用二次探测，则第3次探测的偏移量为A.3  B.5  C.9  D.11答案：C解析：二次探测序列1²,2²,3²…，第3次偏移9。7.在C++17中，结构化绑定可用于A.array  B.tuple  C.vector  D.stack答案：B解析：结构化绑定支持tuple、pair、结构体等。8.以下哪个不是动态规划的必要条件A.最优子结构  B.无后效性  C.重叠子问题  D.贪心选择答案：D解析：贪心选择是贪心策略特征。9.对一棵AVL树插入节点后，最先失去平衡的最小子树根节点称为A.祖先  B.根  C.临界节点  D.叶子答案：C解析：AVL旋转定义。10.在Python3中，表达式(1,2)2的结果是A.(1,2,1,2)  B.[1,2,1,2]  C.(2,4)  D.报错答案：A解析：元组乘法为重复拼接。11.若图G有n个顶点、e条边，则其邻接矩阵空间复杂度为A.O(n+e)  B.O(n²)  C.O(e²)  D.O(nlogn)答案：B解析：n×n矩阵。12.以下哪个排序算法是原地排序且稳定A.快速排序  B.归并排序  C.堆排序  D.冒泡排序答案：D解析：冒泡排序稳定且原地。13.在C++中，若模板参数推导失败，可使用的关键字是A.typename  B.template  C.decltype  D.concept答案：D解析：C++20concept用于约束模板。14.对长度为n的01串，求最长连续1子段，允许最多k次翻转0→1，最优算法复杂度为A.O(nk)  B.O(nlogn)  C.O(n)  D.O(k²n)答案：C解析：双指针滑动窗口。15.在x86-64汇编中，调用函数时第4个整型参数通过哪个寄存器传递A.rdi  B.rsi  C.rdx  D.rcx答案：D解析：SystemVAMD64ABI规定。二、不定项选择题（每题3分，共15分，多选少选均不得分）16.以下哪些操作会使Linux文件描述符变为非阻塞A.fcntl(fd,F_SETFL,O_NONBLOCK)  B.ioctl(fd,FIONBIO,&on)  C.open时用O_NONBLOCK  D.epoll_ctl加EPOLLET答案：ABC解析：D仅边缘触发，不改变fd属性。17.关于Trie树，正确的是A.插入复杂度O(字符串长度)  B.可共享前缀  C.一定比哈希表快  D.支持前缀查询答案：ABD解析：C错误，哈希常数可能更小。18.以下哪些C++容器提供强异常安全保证A.vector  B.list  C.unordered_map  D.array答案：ABC解析：array无动态分配，异常安全默认。19.在计算几何中，判断点是否在凸多边形内可用A.射线法  B.转角和法  C.二分法  D.叉积同号法答案：ABD解析：C仅对凸多边形二分边界。20.以下哪些算法可用于生成1~n的随机排列A.Fisher-Yates  B.std::shuffle  C.rand()%n循环插入  D.堆排序答案：AB解析：C有偏，D与随机排列无关。三、程序阅读题（每题5分，共20分）21.```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){intn=12,m=5;n^=m^=n^=m;cout<<n<<""<<m<<endl;return0;}```输出：512解析：经典三异或交换。22.```cppintf(intx){returnx==1?1:(x&1?f(x3+1)+1:f(x>>1)+1);}cout<<f(3);```输出：8解析：3→10→5→16→8→4→2→1，共8步。23.```pythondeffoo(s):st=[]forchins:ifch=='(':st.append(ch)elifch==')':ifnotst:returnFalsest.pop()returnlen(st)==0print(foo("(()())(())"))```输出：True解析：括号匹配。24.```cppvector<int>a{3,1,4,1,5};nth_element(a.begin(),a.begin()+2,a.end());cout<<a[2];```输出：3解析：nth_element使第2大元素就位。四、程序填空题（每空3分，共15分）25.给定长为n的数组a，求最长严格递增子序列长度，O(nlogn)算法。```cppintlis(vector<int>&a){vector<int>g;for(intx:a){autoit=lower_bound(g.begin(),g.end(),x);if(it==g.end())g.push_back(x);elseit=x;}returng.size();}```填空：lower_bound26.并查集路径压缩模板```cppintfind(intx){returnfa[x]==x?x:fa[x]=find(fa[x]);}```填空：fa[x]=find(fa[x])27.快速幂求a^bmodp```cpplonglongqpow(longlonga,longlongb,longlongp){longlongr=1;while(b){if(b&1)r=ra%p;a=aa%p;b>>=1;}returnr;}```填空：b>>=128.线段树区间加，延迟标记```cppvoidpushdown(into,intl,intm,intr){if(add[o]){add[o<<1]+=add[o];add[o<<1|1]+=add[o];sum[o<<1]+=add[o](m-l+1);sum[o<<1|1]+=add[o](r-m);add[o]=0;}}```填空：add[o]=029.字典序第k小排列```cppstringkth(intn,longlongk){strings;vector<int>v;for(inti=1;i<=n;i++)v.push_back(i);k--;for(inti=n;i>=1;i--){longlongf=1;for(intj=2;j<i;j++)f=j;intt=k/f;s+=char('0'+v[t]);v.erase(v.begin()+t);k%=f;}returns;}```填空：v.erase(v.begin()+t)五、算法设计题（共40分）30.（10分）给定n≤1e5个区间[lᵢ,rᵢ]，求最小数量点，使每个区间至少包含一个点。解：按右端点升序排序，贪心选当前区间右端点，若下一区间左端点大于当前点则新增点。伪代码：```cppsort(segs,[](auto&a,auto&b){returna.r<b.r;});intpos=-2e9,ans=0;for(auto&z:segs)if(z.l>pos){ans++;pos=z.r;}```复杂度：O(nlogn)31.（15分）给定长为n的排列p，每次可交换相邻两数，求将排列变为升序的最少交换次数。解：逆序对数即为答案，用归并排序求逆序对。代码：```cpplonglonginv(vector<int>&a,vector<int>&tmp,intl,intr){if(l>=r)return0;intm=(l+r)>>1;longlongs=inv(a,tmp,l,m)+inv(a,tmp,m+1,r);inti=l,j=m+1,k=l;while(i<=m&&j<=r)if(a[i]<=a[j])tmp[k++]=a[i++];else{tmp[k++]=a[j++];s+=m-i+1;}while(i<=m)tmp[k++]=a[i++];while(j<=r)tmp[k++]=a[j++];for(i=l;i<=r;i++)a[i]=tmp[i];returns;}```32.（15分）给定n≤5000，求将n表示为若干个不同的2的幂次之和的方案数mod1e9+7。解：等价于n的二进制表示中1的位选或不选，但需不同，故唯一方案即二进制本身，但若允许顺序不同则转化为拆分问题。设f[i][j]表示考虑前i个幂次，总和为j的方案数，转移：f[i][j]=f[i−1][j]+f[i−1][j−2ⁱ](j≥2ⁱ)初始f[0][0]=1，答案f[∞][n]。优化：仅对i≤log₂n，复杂度O(nlogn)。代码：```cppconstintMOD=1e9+7;intf[5005];f[0]=1;for(inti=0;(1<<i)<=n;i++)for(intj=n;j>=(1<<i);j--)f[j]=(f[j]+f[j-(1<<i)])%MOD;cout<<f[n];```六、综合应用题（共30分）33.（10分）网络流：给定n个点m条边的有向图，每条边容量下界为1上界为c，求从s到t的最小可行流。解：上下界网络流，建超级源汇，跑一遍可行流，再在残留网络上求s→t最小流。步骤：1.原边u→v，下界1，上界c，拆为：必流1，附加流0~c−1。2.新建S,T，统计每个点入下界−出下界，若>0则S→i差值，若<0则i→T差值。3.跑S→T最大流，若<S出边总和则无解。4.在残留网络上求t→s最大流，最小可行流=下界和−t→s最大流。34.（10分）字符串：给定长n≤1e6的文本s与模式t，|t|≤n，求t在s中出现的所有起始位置，允许k≤5次错配。解：按字符集分块bitset，逐位验证。对t的每个位置i，预处理掩码M[c][i]表示s中字符c在模512块内出现情况。枚举起始位置j，按块验证汉明距离≤k，若块内超k则剪枝。复杂度：O(n·|t|/512·|Σ|)，实际跑得快。35.（10分）交互题：隐藏一个1~n的排列，你最多询问2n次，每次询问一个子集S，返回S中逆序对数。求整个排列。解：分治+归并信息。先询问全集得总逆序对T。对位置区间[l,r]，若长度1则已知；否则二分中点m，询问[l,m]与[m+1,r]得A、B，则跨区间逆序对=T−A−B。用双指针归并思想，根据跨区逆序对数可推断左右部分相对顺序，递归还原。询问次数：T(n)=2T(n/2)+2⇒2n−2。七、编程实现题（共50分）36.（20分）题目：给定n≤2×10⁵个点的树，边权为1，q≤2×10⁵次询问，每次求u,v间距离。要求：在线读入，1秒内存256MB。解：LCA+深度数组，用欧拉序+ST表O(1)查询。代码：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=2e5+5,L=18;intdep[N],st[L][N2],dfn[N],lg[N2],tot;vector<int>g[N];voiddfs(intu,intfa){dfn[u]=++tot;st[0][tot]=u;dep[u]=dep[fa]+1;for(intv:g[u])if(v!=fa){dfs(v,u);st[0][++tot]=u;}}intmini(intx,inty){returndep[x]<dep[y]?x:y;}voidbuild(){dfs(1,0);for(inti=2;i<=tot;i++)lg[i]=lg[i>>1]+1;for(intj=1;j<L;j++)for(inti=1;i+(1<<j)-1<=tot;i++)st[j][i]=mini(st[j-1][i],st[j-1][i+(1<<(j-1))]);}intlca(intu,intv){intl=dfn[u],r=dfn[v];if(l>r)swap(l,r);intk=lg[r-l+1];returnmini(st[k][l],st[k][r-(1<<k)+1]);}intdist(intu,intv){returndep[u]+dep[v]-2dep[lca(u,v)];}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,q;cin>>n>>q;for(inti=1;i<n;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}build();while(q--){intu,v;cin>>u>>v;cout<<dist(u,v)<<'\n';}return0;}```37.（30分）题目：给定n≤1e6个非负整数aᵢ≤1e9，求所有连续子段异或和恰好等于k≤1e9的区间个数。要求：O(n)或O(nlogw)。解：前缀异或+哈希表。设s₀=0，sᵢ=sᵢ₋₁⊕aᵢ，则区间[l,r]异或和=sᵣ⊕sₗ₋₁。问题转化为求有序对(i,j)满足sⱼ⊕sᵢ=k且i<j。用unordered_map<longlong,int>cnt统计前缀出现次数，遍历j时，ans+=cnt[sⱼ⊕k]，再cnt[sⱼ]++。注意开longlong，处理k=0特判。代码：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;inta[N];unordered_map<int,longlong>cnt;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,k;cin>>n>>k;for(inti=1;i<=n;i++)cin>>a[i];longlongans=0;ints=0;cnt[0]=1;for(inti=1;i<=n;i++){s^=a[i];ans+=cnt[s^k];cnt[s]++;}cout<<ans;return0;}```八、附加挑战题（共20分）38.（20分）题目：给定n≤1e5个点的DAG，边权为1，q≤1e5次询问，每次给定s,t，求从s到t的不同最短路径数mod1e9+7。解：按拓扑序DP。先BFS求出s到各点最短距离d[u]。建按d分层图，仅保留d[v]=d[u]+1的边，得到DAG。按拓扑序递推f[u]表示s→u最短路径数，初始f[s]=1，转移f[v]+=f[u]。预处理所有s需反向思考，但q大，需离线。改为：对每个询问(sᵢ,tᵢ)，若d[tᵢ]≠−1则答案为g[tᵢ]，其中g数组按全局拓扑序递推。但s不同则d不同，无法共用。优化：反向建图，以t为起点BFS得反向距离，再对询问按s分组，离线处理。具体：1.反向图BFS求各点到t的最短距离，记为dst[u]。2.对询问(s,t)，若dst[s]+dst[t]≠dst[s]则无解，否则需统计s→t最短路径数。3.按dst分层，正向拓扑序DP，f[u]表示u→t最短路径数，初始f[t]=1，逆拓扑转移f[u]+=f[v]。4.对每个询问，答案=f[s]。复杂度：O((n+q)logn)建图+拓扑。代码：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=1e5+5,MOD=1e9+7;vector<int>og[N],rg[N];intd[N],f[N],deg[N],q[N],hd,tl;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m,Q;cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;og[u].push_back(v);rg[v].push_back(u);}cin>>Q;vector<tuple<int,int,int>>qs;for(inti=0;i<Q;i++){ints,t;cin>>s