2025年程序設(shè)計試題及答案一、字符變換問題給定兩個由小寫字母組成的字符串s和t，以及一個允許替換對的集合R（每個元素為(x,y)，表示可以將字符x替換為y）。每次操作可以選擇以下三種之一：1.插入一個任意小寫字母；2.刪除一個字符；3.替換字符，但僅當(dāng)(x,y)∈R時，可將x替換為y。要求計算將s轉(zhuǎn)換為t所需的最小操作次數(shù)，若無法轉(zhuǎn)換則輸出-1。輸入格式第一行包含字符串s和t（長度均不超過500）。第二行包含整數(shù)m（1≤m≤26），表示R中替換對的數(shù)量。接下來m行，每行兩個字符x和y，表示(x,y)∈R。輸出格式輸出一個整數(shù)，為最小操作次數(shù)或-1。樣例輸入abcadc1bd樣例輸出1解答本題是編輯距離問題的變種，核心是動態(tài)規(guī)劃。定義dp[i][j]為將s的前i個字符轉(zhuǎn)換為t的前j個字符的最小操作次數(shù)。狀態(tài)轉(zhuǎn)移如下：插入操作：dp[i][j]=dp[i][j-1]+1（在s前i個字符后插入t[j-1]）。刪除操作：dp[i][j]=dp[i-1][j]+1（刪除s的第i個字符）。替換操作：若s[i-1]可替換為t[j-1]（即(s[i-1],t[j-1])∈R），則dp[i][j]=dp[i-1][j-1]+1；否則無法通過替換操作轉(zhuǎn)移。初始化：dp[0][j]=j（插入j次），dp[i][0]=i（刪除i次）。最終答案為dp[len(s)][len(t)]，若其值超過可能范圍（如兩字符串長度差超過500）則輸出-1。代碼（C++）```cppinclude<iostream>include<vector>include<string>include<unordered_set>usingnamespacestd;intmain(){strings,t;intm;cin>>s>>t>>m;unordered_set<int>replace;for(inti=0;i<m;++i){charx,y;cin>>x>>y;replace.insert((x'a')26+(y'a'));}intn=s.size(),k=t.size();vector<vector<int>>dp(n+1,vector<int>(k+1,1e9));dp[0][0]=0;for(inti=0;i<=n;++i)dp[i][0]=i;for(intj=0;j<=k;++j)dp[0][j]=j;for(inti=1;i<=n;++i){for(intj=1;j<=k;++j){dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);if(s[i-1]==t[j-1]){dp[i][j]=min(dp[i][j],dp[i-1][j-1]);}elseif(replace.count((s[i-1]-'a')26+(t[j-1]-'a'))){dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);}}}cout<<(dp[n][k]>1000?-1:dp[n][k])<<endl;return0;}```二、城市交通優(yōu)化問題有n個城市（編號1~n），m條雙向道路。每條道路連接u和v，長度為l，且僅在每天的[start,end)時間段開放（單位：分鐘，0≤start<end≤1440）。從城市1出發(fā)，出發(fā)時間為T分鐘，求到達(dá)每個城市（2~n）的最早時間，無法到達(dá)則輸出-1。輸入格式第一行包含n、m、T（n≤1e5，m≤2e5）。接下來m行，每行包含u、v、l、start、end（u≠v）。輸出格式輸出n-1個整數(shù)，依次為城市2到n的最早到達(dá)時間。樣例輸入331012582013205152351225樣例輸出1520解答使用Dijkstra算法的變種，優(yōu)先隊列存儲（到達(dá)時間，城市），維護(hù)每個城市的最早到達(dá)時間。對于當(dāng)前到達(dá)城市u的時間t，遍歷其所有道路：若道路開放時間為[start,end)，則出發(fā)時間需滿足t≤出發(fā)時間<end。若t<start，需等待到start出發(fā)；若t≥start且t<end，可立即出發(fā)。到達(dá)城市v的時間為出發(fā)時間+l。若該時間小于v的當(dāng)前最早時間，則更新并加入優(yōu)先隊列。代碼（C++）```cppinclude<iostream>include<vector>include<queue>include<climits>usingnamespacestd;usingPII=pair<int,int>;structEdge{intto,l,start,end;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m,T;cin>>n>>m>>T;vector<vector<Edge>>adj(n+1);for(inti=0;i<m;++i){intu,v,l,s,e;cin>>u>>v>>l>>s>>e;adj[u].push_back({v,l,s,e});adj[v].push_back({u,l,s,e});}vector<int>dist(n+1,INT_MAX);dist[1]=T;priority_queue<PII,vector<PII>,greater<PII>>pq;pq.emplace(T,1);while(!pq.empty()){auto[t,u]=pq.top();pq.pop();if(t>dist[u])continue;for(auto&edge:adj[u]){intv=edge.to,l=edge.l;ints=edge.start,e=edge.end;intdepart;if(t<s)depart=s;elseif(t<e)depart=t;elsecontinue;intarrive=depart+l;if(arrive<dist[v]){dist[v]=arrive;pq.emplace(arrive,v);}}}for(inti=2;i<=n;++i){cout<<(dist[i]==INT_MAX?-1:dist[i])<<"";}return0;}```三、區(qū)間顏色覆蓋問題初始有一個長度為n的數(shù)組，所有元素初始顏色為0。進(jìn)行q次操作：1.覆蓋操作：輸入l、r、c（1≤l≤r≤n），將區(qū)間[l,r]內(nèi)的所有位置顏色改為c。2.查詢操作：輸入x（1≤x≤n），輸出位置x被覆蓋的次數(shù)（每次覆蓋操作若包含x則計數(shù)+1）。輸入格式第一行包含n和q（n≤1e5，q≤1e5）。接下來q行，每行第一個數(shù)為操作類型（1或2）：類型1后接l、r、c；類型2后接x。輸出格式對于每個查詢操作，輸出結(jié)果。樣例輸入54113112422322樣例輸出22解答使用線段樹，每個節(jié)點(diǎn)維護(hù)覆蓋次數(shù)cnt和覆蓋標(biāo)記color（-1表示無統(tǒng)一顏色）。覆蓋操作時，若當(dāng)前區(qū)間完全包含在[l,r]內(nèi)，則cnt加1并設(shè)置color；否則下傳標(biāo)記后遞歸處理子區(qū)間。查詢時遞歸到葉子節(jié)點(diǎn)，累加路徑上的cnt。代碼（C++）```cppinclude<iostream>include<vector>usingnamespacestd;structNode{intcnt=0;intcolor=-1;};classSegmentTree{vector<Node>tree;intn;voidpush(intnode,intl,intr){if(tree[node].color!=-1&&l!=r){intmid=(l+r)/2;tree[2node].cnt+=tree[node].cnt;tree[2node].color=tree[node].color;tree[2node+1].cnt+=tree[node].cnt;tree[2node+1].color=tree[node].color;tree[node].cnt=0;tree[node].color=-1;}}voidupdate(intnode,intl,intr,intul,intur,intc){if(ur<l||ul>r)return;if(ul<=l&&r<=ur){tree[node].cnt++;tree[node].color=c;return;}push(node,l,r);intmid=(l+r)/2;update(2node,l,mid,ul,ur,c);update(2node+1,mid+1,r,ul,ur,c);}intquery(intnode,intl,intr,intx){if(l==r)returntree[node].cnt;push(node,l,r);intmid=(l+r)/2;if(x<=mid)returnquery(2node,l,mid,x);elsereturnquery(2node+1,mid+1,r,x);}public:SegmentTree(intsize){n=size;tree.resize(4n);}voidupdate(intl,intr,intc){update(1,1,n,l,r,c);}intquery(intx){returnquery(1,1,n,x);}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,q;cin>>n>>q;SegmentTreest(n);while(q--){intop;cin>>op;if(op==1){intl,r,c;cin>>l>>r>>c;st.update(l,r,c);}else{intx;cin>>x;cout<<st.query(x)<<'\n';}}return0;}```四、數(shù)位統(tǒng)計問題給定正整數(shù)n和k（n≤1e18，k≤1e3），求1到n中各位數(shù)字之和是k的倍數(shù)的數(shù)的個數(shù)（模1e9+7）。輸入格式第一行包含n和k。輸出格式輸出一個整數(shù)，為符合條件的數(shù)的個數(shù)模1e9+7。樣例輸入203樣例輸出3解答使用數(shù)位動態(tài)規(guī)劃，狀態(tài)為pos（當(dāng)前處理位）、sum（當(dāng)前數(shù)字和模k）、tight（是否受n限制）、lead（前導(dǎo)零）。記憶化搜索計算滿足條件的數(shù)的個數(shù)。代碼（C++）```cppinclude<iostream>include<vector>include<cstring>usingnamespacestd;usingll=longlong;constintMOD=1e9+7;structState{intpos,sum,tight,lead;booloperator==(constState&other)const{returnpos==other.pos&&sum==other.sum&&tight==other.tight&&lead==other.lead;}};namespacestd{template<>structhash<State>{size_toperator()(constState&s)const{returns.pos^(s.sum<<5)^(s.tight<<10)^(s.lead<<11);}};}classDigitDP{strings;intk;unordered_map<State,int>memo;intdfs(intpos,intsum,booltight,boollead){if(pos==s.size()){return(!lead&&sum%k==0)?1:0;}Statestate{pos,sum,tight,lead};