2025年acm考試試題及答案一、字符串變換問(wèn)題輸入一個(gè)長(zhǎng)度為n的二進(jìn)制字符串s（僅由'0'和'1'組成），每次操作可以選擇任意子串[l,r]（1≤l≤r≤n），將s[l..r]中的每個(gè)字符異或1（即0變1，1變0）。求將s變?yōu)槿?所需的最少操作次數(shù)。輸入格式：第一行一個(gè)整數(shù)n（1≤n≤5×10?），第二行一個(gè)字符串s（長(zhǎng)度為n）。輸出格式：一個(gè)整數(shù)，表示最少操作次數(shù)。樣例輸入1：510101樣例輸出1：3解答：最少操作次數(shù)等于字符串中連續(xù)“1”塊的數(shù)量。具體分析如下：連續(xù)的“1”可以通過(guò)一次翻轉(zhuǎn)操作變?yōu)椤?”。例如，字符串“110011”包含兩個(gè)連續(xù)的“1”塊（前兩位和后兩位），因此需要2次操作。遍歷字符串時(shí)，記錄前一個(gè)字符是否為“0”。當(dāng)遇到“1”且前一個(gè)字符為“0”時(shí)，說(shuō)明進(jìn)入一個(gè)新的“1”塊，操作次數(shù)加1。代碼實(shí)現(xiàn)：```pythonn=int(input())s=input().strip()ifn==0:print(0)exit()count=0prev='0'初始前一個(gè)字符視為'0'forcins:ifc=='1'andprev=='0':count+=1prev=cprint(count)```二、資源約束下的項(xiàng)目收益最大化某公司有m個(gè)項(xiàng)目，每個(gè)項(xiàng)目需在時(shí)間區(qū)間[start_i,end_i)（左閉右開）內(nèi)進(jìn)行，占用r_i個(gè)資源，完成后獲得p_i的收益。公司最多同時(shí)提供R個(gè)資源。選擇若干不重疊（時(shí)間不重疊）的項(xiàng)目，求總收益的最大值。輸入格式：第一行兩個(gè)整數(shù)m和R（1≤m≤2000，1≤R≤200）。接下來(lái)m行，每行四個(gè)整數(shù)start_i,end_i,r_i,p_i（0≤start_i<end_i≤10?，1≤r_i≤R，1≤p_i≤10?）。輸出格式：一個(gè)整數(shù)，表示最大總收益。樣例輸入2：320215241635210樣例輸出2：11解答：采用動(dòng)態(tài)規(guī)劃求解，步驟如下：1.排序：將項(xiàng)目按結(jié)束時(shí)間升序排序，便于快速查找不重疊的前驅(qū)項(xiàng)目。2.預(yù)處理前驅(qū)：對(duì)每個(gè)項(xiàng)目i，用二分查找找到最大的j，使得end_j≤start_i。3.狀態(tài)定義：dp[i][r]表示前i個(gè)項(xiàng)目中，使用r資源的最大收益。4.狀態(tài)轉(zhuǎn)移：對(duì)于項(xiàng)目i，若選擇該項(xiàng)目，則需從其前驅(qū)項(xiàng)目j的狀態(tài)轉(zhuǎn)移而來(lái)（資源r≥r_i時(shí)，dp[i][r]=max(dp[i][r],dp[j][rr_i]+p_i)）；若不選擇，則繼承前i-1個(gè)項(xiàng)目的狀態(tài)。代碼實(shí)現(xiàn)：```pythonimportbisectm,R=map(int,input().split())projects=[]for_inrange(m):s,e,r,p=map(int,input().split())projects.append((e,s,r,p))按結(jié)束時(shí)間排序projects.sort()按end升序排序end_times=[proj[0]forprojinprojects]預(yù)處理每個(gè)項(xiàng)目的前驅(qū)（最后一個(gè)不重疊的項(xiàng)目）prev=[-1]mforiinrange(m):s_i=projects[i][1]當(dāng)前項(xiàng)目的start找最大的j，使得end_j<=s_ij=bisect.bisect_right(end_times,s_i)1ifj>=0:prev[i]=j動(dòng)態(tài)規(guī)劃，dp[r]表示當(dāng)前使用r資源的最大收益dp=[[-1](R+1)for_inrange(m+1)]dp[0][0]=0前0個(gè)項(xiàng)目，0資源，收益0foriinrange(1,m+1):e_i,s_i,r_i,p_i=projects[i1]不選第i個(gè)項(xiàng)目forrinrange(R+1):dp[i][r]=max(dp[i][r],dp[i1][r])選第i個(gè)項(xiàng)目j=prev[i1]前驅(qū)項(xiàng)目的索引（0-based）forr_previnrange(R+1r_i):ifdp[j+1][r_prev]!=-1:前驅(qū)是前j+1個(gè)項(xiàng)目（j是0-based）new_r=r_prev+r_iifnew_r>R:continuedp[i][new_r]=max(dp[i][new_r],dp[j+1][r_prev]+p_i)max_profit=max(dp[m][r]forrinrange(R+1))print(max_profitifmax_profit!=-1else0)```三、顏色變化限制的最短路徑給定有向圖，每條邊有長(zhǎng)度w和顏色c（0、1、2）。求從起點(diǎn)s到終點(diǎn)t的最短路徑，要求路徑中相鄰邊顏色變化次數(shù)不超過(guò)k次。輸入格式：第一行四個(gè)整數(shù)n,m,k,s,t（n≤1e4，m≤2e4，k≤10，s,t≤n-1）。接下來(lái)m行，每行四個(gè)整數(shù)u,v,w,c（0≤u,v≤n-1，w≤1e4，c∈{0,1,2}）。輸出格式：一個(gè)整數(shù)，表示最短路徑長(zhǎng)度；若無(wú)法到達(dá)，輸出-1。樣例輸入3：45103012012312342025003102樣例輸出3：9解答：使用改進(jìn)的Dijkstra算法，狀態(tài)包含當(dāng)前節(jié)點(diǎn)、上一條邊的顏色（初始為-1）、已用顏色變化次數(shù)。優(yōu)先隊(duì)列按總長(zhǎng)度排序，每次擴(kuò)展時(shí)更新狀態(tài)。代碼實(shí)現(xiàn)：```pythonimportheapqn,m,k,s,t=map(int,input().split())edges=[[]for_inrange(n)]for_inrange(m):u,v,w,c=map(int,input().split())edges[u].append((v,w,c))狀態(tài)：(總長(zhǎng)度,當(dāng)前節(jié)點(diǎn),上一顏色,變化次數(shù))INF=float('inf')距離數(shù)組：dist[node][last_color][changes]=最短長(zhǎng)度last_color:-1（初始）,0,1,2；changes:0~kdist=[[[INF](k+1)for_inrange(3)]for__inrange(n)]forcinrange(3):forchinrange(k+1):dist[s][c][ch]=INF初始狀態(tài)：沒(méi)有前驅(qū)邊，變化次數(shù)0，總長(zhǎng)度0forchinrange(k+1):dist[s][-1][ch]=0用-1表示無(wú)顏色，實(shí)際存儲(chǔ)時(shí)用3代替（避免索引負(fù)數(shù)）heap=[]heapq.heappush(heap,(0,s,-1,0))(length,node,last_color,changes)found=Falseans=INFwhileheap:length,u,last_c,changes=heapq.heappop(heap)ifu==t:ans=min(ans,length)found=Trueiflength>dist[u][last_c][changes]iflast_c!=-1elselength>dist[u][3][changes]:continue已找到更短路徑，跳過(guò)forv,w,cinedges[u]:new_changes=changesiflast_c!=-1:不是初始狀態(tài)ifc!=last_c:new_changes+=1ifnew_changes>k:continue超過(guò)顏色變化限制轉(zhuǎn)換last_c為非負(fù)數(shù)索引（-1→3）last_idx=last_ciflast_c!=-1else3current_dist=dist[u][last_idx][changes]ifcurrent_dist+w<dist[v][c][new_changes]:dist[v][c][new_changes]=current_dist+wheapq.heappush(heap,(dist[v][c][new_changes],v,c,new_changes))print(ansiffoundelse-1)```四、二維區(qū)間查詢統(tǒng)計(jì)給定數(shù)組A，每個(gè)元素有屬性x和y。進(jìn)行q次查詢，每次查詢給出a和b，求滿足x_i>a且y_i<b的元素個(gè)數(shù)。輸入格式：第一行兩個(gè)整數(shù)n和q（n≤1e5，q≤1e5）。接下來(lái)n行，每行兩個(gè)整數(shù)x_i,y_i。接下來(lái)q行，每行兩個(gè)整數(shù)a,b。輸出格式：對(duì)每個(gè)查詢，輸出一個(gè)整數(shù)。樣例輸入4：5235124124522342樣例輸出4：21解答：采用離線處理+樹狀數(shù)組。步驟如下：1.離散化y值：收集所有y_i和查詢的b，排序去重，映射為排名。2.排序元素和查詢：元素按x降序排序，查詢按a降序排序，并記錄原始索引。3.處理查詢：用指針遍歷元素，將x_i>a的元素的y插入樹狀數(shù)組，查詢y<b的數(shù)量。代碼實(shí)現(xiàn)：```pythonimportbisectn,q=map(int,input().split())elements=[]y_values=[]for_inrange(n):x,y=map(int,input().split())elements.append((x,y))y_values.append(y)queries=[]foriinrange(q):a,b=map(int,input().split())queries.append((a,b,i))y_values.append(b)離散化y值y_sorted=sorted(list(set(y_values)))y_rank={y:i+1fori,yinenumerate(y_sorted)}樹狀數(shù)組從1開始元素按x降序排序elements.sort(key=lambdax:(-x[0],x[1]))查詢按a降序排序，并記錄原始索引queries.sort(key=lambdax:(-x[0],x[1]))樹狀數(shù)組classFenwickTree:def__init__(self,size):self.n=sizeself.tree=[0](self.n+2)defupdate(self,idx,delta=1):whileidx<=self.n:self.tree[idx]+=deltaidx+=idx&-idxdefquery(self,idx):res=0whileidx>0:res+=self.tree[idx]idx-=idx&-idxreturnresft=FenwickTree(len(y_sorted))ans=[0]qptr=0指向當(dāng)前處理的元素（按x降序）fora,b,idxinqueries:處理所有x>a的元素（即x降序中，x>a的元素）whileptr<nandelements[ptr][0]>a:y=elements[ptr][1]r=y_rank[y]ft.update(r)ptr+=1查詢y<b的數(shù)量，即離散化后排名小于b的排名的數(shù)量b_rank=bisect.bisect_left(y_sorted,b)第一個(gè)≥b的位置，左邊都是<b的count=ft.query(b_rank)樹狀數(shù)組中排名<=b_rank-1的數(shù)量（因?yàn)閥_sorted[b_rank]是第一個(gè)≥b的）ans[idx]=countforainans:print(a)```