2025年新版奥赛编程题库及答案

2025年新版奥赛编程题库及答案题目1：星图路径计数在一个N×M的网格中，每个格子可能是普通格（.）或能量格（用a、b、c表示不同类型）。机器人从左上角(0,0)出发，只能向右或向下移动，终点为右下角(N-1,M-1)。路径的“能量序列”定义为路径上所有能量格的类型按顺序组成的字符串（无能量格则为空）。若能量序列满足：长度不超过K，且所有字符的出现次数均为偶数（包括0次），则该路径为“有效路径”。求所有有效路径的数量，结果对1e9+7取模。输入格式第一行三个整数N,M,K（1≤N,M≤50，0≤K≤20）接下来N行，每行M个字符，表示网格输出格式一个整数，表示有效路径数样例输入332a...b...c样例输出4解答本题需统计满足能量序列条件的路径数，核心难点在于动态维护路径的能量状态。由于能量类型为a、b、c三种，可用3位二进制数表示各类型的奇偶性（0偶，1奇），总共有2³=8种状态。同时需记录当前能量序列长度（不超过K）。定义dp[i][j][s][l]表示到达(i,j)时，能量状态为s，序列长度为l的路径数。状态转移时，若当前格子是普通格，则状态不变；若是能量格c，则s的对应位翻转，l加1（若l+1>K则无效）。初始化dp[0][0][0][0]为1（起点无能量）。遍历网格时，每个格子从上方和左方转移而来。最终答案是所有到达(N-1,M-1)的状态中，s=0且l≤K的路径数之和。代码（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;//向右转移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;}//向下转移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：星际物流调度宇宙中有N个星球（编号1~N），M条双向虫洞。每条虫洞有基础通行时间T，且仅在时间区间[L,R]内可用（即进入虫洞的时刻必须满足L≤t≤R-T，否则无法使用）。飞船从星球1出发，求到达星球N的最早时间。若无法到达，输出-1。输入格式第一行N,M（2≤N≤1e5，1≤M≤2e5）接下来M行，每行四个整数u,v,T,L,R（u≠v，1≤T≤1e9，0≤L≤R-T）输出格式一个整数，表示最早到达时间样例输入3312501023582013200100样例输出13解答本题为带时间窗口的最短路径问题。传统Dijkstra算法需扩展状态为（节点，到达时间），优先队列按到达时间排序。对于每条边u→v，若当前到达u的时间为t，则使用该边的条件是L≤t≤R-T，此时到达v的时间为t+T。若t<L，则需等待到L时刻进入，到达v的时间为L+T（但需满足L+T≤R）。使用优先队列维护到达各节点的最早时间，若新到达时间比已记录的时间更早，则更新。由于N和M较大，需用邻接表存储图，并使用小根堆优化。代码（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：回文子序列计数给定字符串S（长度≤1e5），求其所有回文子序列的数量（子序列长度≥1）。结果对1e9+7取模。输入格式一行字符串S输出格式一个整数样例输入abba样例输出11解答回文子序列的计数需避免重复计算。设dp[i][j]表示S[i..j]区间内的回文子序列数。状态转移分两种情况：1.S[i]≠S[j]：dp[i][j]=dp[i+1][j]+dp[i][j-1]dp[i+1][j-1]（容斥重复部分）2.S[i]==S[j]：需找到i<k<j中S[k]==S[i]的位置，设最左为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(n²)）。优化方法是利用回文中心特性，结合哈希记录字符位置，或使用一维DP配合预处理。更高效的方法是利用容斥原理和预处理每个字符的前后出现位置，将复杂度降为O(n)或O(n²)但常数优化。代码（C++，优化版）```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的数字串，满足各位数字之和为S，且能被M整除。求这样的密码总数，结果对1e9+7取模。输入格式一行三个整数L,S,M（1≤L≤100，0≤S≤900，1≤M≤100）输出格式一个整数解答本题需同时满足数字和为S、数值模M为0两个条件。动态规划状态设计为dp[pos][sum][mod]，表示处理到第pos位（从0开始），当前数字和为sum，数值模M为mod的方案数。转移时，每一位可填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){//仅当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]++;}//填充后续位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：动态区间众数给定数组A（长度N≤1e5），处理Q次操作（Q≤1e5）：1.修改操作：将位置i的数改为x2.查询操作：查询区间[L,R]内的众数（若有多个，取最小的）输入格式第一行N,Q第二行N个整数A[1..N]接下来Q行，每行表示一个操作：1ix（修改）2LR（查询）输出格式对每个查询操作输出结果解答区间众数问题的高效处理是难点。由于需支持动态修改，莫队算法（时间复杂度O(N√N)）是常用方法。莫队将数组分块，按块排序查询，维护当前区间的频率统计，并记录当前众数。对于修改操作，采用“带修改的莫队”（三维排序：块号、右端点、时间戳），时间复杂度O(N^(5/3))。具体实现：分块大小取N^(2/3)，将查询按左块、右块、时间排序维护当前区间的频率数组cnt[x]，以及频率的出现次数freq[c]（即有多少数出现c次）维护当前最大频率max_freq，以及对应最小数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;