第十四次CCFCSP認(rèn)證考試練習(xí)題2025含答案第一題有效子數(shù)組統(tǒng)計問題描述：給定一個長度為n的整數(shù)數(shù)組a和整數(shù)k，統(tǒng)計所有連續(xù)子數(shù)組中滿足“子數(shù)組最大值與最小值的差的絕對值不超過k”的子數(shù)組數(shù)目。輸入格式：第一行包含兩個整數(shù)n和k（1≤n≤10?，0≤k≤10?）；第二行包含n個整數(shù)a?,a?,…,a?（1≤a?≤10?）。輸出格式：輸出一個整數(shù)，表示符合條件的子數(shù)組數(shù)目。樣例輸入：5213254樣例輸出：12解題思路：使用滑動窗口法維護(hù)當(dāng)前窗口的最大值和最小值。用雙端隊列分別存儲當(dāng)前窗口內(nèi)最大值和最小值的索引：右指針r從0到n1遍歷，每次將a[r]加入隊列，確保最大值隊列的隊首是當(dāng)前窗口的最大值（若隊列尾部元素≤a[r]，則彈出尾部，直到隊列為空或尾部元素更大）；最小值隊列同理（若隊列尾部元素≥a[r]，則彈出尾部）。當(dāng)當(dāng)前窗口的最大值與最小值之差超過k時，左指針l右移，并更新隊列（若隊列的隊首是l，則彈出隊首）。每次右指針移動后，當(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ù)最大值隊列while(!maxq.empty()&&a[r]>=a[maxq.back()])maxq.pop_back();maxq.push_back(r);//維護(hù)最小值隊列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)化問題描述：有m個任務(wù)，每個任務(wù)包含截止時間d?（完成時間需≤d?）和耗時t?（需連續(xù)t?天完成）。每天只能執(zhí)行一個任務(wù)的一個步驟（即一個任務(wù)需占用連續(xù)t?天）。求最多能完成的任務(wù)數(shù)量。輸入格式：第一行包含整數(shù)m（1≤m≤10?）；接下來m行，每行兩個整數(shù)d?和t?（1≤t?≤d?≤10?）。輸出格式：輸出能完成的最大任務(wù)數(shù)。樣例輸入：3325342樣例輸出：2解題思路：貪心策略：按截止時間d?升序排序。維護(hù)當(dāng)前已選任務(wù)的總耗時sum，并使用大頂堆存儲已選任務(wù)的耗時。遍歷每個任務(wù)：若sum+t?≤d?，直接加入，sum+=t?，堆插入t?。否則，若堆頂元素（當(dāng)前已選的最長耗時任務(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;}```第三題特殊回文子串計數(shù)問題描述：給定字符串s，統(tǒng)計所有長度≥2的回文子串中，滿足“子串的首字符和尾字符在原串中的出現(xiàn)次數(shù)均為奇數(shù)”的子串?dāng)?shù)目。輸入格式：輸入一個僅包含小寫字母的字符串s（長度≤10?）。輸出格式：輸出符合條件的子串?dāng)?shù)目。樣例輸入：ababa樣例輸出：3樣例解釋：符合條件的子串為"aba"（索引02）、"bab"（索引13）、"ababa"（索引04）。解題思路：1.預(yù)處理每個字符的前綴出現(xiàn)次數(shù)數(shù)組cnt[26][n+1]，其中cnt[c][i]表示前i個字符中字符c的出現(xiàn)次數(shù)。2.枚舉所有可能的回文子串中心（奇數(shù)長度中心為字符，偶數(shù)長度中心為字符間隙），用中心擴(kuò)展法計算每個中心的最大回文半徑。3.對于每個回文子串，取首尾字符，利用前綴數(shù)組判斷其在原串中的總出現(xiàn)次數(shù)是否為奇數(shù)（即cnt[c][n]%2==1）。若首尾字符均滿足條件，則計數(shù)加1。代碼（Python）：```pythons=input().strip()n=len(s)ifn<2:print(0)exit()預(yù)處理每個字符的前綴出現(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計算每個字符的總出現(xiàn)次數(shù)是否為奇數(shù)total_odd=[False]26forcinrange(26):total_odd[c]=(cnt[c][n]%2==1)res=0處理奇數(shù)長度回文（中心為字符）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ù)長度回文（中心為間隙）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)格路徑最小值問題描述：給定一個n行m列的網(wǎng)格，每個格子有正整數(shù)a[i][j]。從左上角(0,0)到右下角(n1,m1)，只能向右或向下移動。求所有可能路徑中，路徑上格子值的最大值的最小可能值。輸入格式：第一行包含兩個整數(shù)n和m（1≤n,m≤500）；接下來n行，每行m個整數(shù)表示a[i][j]（1≤a[i][j]≤10?）。輸出格式：輸出這個最小可能的最大值。樣例輸入：33131151421樣例輸出：2解題思路：動態(tài)規(guī)劃。定義dp[i][j]為到達(dá)(i,j)時路徑上的最大值的最小可能值。狀態(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]);}//動態(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á)時間問題描述：給定有向圖，n個節(jié)點(diǎn)m條邊，邊權(quán)為時間t。每個節(jié)點(diǎn)u有開放時間s[u]和關(guān)閉時間e[u]，只能在時間區(qū)間[s[u],e[u]]內(nèi)進(jìn)入節(jié)點(diǎn)u（到達(dá)u的時間需滿足該條件）。求從節(jié)點(diǎn)1到節(jié)點(diǎn)n的最早到達(dá)時間，若無法到達(dá)則輸出1。輸入格式：第一行包含兩個整數(shù)n和m（2≤n≤10?，1≤m≤2×10?）；接下來m行，每行三個整數(shù)u,v,t（1≤u,v≤n，1≤t≤10?）；最后一行n個整數(shù)s[1..n]和n個整數(shù)e[1..n]（0≤s[u]≤e[u]≤101?）。輸出格式：輸出最早到達(dá)時間，無法到達(dá)則輸出1。樣例輸入：33121231133000100100100樣例輸出：2樣例解釋：路徑1→2→3：到達(dá)2的時間為1（在[0,100]內(nèi)），從2出發(fā)時間為1，到達(dá)3的時間為2（在[0,100]內(nèi)）。解題思路：Dijkstra算法變種。優(yōu)先隊列存儲（到達(dá)時間，節(jié)點(diǎn)），維護(hù)每個節(jié)點(diǎn)的最早到達(dá)時間。對于節(jié)點(diǎn)u，到達(dá)時間為arrive_u，需滿足s[u]≤arrive_u≤e[u]。從u出發(fā)經(jīng)過邊u→v（耗時t）時，出發(fā)時間為max(arrive_u,s[u])，到達(dá)v的時間為出發(fā)時間+t。若到達(dá)v的時間≤e[v]，則更新v的最早到達(dá)時間。代碼（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的時間為0？需檢查是否在[s[1],e[1]]內(nèi)if(dist[1]<s[1]||dist[1]>e[1]){//初始無法進(jìn)入節(jié)點(diǎn)1cout<<1<<endl;return0;}priority_queue<pair<ll,in