第十四次CCFCSP認(rèn)證考試真題2025含答案

第十四次CCFCSP認(rèn)證考試練習(xí)題2025含答案第一題有效子數(shù)組統(tǒng)計(jì)問(wèn)題描述：給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組a和整數(shù)k，統(tǒng)計(jì)所有連續(xù)子數(shù)組中滿足“子數(shù)組最大值與最小值的差的絕對(duì)值不超過(guò)k”的子數(shù)組數(shù)目。輸入格式：第一行包含兩個(gè)整數(shù)n和k（1≤n≤10?，0≤k≤10?）；第二行包含n個(gè)整數(shù)a?,a?,…,a?（1≤a?≤10?）。輸出格式：輸出一個(gè)整數(shù)，表示符合條件的子數(shù)組數(shù)目。樣例輸入：5213254樣例輸出：12解題思路：使用滑動(dòng)窗口法維護(hù)當(dāng)前窗口的最大值和最小值。用雙端隊(duì)列分別存儲(chǔ)當(dāng)前窗口內(nèi)最大值和最小值的索引：右指針r從0到n1遍歷，每次將a[r]加入隊(duì)列，確保最大值隊(duì)列的隊(duì)首是當(dāng)前窗口的最大值（若隊(duì)列尾部元素≤a[r]，則彈出尾部，直到隊(duì)列為空或尾部元素更大）；最小值隊(duì)列同理（若隊(duì)列尾部元素≥a[r]，則彈出尾部）。當(dāng)當(dāng)前窗口的最大值與最小值之差超過(guò)k時(shí)，左指針l右移，并更新隊(duì)列（若隊(duì)列的隊(duì)首是l，則彈出隊(duì)首）。每次右指針移動(dòng)后，當(dāng)前窗口的有效子數(shù)組數(shù)目為rl+1，累加到結(jié)果中。代碼（C++）：```cppinclude<iostream>include<vector>include<deque>usingnamespacestd;intmain(){intn,k;cin>>n>>k;vector<int>a(n);for(inti=0;i<n;++i)cin>>a[i];deque<int>maxq,minq;longlongres=0;intl=0;for(intr=0;r<n;++r){//維護(hù)最大值隊(duì)列while(!maxq.empty()&&a[r]>=a[maxq.back()])maxq.pop_back();maxq.push_back(r);//維護(hù)最小值隊(duì)列while(!minq.empty()&&a[r]<=a[minq.back()])minq.pop_back();minq.push_back(r);//調(diào)整左指針，直到窗口滿足條件while(a[maxq.front()]a[minq.front()]>k){if(maxq.front()==l)maxq.pop_front();if(minq.front()==l)minq.pop_front();l++;}res+=rl+1;}cout<<res<<endl;return0;}```第二題任務(wù)調(diào)度優(yōu)化問(wèn)題描述：有m個(gè)任務(wù)，每個(gè)任務(wù)包含截止時(shí)間d?（完成時(shí)間需≤d?）和耗時(shí)t?（需連續(xù)t?天完成）。每天只能執(zhí)行一個(gè)任務(wù)的一個(gè)步驟（即一個(gè)任務(wù)需占用連續(xù)t?天）。求最多能完成的任務(wù)數(shù)量。輸入格式：第一行包含整數(shù)m（1≤m≤10?）；接下來(lái)m行，每行兩個(gè)整數(shù)d?和t?（1≤t?≤d?≤10?）。輸出格式：輸出能完成的最大任務(wù)數(shù)。樣例輸入：3325342樣例輸出：2解題思路：貪心策略：按截止時(shí)間d?升序排序。維護(hù)當(dāng)前已選任務(wù)的總耗時(shí)sum，并使用大頂堆存儲(chǔ)已選任務(wù)的耗時(shí)。遍歷每個(gè)任務(wù)：若sum+t?≤d?，直接加入，sum+=t?，堆插入t?。否則，若堆頂元素（當(dāng)前已選的最長(zhǎng)耗時(shí)任務(wù)）>t?，則替換（sum=sum堆頂+t?），堆彈出頂并插入t?。最終堆的大小即為最多完成的任務(wù)數(shù)。代碼（C++）：```cppinclude<iostream>include<vector>include<queue>include<algorithm>usingnamespacestd;intmain(){intm;cin>>m;vector<pair<int,int>>tasks(m);for(inti=0;i<m;++i){cin>>tasks[i].first>>tasks[i].second;}sort(tasks.begin(),tasks.end());//按d升序排序priority_queue<int>heap;//大頂堆存已選任務(wù)的tlonglongsum=0;for(auto&task:tasks){intd=task.first,t=task.second;if(sum+t<=d){sum+=t;heap.push(t);}elseif(!heap.empty()&&heap.top()>t){sum=heap.top();sum+=t;heap.pop();heap.push(t);}}cout<<heap.size()<<endl;return0;}```第三題特殊回文子串計(jì)數(shù)問(wèn)題描述：給定字符串s，統(tǒng)計(jì)所有長(zhǎng)度≥2的回文子串中，滿足“子串的首字符和尾字符在原串中的出現(xiàn)次數(shù)均為奇數(shù)”的子串?dāng)?shù)目。輸入格式：輸入一個(gè)僅包含小寫(xiě)字母的字符串s（長(zhǎng)度≤10?）。輸出格式：輸出符合條件的子串?dāng)?shù)目。樣例輸入：ababa樣例輸出：3樣例解釋：符合條件的子串為"aba"（索引02）、"bab"（索引13）、"ababa"（索引04）。解題思路：1.預(yù)處理每個(gè)字符的前綴出現(xiàn)次數(shù)數(shù)組cnt[26][n+1]，其中cnt[c][i]表示前i個(gè)字符中字符c的出現(xiàn)次數(shù)。2.枚舉所有可能的回文子串中心（奇數(shù)長(zhǎng)度中心為字符，偶數(shù)長(zhǎng)度中心為字符間隙），用中心擴(kuò)展法計(jì)算每個(gè)中心的最大回文半徑。3.對(duì)于每個(gè)回文子串，取首尾字符，利用前綴數(shù)組判斷其在原串中的總出現(xiàn)次數(shù)是否為奇數(shù)（即cnt[c][n]%2==1）。若首尾字符均滿足條件，則計(jì)數(shù)加1。代碼（Python）：```pythons=input().strip()n=len(s)ifn<2:print(0)exit()預(yù)處理每個(gè)字符的前綴出現(xiàn)次數(shù)cnt=[[0](n+1)for_inrange(26)]foriinrange(n):c=ord(s[i])ord('a')forjinrange(26):cnt[j][i+1]=cnt[j][i]cnt[c][i+1]+=1計(jì)算每個(gè)字符的總出現(xiàn)次數(shù)是否為奇數(shù)total_odd=[False]26forcinrange(26):total_odd[c]=(cnt[c][n]%2==1)res=0處理奇數(shù)長(zhǎng)度回文（中心為字符）forcenterinrange(n):l,r=center,centerwhilel>=0andr<nands[l]==s[r]:ifrl+1>=2:first_c=ord(s[l])ord('a')last_c=ord(s[r])ord('a')iftotal_odd[first_c]andtotal_odd[last_c]:res+=1l=1r+=1處理偶數(shù)長(zhǎng)度回文（中心為間隙）forcenterinrange(n1):l,r=center,center+1whilel>=0andr<nands[l]==s[r]:ifrl+1>=2:first_c=ord(s[l])ord('a')last_c=ord(s[r])ord('a')iftotal_odd[first_c]andtotal_odd[last_c]:res+=1l=1r+=1print(res)```第四題網(wǎng)格路徑最小值問(wèn)題描述：給定一個(gè)n行m列的網(wǎng)格，每個(gè)格子有正整數(shù)a[i][j]。從左上角(0,0)到右下角(n1,m1)，只能向右或向下移動(dòng)。求所有可能路徑中，路徑上格子值的最大值的最小可能值。輸入格式：第一行包含兩個(gè)整數(shù)n和m（1≤n,m≤500）；接下來(lái)n行，每行m個(gè)整數(shù)表示a[i][j]（1≤a[i][j]≤10?）。輸出格式：輸出這個(gè)最小可能的最大值。樣例輸入：33131151421樣例輸出：2解題思路：動(dòng)態(tài)規(guī)劃。定義dp[i][j]為到達(dá)(i,j)時(shí)路徑上的最大值的最小可能值。狀態(tài)轉(zhuǎn)移方程：dp[i][j]=min(max(dp[i1][j],a[i][j]),max(dp[i][j1],a[i][j]))初始條件：dp[0][0]=a[0][0]，第一行和第一列只能沿單一方向到達(dá)，故dp[0][j]=max(dp[0][j1],a[0][j])，dp[i][0]=max(dp[i1][0],a[i][0])。代碼（C++）：```cppinclude<iostream>include<vector>include<algorithm>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<vector<int>>a(n,vector<int>(m));for(inti=0;i<n;++i){for(intj=0;j<m;++j){cin>>a[i][j];}}vector<vector<int>>dp(n,vector<int>(m));dp[0][0]=a[0][0];//初始化第一行for(intj=1;j<m;++j){dp[0][j]=max(dp[0][j1],a[0][j]);}//初始化第一列for(inti=1;i<n;++i){dp[i][0]=max(dp[i1][0],a[i][0]);}//動(dòng)態(tài)規(guī)劃填充for(inti=1;i<n;++i){for(intj=1;j<m;++j){intfrom_up=max(dp[i1][j],a[i][j]);intfrom_left=max(dp[i][j1],a[i][j]);dp[i][j]=min(from_up,from_left);}}cout<<dp[n1][m1]<<endl;return0;}```第五題有向圖的最早到達(dá)時(shí)間問(wèn)題描述：給定有向圖，n個(gè)節(jié)點(diǎn)m條邊，邊權(quán)為時(shí)間t。每個(gè)節(jié)點(diǎn)u有開(kāi)放時(shí)間s[u]和關(guān)閉時(shí)間e[u]，只能在時(shí)間區(qū)間[s[u],e[u]]內(nèi)進(jìn)入節(jié)點(diǎn)u（到達(dá)u的時(shí)間需滿足該條件）。求從節(jié)點(diǎn)1到節(jié)點(diǎn)n的最早到達(dá)時(shí)間，若無(wú)法到達(dá)則輸出1。輸入格式：第一行包含兩個(gè)整數(shù)n和m（2≤n≤10?，1≤m≤2×10?）；接下來(lái)m行，每行三個(gè)整數(shù)u,v,t（1≤u,v≤n，1≤t≤10?）；最后一行n個(gè)整數(shù)s[1..n]和n個(gè)整數(shù)e[1..n]（0≤s[u]≤e[u]≤101?）。輸出格式：輸出最早到達(dá)時(shí)間，無(wú)法到達(dá)則輸出1。樣例輸入：33121231133000100100100樣例輸出：2樣例解釋：路徑1→2→3：到達(dá)2的時(shí)間為1（在[0,100]內(nèi)），從2出發(fā)時(shí)間為1，到達(dá)3的時(shí)間為2（在[0,100]內(nèi)）。解題思路：Dijkstra算法變種。優(yōu)先隊(duì)列存儲(chǔ)（到達(dá)時(shí)間，節(jié)點(diǎn)），維護(hù)每個(gè)節(jié)點(diǎn)的最早到達(dá)時(shí)間。對(duì)于節(jié)點(diǎn)u，到達(dá)時(shí)間為arrive_u，需滿足s[u]≤arrive_u≤e[u]。從u出發(fā)經(jīng)過(guò)邊u→v（耗時(shí)t）時(shí)，出發(fā)時(shí)間為max(arrive_u,s[u])，到達(dá)v的時(shí)間為出發(fā)時(shí)間+t。若到達(dá)v的時(shí)間≤e[v]，則更新v的最早到達(dá)時(shí)間。代碼（C++）：```cppinclude<iostream>include<vector>include<queue>include<climits>usingnamespacestd;usingll=longlong;constllINF=LLONG_MAX;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<vector<pair<int,ll>>>adj(n+1);//鄰接表，u→(v,t)for(inti=0;i<m;++i){intu,v;llt;cin>>u>>v>>t;adj[u].emplace_back(v,t);}vector<ll>s(n+1),e(n+1);for(inti=1;i<=n;++i)cin>>s[i];for(inti=1;i<=n;++i)cin>>e[i];vector<ll>dist(n+1,INF);dist[1]=0;//初始到達(dá)節(jié)點(diǎn)1的時(shí)間為0？需檢查是否在[s[1],e[1]]內(nèi)if(dist[1]<s[1]||dist[1]>e[1]){//初始無(wú)法進(jìn)入節(jié)點(diǎn)1cout<<1<<endl;return0;}priority_queue<pair<ll,in