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個節(jié)點的二叉樹，其最小高度為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(n2)??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解析：二次探測序列12,22,32…，第3次偏移9。7.在C++17中，結構化綁定可用于A.array??B.tuple??C.vector??D.stack答案：B解析：結構化綁定支持tuple、pair、結構體等。8.以下哪個不是動態(tài)規(guī)劃的必要條件A.最優(yōu)子結構??B.無后效性??C.重疊子問題??D.貪心選擇答案：D解析：貪心選擇是貪心策略特征。9.對一棵AVL樹插入節(jié)點后，最先失去平衡的最小子樹根節(jié)點稱為A.祖先??B.根??C.臨界節(jié)點??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(n2)??C.O(e2)??D.O(nlogn)答案：B解析：n×n矩陣。12.以下哪個排序算法是原地排序且穩(wěn)定A.快速排序??B.歸并排序??C.堆排序??D.冒泡排序答案：D解析：冒泡排序穩(wěn)定且原地。13.在C++中，若模板參數(shù)推導失敗，可使用的關鍵字是A.typename??B.template??C.decltype??D.concept答案：D解析：C++20concept用于約束模板。14.對長度為n的01串，求最長連續(xù)1子段，允許最多k次翻轉0→1，最優(yōu)算法復雜度為A.O(nk)??B.O(nlogn)??C.O(n)??D.O(k2n)答案：C解析：雙指針滑動窗口。15.在x86-64匯編中，調用函數(shù)時第4個整型參數(shù)通過哪個寄存器傳遞A.rdi??B.rsi??C.rdx??D.rcx答案：D解析：SystemVAMD64ABI規(guī)定。二、不定項選擇題（每題3分，共15分，多選少選均不得分）16.以下哪些操作會使Linux文件描述符變?yōu)榉亲枞鸄.fcntl(fd,F_SETFL,O_NONBLOCK)??B.ioctl(fd,FIONBIO,&on)??C.open時用O_NONBLOCK??D.epoll_ctl加EPOLLET答案：ABC解析：D僅邊緣觸發(fā)，不改變fd屬性。17.關于Trie樹，正確的是A.插入復雜度O(字符串長度)??B.可共享前綴??C.一定比哈希表快??D.支持前綴查詢答案：ABD解析：C錯誤，哈希常數(shù)可能更小。18.以下哪些C++容器提供強異常安全保證A.vector??B.list??C.unordered_map??D.array答案：ABC解析：array無動態(tài)分配，異常安全默認。19.在計算幾何中，判斷點是否在凸多邊形內可用A.射線法??B.轉角和法??C.二分法??D.叉積同號法答案：ABD解析：C僅對凸多邊形二分邊界。20.以下哪些算法可用于生成1~n的隨機排列A.Fisher-Yates??B.std::shuffle??C.rand()%n循環(huá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解析：經(jīng)典三異或交換。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的數(shù)組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.線段樹區(qū)間加，延遲標記```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個區(qū)間[l?,r?]，求最小數(shù)量點，使每個區(qū)間至少包含一個點。解：按右端點升序排序，貪心選當前區(qū)間右端點，若下一區(qū)間左端點大于當前點則新增點。偽代碼：```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，每次可交換相鄰兩數(shù)，求將排列變?yōu)樯虻淖钌俳粨Q次數(shù)。解：逆序對數(shù)即為答案，用歸并排序求逆序對。代碼：```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的冪次之和的方案數(shù)mod1e9+7。解：等價于n的二進制表示中1的位選或不選，但需不同，故唯一方案即二進制本身，但若允許順序不同則轉化為拆分問題。設f[i][j]表示考慮前i個冪次，總和為j的方案數(shù)，轉移：f[i][j]=f[i?1][j]+f[i?1][j?2?](j≥2?)初始f[0][0]=1，答案f[∞][n]。優(yōu)化：僅對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分）網(wǎng)絡流：給定n個點m條邊的有向圖，每條邊容量下界為1上界為c，求從s到t的最小可行流。解：上下界網(wǎng)絡流，建超級源匯，跑一遍可行流，再在殘留網(wǎng)絡上求s→t最小流。步驟：1.原邊u→v，下界1，上界c，拆為：必流1，附加流0~c?1。2.新建S,T，統(tǒng)計每個點入下界?出下界，若>0則S→i差值，若<0則i→T差值。3.跑S→T最大流，若<S出邊總和則無解。4.在殘留網(wǎng)絡上求t→s最大流，最小可行流=下界和?t→s最大流。34.（10分）字符串：給定長n≤1e6的文本s與模式t，|t|≤n，求t在s中出現(xiàn)的所有起始位置，允許k≤5次錯配。解：按字符集分塊bitset，逐位驗證。對t的每個位置i，預處理掩碼M[c][i]表示s中字符c在模512塊內出現(xiàn)情況。枚舉起始位置j，按塊驗證漢明距離≤k，若塊內超k則剪枝。復雜度：O(n·|t|/512·|Σ|)，實際跑得快。35.（10分）交互題：隱藏一個1~n的排列，你最多詢問2n次，每次詢問一個子集S，返回S中逆序對數(shù)。求整個排列。解：分治+歸并信息。先詢問全集得總逆序對T。對位置區(qū)間[l,r]，若長度1則已知；否則二分中點m，詢問[l,m]與[m+1,r]得A、B，則跨區(qū)間逆序對=T?A?B。用雙指針歸并思想，根據(jù)跨區(qū)逆序對數(shù)可推斷左右部分相對順序，遞歸還原。詢問次數(shù)：T(n)=2T(n/2)+2?2n?2。七、編程實現(xiàn)題（共50分）36.（20分）題目：給定n≤2×10?個點的樹，邊權為1，q≤2×10?次詢問，每次求u,v間距離。要求：在線讀入，1秒內存256MB。解：LCA+深度數(shù)組，用歐拉序+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個非負整數(shù)a?≤1e9，求所有連續(xù)子段異或和恰好等于k≤1e9的區(qū)間個數(shù)。要求：O(n)或O(nlogw)。解：前綴異或+哈希表。設s?=0，s?=s???⊕a?，則區(qū)間[l,r]異或和=s?⊕s???。問題轉化為求有序對(i,j)滿足s?⊕s?=k且i<j。用unordered_map<longlong,int>cnt統(tǒng)計前綴出現(xiàn)次數(shù)，遍歷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;}```八、附加挑戰(zhàn)題（共20分）38.（20分）題目：給定n≤1e5個點的DAG，邊權為1，q≤1e5次詢問，每次給定s,t，求從s到t的不同最短路徑數(shù)mod1e9+7。解：按拓撲序DP。先BFS求出s到各點最短距離d[u]。建按d分層圖，僅保留d[v]=d[u]+1的邊，得到DAG。按拓撲序遞推f[u]表示s→u最短路徑數(shù)，初始f[s]=1，轉移f[v]+=f[u]。預處理所有s需反向思考，但q大，需離線。改為：對每個詢問(s?,t?)，若d[t?]≠?1則答案為g[t?]，其中g數(shù)組按全局拓撲序遞推。但s不同則d不同，無法共用。優(yōu)化：反向建圖，以t為起點BFS得反向距離，再對詢問按s分組，離線處理。具體：1.反向圖BFS求各點到t的最短距離，記為dst[u]。2.對詢問(s,t)，若dst[s]+dst[t]≠dst[s]則無解，否則需統(tǒng)計s→t最短路徑數(shù)。3.按dst分層，正向拓撲序DP，f[u]表示u→t最短路徑數(shù)，初始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