2025年程序设计试题及答案

2025年程序设计试题及答案一、字符变换问题给定两个由小写字母组成的字符串s和t，以及一个允许替换对的集合R（每个元素为(x,y)，表示可以将字符x替换为y）。每次操作可以选择以下三种之一：1.插入一个任意小写字母；2.删除一个字符；3.替换字符，但仅当(x,y)∈R时，可将x替换为y。要求计算将s转换为t所需的最小操作次数，若无法转换则输出-1。输入格式第一行包含字符串s和t（长度均不超过500）。第二行包含整数m（1≤m≤26），表示R中替换对的数量。接下来m行，每行两个字符x和y，表示(x,y)∈R。输出格式输出一个整数，为最小操作次数或-1。样例输入abcadc1bd样例输出1解答本题是编辑距离问题的变种，核心是动态规划。定义dp[i][j]为将s的前i个字符转换为t的前j个字符的最小操作次数。状态转移如下：插入操作：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；否则无法通过替换操作转移。初始化：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;}```二、城市交通优化问题有n个城市（编号1~n），m条双向道路。每条道路连接u和v，长度为l，且仅在每天的[start,end)时间段开放（单位：分钟，0≤start<end≤1440）。从城市1出发，出发时间为T分钟，求到达每个城市（2~n）的最早时间，无法到达则输出-1。输入格式第一行包含n、m、T（n≤1e5，m≤2e5）。接下来m行，每行包含u、v、l、start、end（u≠v）。输出格式输出n-1个整数，依次为城市2到n的最早到达时间。样例输入331012582013205152351225样例输出1520解答使用Dijkstra算法的变种，优先队列存储（到达时间，城市），维护每个城市的最早到达时间。对于当前到达城市u的时间t，遍历其所有道路：若道路开放时间为[start,end)，则出发时间需满足t≤出发时间<end。若t<start，需等待到start出发；若t≥start且t<end，可立即出发。到达城市v的时间为出发时间+l。若该时间小于v的当前最早时间，则更新并加入优先队列。代码（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;}```三、区间颜色覆盖问题初始有一个长度为n的数组，所有元素初始颜色为0。进行q次操作：1.覆盖操作：输入l、r、c（1≤l≤r≤n），将区间[l,r]内的所有位置颜色改为c。2.查询操作：输入x（1≤x≤n），输出位置x被覆盖的次数（每次覆盖操作若包含x则计数+1）。输入格式第一行包含n和q（n≤1e5，q≤1e5）。接下来q行，每行第一个数为操作类型（1或2）：类型1后接l、r、c；类型2后接x。输出格式对于每个查询操作，输出结果。样例输入54113112422322样例输出22解答使用线段树，每个节点维护覆盖次数cnt和覆盖标记color（-1表示无统一颜色）。覆盖操作时，若当前区间完全包含在[l,r]内，则cnt加1并设置color；否则下传标记后递归处理子区间。查询时递归到叶子节点，累加路径上的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;}```四、数位统计问题给定正整数n和k（n≤1e18，k≤1e3），求1到n中各位数字之和是k的倍数的数的个数（模1e9+7）。输入格式第一行包含n和k。输出格式输出一个整数，为符合条件的数的个数模1e9+7。样例输入203样例输出3解答使用数位动态规划，状态为pos（当前处理位）、sum（当前数字和模k）、tight（是否受n限制）、lead（前导零）。记忆化搜索计算满足条件的数的个数。代码（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};