2025年ccf考試題庫及答案一、項目選擇問題某公司有n個待選項目，每個項目i有開始時間s_i、結(jié)束時間e_i（s_i<e_i，時間單位為整數(shù)）和利潤p_i（p_i>0）。若兩個項目的時間區(qū)間有重疊（即一個項目的開始時間小于另一個的結(jié)束時間），則無法同時選擇。要求選擇若干不重疊的項目，使得總利潤最大。n≤1e5，s_i、e_i≤1e9。答案1.解題思路：該問題為經(jīng)典的帶權(quán)區(qū)間調(diào)度問題，需用動態(tài)規(guī)劃結(jié)合二分查找優(yōu)化。核心思想是按結(jié)束時間排序，對于每個項目i，找到最后一個不與i沖突的項目j（即e_j≤s_i），則最大利潤為max（不選i時的最大利潤，選i時的利潤+p_j的最大利潤）。2.具體步驟：排序：將所有項目按結(jié)束時間e_i升序排序。預(yù)處理：創(chuàng)建數(shù)組end保存排序后的e_i，用于二分查找。動態(tài)規(guī)劃：定義dp[i]為前i個項目的最大利潤。初始dp[0]=0（無項目時利潤為0）。對于第i個項目（i從1到n），通過二分查找在end數(shù)組中找到最大的j，使得end[j]≤s_i（項目i的開始時間）。則dp[i]=max(dp[i-1],dp[j]+p_i)。3.代碼實現(xiàn)（C++）：```cppinclude<bits/stdc++.h>usingnamespacestd;structProject{ints,e,p;booloperator<(constProject&other)const{returne<other.e;}};intmain(){intn;cin>>n;vector<Project>projs(n);for(inti=0;i<n;++i){cin>>projs[i].s>>projs[i].e>>projs[i].p;}sort(projs.begin(),projs.end());vector<int>end(n);for(inti=0;i<n;++i)end[i]=projs[i].e;vector<longlong>dp(n+1,0);for(inti=1;i<=n;++i){ints=projs[i-1].s;//二分查找最大的j，使得end[j]<=sintl=0,r=i-2,j=-1;while(l<=r){intmid=(l+r)/2;if(end[mid]<=s){j=mid;l=mid+1;}else{r=mid1;}}dp[i]=max(dp[i-1],dp[j+1]+projs[i-1].p);}cout<<dp[n]<<endl;return0;}```4.復(fù)雜度分析：排序O(nlogn)，二分查找每次O(logn)，動態(tài)規(guī)劃O(nlogn)，總時間復(fù)雜度O(nlogn)。二、鄉(xiāng)村道路維護問題某地區(qū)有m個村莊，初始由k條雙向道路連接，每條道路有維護費用c_i?，F(xiàn)需保留一個道路子集，使得所有村莊連通，且總維護費用最小。此外，有t條“主路”必須被保留（t≤k）。求最小總維護費用。m≤1e4，k≤1e5，c_i≤1e3。答案1.解題思路：該問題為帶約束的最小提供樹（MST）問題。需先將必須保留的主路加入提供樹，再用Kruskal算法處理剩余邊。若主路本身形成環(huán)，則問題無解（無法保留所有主路）。2.具體步驟：并查集初始化：每個村莊初始為獨立集合。處理主路：遍歷所有主路，若兩端村莊已連通（合并失?。?，說明存在環(huán)，輸出-1；否則合并，累加費用。處理剩余邊：將非主路按費用升序排序，用Kruskal算法依次嘗試添加，合并不同集合的村莊，累加費用。最終檢查：若所有村莊連通（并查集根節(jié)點數(shù)為1），輸出總費用；否則輸出-1。3.代碼實現(xiàn)（C++）：```cppinclude<bits/stdc++.h>usingnamespacestd;structEdge{intu,v,c;boolis_main;booloperator<(constEdge&other)const{returnc<other.c;}};vector<int>parent;intfind(intx){if(parent[x]!=x)parent[x]=find(parent[x]);returnparent[x];}intmain(){intm,k,t;cin>>m>>k>>t;vector<Edge>edges(k);for(inti=0;i<k;++i){cin>>edges[i].u>>edges[i].v>>edges[i].c;edges[i].is_main=false;}//標記主路（假設(shè)前t條為必須保留的主路）for(inti=0;i<t;++i)edges[i].is_main=true;parent.resize(m+1);for(inti=1;i<=m;++i)parent[i]=i;longlongtotal=0;intcnt=m;//連通分量數(shù)//先處理主路for(auto&e:edges){if(!e.is_main)continue;intu=find(e.u),v=find(e.v);if(u==v){//主路形成環(huán)，無解cout<<-1<<endl;return0;}parent[u]=v;total+=e.c;cnt--;}//處理非主路，按費用排序sort(edges.begin(),edges.end());for(auto&e:edges){if(e.is_main)continue;intu=find(e.u),v=find(e.v);if(u!=v){parent[u]=v;total+=e.c;cnt--;if(cnt==1)break;}}if(cnt==1)cout<<total<<endl;elsecout<<-1<<endl;return0;}```4.復(fù)雜度分析：并查集操作近似O(α(m))（α為阿克曼函數(shù)反函數(shù)，可視為常數(shù)），排序O(klogk)，總時間復(fù)雜度O(klogk)。三、網(wǎng)絡(luò)評論敏感詞過濾問題給定一段文本S（長度≤1e5）和敏感詞庫T（含m個詞，m≤1e3，每個詞長度≤20），部分敏感詞包含通配符''（表示任意單個字符）。要求找出S中所有敏感詞的出現(xiàn)位置（起始索引，從0開始），若多個敏感詞在同一位置重疊，需全部輸出。答案1.解題思路：通配符處理需將模式串轉(zhuǎn)換為正則表達式邏輯，結(jié)合AC自動機（Aho-Corasick）實現(xiàn)多模式匹配。對于含''的模式，將其拆分為多個子串，匹配時允許任意字符填充''的位置。2.具體步驟：預(yù)處理模式串：將每個敏感詞中的''替換為正則表達式中的'.'，并構(gòu)建AC自動機的trie樹。構(gòu)建失敗指針：為trie樹節(jié)點設(shè)置失敗指針，用于快速跳轉(zhuǎn)不匹配的情況。文本匹配：遍歷文本S的每個字符，沿trie樹移動，若到達某個終止節(jié)點（對應(yīng)敏感詞），記錄其起始位置（當前索引-詞長度+1）。3.代碼實現(xiàn)（Python）：```pythonfromcollectionsimportdequeclassACNode:def__init__(self):self.children={}字符到子節(jié)點的映射self.fail=None失敗指針self.output=[]存儲以該節(jié)點結(jié)尾的敏感詞長度（原詞長度）defbuild_ac_automaton(patterns):root=ACNode()構(gòu)建trie樹forpatinpatterns:node=rootforcinpat.replace('','.'):通配符視為任意字符ifcnotinnode.children:node.children[c]=ACNode()node=node.children[c]node.output.append(len(pat))記錄原詞長度（含）構(gòu)建失敗指針queue=deque()root.fail=Nonequeue.append(root)whilequeue:current_node=queue.popleft()forchar,childincurrent_node.children.items():ifcurrent_node==root:child.fail=rootelse:p=current_node.failwhilepandcharnotinp.children:p=p.failchild.fail=p.children[char]ifpelserootqueue.append(child)returnrootdeffind_sensitive_words(S,patterns):root=build_ac_automaton(patterns)current=rootresult=[]fori,cinenumerate(S):whilecurrent!=rootandcnotincurrent.children:current=current.failifcincurrent.children:current=current.children[c]else:current=root回到根節(jié)點檢查所有可能的輸出temp=currentwhiletemp!=root:forlengthintemp.output:start=ilength+1ifstart>=0:result.append((start,i))(起始索引，結(jié)束索引)temp=temp.failreturnresult示例調(diào)用S="abxcydze"patterns=["ac","xz"]print(find_sensitive_words(S,patterns))輸出：[(0,2),(2,6)]（假設(shè)匹配成功）```4.復(fù)雜度分析：構(gòu)建AC自動機O(total_length_of_patterns)，匹配文本O(len(S)+num_matches)，適用于大規(guī)模文本和多模式匹配。四、股票價格在線監(jiān)控問題設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，支持以下操作：1.insert(t,p)：插入時間t（t唯一且遞增）對應(yīng)的股票價格p；2.query(l,r)：查詢時間在[l,r]區(qū)間內(nèi)的最大價格。要求insert時間O(logn)，query時間O(logn)，n為已插入記錄數(shù)。答案1.解題思路：由于時間t遞增，可將時間存儲為有序數(shù)組，用線段樹或平衡二叉搜索樹（如C++的std::map）維護區(qū)間最大值。線段樹適合動態(tài)區(qū)間查詢，且插入操作可通過更新葉子節(jié)點實現(xiàn)。2.具體實現(xiàn)（線段樹方案）：線段樹節(jié)點：每個節(jié)點保存區(qū)間的左右端點和該區(qū)間的最大值。insert操作：時間t遞增，因此每次插入相當于在數(shù)組末尾添加元素，線段樹需動態(tài)擴展或預(yù)分配足夠空間（根據(jù)t的范圍）。實際中可采用離散化時間點，或使用動態(tài)開點線段樹。query操作：遞歸查詢區(qū)間[l,r]覆蓋的線段樹節(jié)點，取最大值。3.代碼實現(xiàn)（動態(tài)開點線段樹，Python）：```pythonclassSegmentTreeNode:def__init__(self,l,r):self.l=lself.r=rself.left=Noneself.right=Noneself.max_val=-float('inf')classStockMonitor:def__init__(self):self.root=SegmentTreeNode(0,1018)假設(shè)時間t最大為1e18self.times=[]記錄已插入的時間，用于驗證遞增definsert(self,t,p):ifself.timesandt<=self.times[-1]:raiseValueError("時間必須遞增")self.times.append(t)self._update(self.root,t,p)def_update(self,node,t,p):ifnode.l==node.r:node.max_val=max(node.max_val,p)returnmid=(node.l+node.r)//2ift<=mid:ifnotnode.left:node.left=SegmentTreeNode(node.l,mid)self._update(node.left,t,p)else:ifnotnode.right:node.right=SegmentTreeNode(mid+1,node.r)self._update(node.right,t,p)left_max=node.left.max_valifnode.leftelse-float('inf')right_max=node.right.max_valifnode.rightelse-float('inf')node.max_val=max(left_max,right_max)defquery(self,l,r):returnself._query(self.root,l,r)def_query(self,node,l,r):ifnotnodeornode.r<lornode.l>r:return-float('inf')ifl<=node.landnode.r<=r:returnnode.max_valreturnmax(self._query(node.left,l,r),self._query(node.right,l,r))示例調(diào)用monitor=StockMonitor()monitor.insert(1,10)monitor.insert(2,15)monitor.insert(3,12)print(monitor.query(1,3))輸出15```4.復(fù)雜度分析：insert操作需遍歷線段樹高度O(logM)（M為時間范圍），query同理，滿足O(logn)要求（n為插入次數(shù)，M足夠大時logM≈logn）。五、移動設(shè)備最近距離查詢問題動態(tài)添加移動設(shè)備的坐標（x,y），每次添加后需快速查詢當前所有設(shè)備中最近的兩個設(shè)備的距離。要求添加操作O(logn)，查詢操作O(1)或O(logn)，n為設(shè)備數(shù)。答案1.解題思路：靜態(tài)最近點對問題可用分治法（O(nlogn)），但動態(tài)情況下需維護點集結(jié)構(gòu)。一種方法是維護最近距離的候選集，每次插入新點時，僅檢查其附近一定范圍內(nèi)的點（如基于網(wǎng)格劃分，每個網(wǎng)格保存點列表，插入時檢查相鄰網(wǎng)格的點）。2.具體步驟：網(wǎng)格劃分：設(shè)定網(wǎng)格大小為d（初始可設(shè)為當前已知最近距離的一半），每個網(wǎng)格保存其中的點。插入新點：計算新點所在網(wǎng)格，檢查該網(wǎng)格及周圍8個相鄰網(wǎng)格中的點，計算與新點的距離，更新全局最近距離。動態(tài)調(diào)整網(wǎng)格大?。喝羧肿罱嚯x變小，縮小網(wǎng)格大小以提高后續(xù)插入的檢查效率。3.代碼實現(xiàn)（Python）：```pythonimportmathfromcollectionsimportdefaultdictclassDeviceTracker:def__init__(self):self.points=[]保存所有點self.min_dist=float('inf')當前最近距離self.grid=defaultdict(list)網(wǎng)格坐標到點的映射self.cell_size=1初始網(wǎng)格大小def_get_grid_key(self,x,y):return(int(x//self.cell_size),int(y//self.cell_size))definsert(self,x,y):new_point=(x,y)key=self._get_grid_key(x,y)