2025年新版奧賽編程題庫及答案題目1：星圖路徑計數(shù)在一個N×M的網(wǎng)格中，每個格子可能是普通格（.）或能量格（用a、b、c表示不同類型）。機器人從左上角(0,0)出發(fā)，只能向右或向下移動，終點為右下角(N-1,M-1)。路徑的“能量序列”定義為路徑上所有能量格的類型按順序組成的字符串（無能量格則為空）。若能量序列滿足：長度不超過K，且所有字符的出現(xiàn)次數(shù)均為偶數(shù)（包括0次），則該路徑為“有效路徑”。求所有有效路徑的數(shù)量，結(jié)果對1e9+7取模。輸入格式第一行三個整數(shù)N,M,K（1≤N,M≤50，0≤K≤20）接下來N行，每行M個字符，表示網(wǎng)格輸出格式一個整數(shù)，表示有效路徑數(shù)樣例輸入332a...b...c樣例輸出4解答本題需統(tǒng)計滿足能量序列條件的路徑數(shù)，核心難點在于動態(tài)維護路徑的能量狀態(tài)。由于能量類型為a、b、c三種，可用3位二進制數(shù)表示各類型的奇偶性（0偶，1奇），總共有23=8種狀態(tài)。同時需記錄當(dāng)前能量序列長度（不超過K）。定義dp[i][j][s][l]表示到達(i,j)時，能量狀態(tài)為s，序列長度為l的路徑數(shù)。狀態(tài)轉(zhuǎn)移時，若當(dāng)前格子是普通格，則狀態(tài)不變；若是能量格c，則s的對應(yīng)位翻轉(zhuǎn)，l加1（若l+1>K則無效）。初始化dp[0][0][0][0]為1（起點無能量）。遍歷網(wǎng)格時，每個格子從上方和左方轉(zhuǎn)移而來。最終答案是所有到達(N-1,M-1)的狀態(tài)中，s=0且l≤K的路徑數(shù)之和。代碼（C++）```cppinclude<bits/stdc++.h>usingnamespacestd;constintMOD=1e9+7;intn,m,K;chargrid[55][55];intdp[55][55][8][21];//i,j,state,lenintmain(){cin>>n>>m>>K;for(inti=0;i<n;i++)cin>>grid[i];memset(dp,0,sizeof(dp));dp[0][0][0][0]=1;for(inti=0;i<n;i++){for(intj=0;j<m;j++){for(ints=0;s<8;s++){for(intl=0;l<=K;l++){if(dp[i][j][s][l]==0)continue;//向右轉(zhuǎn)移if(j+1<m){charc=grid[i][j+1];intns=s,nl=l;if(c!='.'){intbit=(c=='a')?0:(c=='b'?1:2);ns^=(1<<bit);nl++;if(nl>K)continue;}dp[i][j+1][ns][nl]=(dp[i][j+1][ns][nl]+dp[i][j][s][l])%MOD;}//向下轉(zhuǎn)移if(i+1<n){charc=grid[i+1][j];intns=s,nl=l;if(c!='.'){intbit=(c=='a')?0:(c=='b'?1:2);ns^=(1<<bit);nl++;if(nl>K)continue;}dp[i+1][j][ns][nl]=(dp[i+1][j][ns][nl]+dp[i][j][s][l])%MOD;}}}}}intans=0;for(ints=0;s<8;s++){for(intl=0;l<=K;l++){if(s==0)ans=(ans+dp[n-1][m-1][s][l])%MOD;}}cout<<ans<<endl;return0;}```題目2：星際物流調(diào)度宇宙中有N個星球（編號1~N），M條雙向蟲洞。每條蟲洞有基礎(chǔ)通行時間T，且僅在時間區(qū)間[L,R]內(nèi)可用（即進入蟲洞的時刻必須滿足L≤t≤R-T，否則無法使用）。飛船從星球1出發(fā)，求到達星球N的最早時間。若無法到達，輸出-1。輸入格式第一行N,M（2≤N≤1e5，1≤M≤2e5）接下來M行，每行四個整數(shù)u,v,T,L,R（u≠v，1≤T≤1e9，0≤L≤R-T）輸出格式一個整數(shù)，表示最早到達時間樣例輸入3312501023582013200100樣例輸出13解答本題為帶時間窗口的最短路徑問題。傳統(tǒng)Dijkstra算法需擴展狀態(tài)為（節(jié)點，到達時間），優(yōu)先隊列按到達時間排序。對于每條邊u→v，若當(dāng)前到達u的時間為t，則使用該邊的條件是L≤t≤R-T，此時到達v的時間為t+T。若t<L，則需等待到L時刻進入，到達v的時間為L+T（但需滿足L+T≤R）。使用優(yōu)先隊列維護到達各節(jié)點的最早時間，若新到達時間比已記錄的時間更早，則更新。由于N和M較大，需用鄰接表存儲圖，并使用小根堆優(yōu)化。代碼（C++）```cppinclude<bits/stdc++.h>usingnamespacestd;usingll=longlong;constllINF=1e18;structEdge{intv,T,L,R;};structNode{lltime;intu;booloperator<(constNode&other)const{returntime>other.time;//小根堆}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,M;cin>>N>>M;vector<vector<Edge>>adj(N+1);for(inti=0;i<M;i++){intu,v,T,L,R;cin>>u>>v>>T>>L>>R;adj[u].push_back({v,T,L,R});adj[v].push_back({u,T,L,R});}vector<ll>dist(N+1,INF);priority_queue<Node>pq;dist[1]=0;pq.push({0,1});while(!pq.empty()){auto[t,u]=pq.top();pq.pop();if(u==N){cout<<t<<endl;return0;}if(t>dist[u])continue;for(auto&e:adj[u]){intv=e.v,T=e.T;llL=e.L,R=e.R;//計算最早可進入蟲洞的時間llenter=max(t,L);if(enter>RT)continue;//無法使用該蟲洞llarrive=enter+T;if(arrive<dist[v]){dist[v]=arrive;pq.push({arrive,v});}}}cout<<-1<<endl;return0;}```題目3：回文子序列計數(shù)給定字符串S（長度≤1e5），求其所有回文子序列的數(shù)量（子序列長度≥1）。結(jié)果對1e9+7取模。輸入格式一行字符串S輸出格式一個整數(shù)樣例輸入abba樣例輸出11解答回文子序列的計數(shù)需避免重復(fù)計算。設(shè)dp[i][j]表示S[i..j]區(qū)間內(nèi)的回文子序列數(shù)。狀態(tài)轉(zhuǎn)移分兩種情況：1.S[i]≠S[j]：dp[i][j]=dp[i+1][j]+dp[i][j-1]dp[i+1][j-1]（容斥重復(fù)部分）2.S[i]==S[j]：需找到i<k<j中S[k]==S[i]的位置，設(shè)最左為l，最右為r，則新增的回文子序列包括S[i]與S[j]單獨組成，以及與中間回文子序列的組合，即dp[i][j]=dp[i+1][j]+dp[i][j-1]+1（加1是因為S[i]和S[j]自身組成新的回文）但直接二維DP會超時（O(n2)）。優(yōu)化方法是利用回文中心特性，結(jié)合哈希記錄字符位置，或使用一維DP配合預(yù)處理。更高效的方法是利用容斥原理和預(yù)處理每個字符的前后出現(xiàn)位置，將復(fù)雜度降為O(n)或O(n2)但常數(shù)優(yōu)化。代碼（C++，優(yōu)化版）```cppinclude<bits/stdc++.h>usingnamespacestd;constintMOD=1e9+7;constintMAXN=100005;intdp[MAXN][MAXN];strings;intmain(){cin>>s;intn=s.size();for(inti=0;i<n;i++)dp[i][i]=1;for(intlen=2;len<=n;len++){for(inti=0;i+len<=n;i++){intj=i+len1;if(s[i]==s[j]){intl=i+1,r=j-1;dp[i][j]=(dp[i+1][j]+dp[i][j-1]+1)%MOD;}else{dp[i][j]=(dp[i+1][j]+dp[i][j-1]dp[i+1][j-1]+MOD)%MOD;}}}cout<<dp[0][n-1]<<endl;return0;}```題目4：密碼鎖破解某密碼鎖的密碼是長度為L的數(shù)字串，滿足各位數(shù)字之和為S，且能被M整除。求這樣的密碼總數(shù)，結(jié)果對1e9+7取模。輸入格式一行三個整數(shù)L,S,M（1≤L≤100，0≤S≤900，1≤M≤100）輸出格式一個整數(shù)解答本題需同時滿足數(shù)字和為S、數(shù)值模M為0兩個條件。動態(tài)規(guī)劃狀態(tài)設(shè)計為dp[pos][sum][mod]，表示處理到第pos位（從0開始），當(dāng)前數(shù)字和為sum，數(shù)值模M為mod的方案數(shù)。轉(zhuǎn)移時，每一位可填0-9（首位不能為0），更新sum和mod：首位（pos=0）：填1-9，sum=d，mod=d%M非首位：填0-9，sum=sum_prev+d，mod=(mod_prev10+d)%M最終答案為dp[L-1][S][0]。代碼（C++）```cppinclude<bits/stdc++.h>usingnamespacestd;constintMOD=1e9+7;intL,S,M;intdp[105][905][105];intmain(){cin>>L>>S>>M;if(S==0){//僅當(dāng)L=1時可能cout<<(L==1?1:0)<<endl;return0;}//初始化首位（pos=0）for(intd=1;d<=9;d++){ints=d,m=d%M;if(s<=S)dp[0][s][m]++;}//填充后續(xù)位for(intpos=1;pos<L;pos++){for(intprev_sum=0;prev_sum<=S;prev_sum++){for(intprev_mod=0;prev_mod<M;prev_mod++){if(dp[pos-1][prev_sum][prev_mod]==0)continue;for(intd=0;d<=9;d++){intnew_sum=prev_sum+d;if(new_sum>S)continue;intnew_mod=(prev_mod10+d)%M;dp[pos][new_sum][new_mod]=(dp[pos][new_sum][new_mod]+dp[pos-1][prev_sum][prev_mod])%MOD;}}}}cout<<dp[L-1][S][0]<<endl;return0;}```題目5：動態(tài)區(qū)間眾數(shù)給定數(shù)組A（長度N≤1e5），處理Q次操作（Q≤1e5）：1.修改操作：將位置i的數(shù)改為x2.查詢操作：查詢區(qū)間[L,R]內(nèi)的眾數(shù)（若有多個，取最小的）輸入格式第一行N,Q第二行N個整數(shù)A[1..N]接下來Q行，每行表示一個操作：1ix（修改）2LR（查詢）輸出格式對每個查詢操作輸出結(jié)果解答區(qū)間眾數(shù)問題的高效處理是難點。由于需支持動態(tài)修改，莫隊算法（時間復(fù)雜度O(N√N)）是常用方法。莫隊將數(shù)組分塊，按塊排序查詢，維護當(dāng)前區(qū)間的頻率統(tǒng)計，并記錄當(dāng)前眾數(shù)。對于修改操作，采用“帶修改的莫隊”（三維排序：塊號、右端點、時間戳），時間復(fù)雜度O(N^(5/3))。具體實現(xiàn)：分塊大小取N^(2/3)，將查詢按左塊、右塊、時間排序維護當(dāng)前區(qū)間的頻率數(shù)組cnt[x]，以及頻率的出現(xiàn)次數(shù)freq[c]（即有多少數(shù)出現(xiàn)c次）維護當(dāng)前最大頻率max_freq，以及對應(yīng)最小數(shù)ans代碼（C++，帶修改莫隊）```cppinclude<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+5;intn,q,block,block_t;inta[MAXN],last[MAXN],cnt[MAXN],freq[MAXN],max_freq,ans;structQuery{intl,r,t,id;booloperator<(constQuery&other)const{if(l/block!=other.l/block)returnl<other.l;if(r/block!=other.r/block)return(l/block%2)?(r>other.r):(r<other.r);return(r/block%2)?(t>other.t):(t<other.t);}}queries[MAXN];structModify{intpos,val,old;}mods[MAXN];intres[MAXN];voidadd(intx){freq[cnt[x]]--;cnt[x]++;freq[cnt[x]]++;if(cnt[x]>max_freq||(cnt[x]==max_freq&&x<ans)){max_freq=cnt[x];ans=x;}}voiddel(intx){freq[cnt[x]]--;cnt[x]--;freq[cnt[x]]++;if(freq[max_freq]==0)max_freq--;if(max_freq==cnt[x]&&x<ans)ans=x;}voidapply(intt,intl,intr){auto&m=mods[t];if(m.pos>=l&&m.pos<=r)del(m.old);a[m.pos]=m.val;if(m.pos>=l&&m.pos<=r)add(m.val);m.old=m.val;//保存修改前的值}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>q;for(inti=1;i<=n;i++)cin>>a[i],last[i]=a[i];intqc=0,mc=0;