2025年acm考试试题及答案

2025年acm考试试题及答案一、字符串变换问题输入一个长度为n的二进制字符串s（仅由'0'和'1'组成），每次操作可以选择任意子串[l,r]（1≤l≤r≤n），将s[l..r]中的每个字符异或1（即0变1，1变0）。求将s变为全0所需的最少操作次数。输入格式：第一行一个整数n（1≤n≤5×10⁵），第二行一个字符串s（长度为n）。输出格式：一个整数，表示最少操作次数。样例输入1：510101样例输出1：3解答：最少操作次数等于字符串中连续“1”块的数量。具体分析如下：连续的“1”可以通过一次翻转操作变为“0”。例如，字符串“110011”包含两个连续的“1”块（前两位和后两位），因此需要2次操作。遍历字符串时，记录前一个字符是否为“0”。当遇到“1”且前一个字符为“0”时，说明进入一个新的“1”块，操作次数加1。代码实现：```pythonn=int(input())s=input().strip()ifn==0:print(0)exit()count=0prev='0'初始前一个字符视为'0'forcins:ifc=='1'andprev=='0':count+=1prev=cprint(count)```二、资源约束下的项目收益最大化某公司有m个项目，每个项目需在时间区间[start_i,end_i)（左闭右开）内进行，占用r_i个资源，完成后获得p_i的收益。公司最多同时提供R个资源。选择若干不重叠（时间不重叠）的项目，求总收益的最大值。输入格式：第一行两个整数m和R（1≤m≤2000，1≤R≤200）。接下来m行，每行四个整数start_i,end_i,r_i,p_i（0≤start_i<end_i≤10⁹，1≤r_i≤R，1≤p_i≤10⁵）。输出格式：一个整数，表示最大总收益。样例输入2：320215241635210样例输出2：11解答：采用动态规划求解，步骤如下：1.排序：将项目按结束时间升序排序，便于快速查找不重叠的前驱项目。2.预处理前驱：对每个项目i，用二分查找找到最大的j，使得end_j≤start_i。3.状态定义：dp[i][r]表示前i个项目中，使用r资源的最大收益。4.状态转移：对于项目i，若选择该项目，则需从其前驱项目j的状态转移而来（资源r≥r_i时，dp[i][r]=max(dp[i][r],dp[j][rr_i]+p_i)）；若不选择，则继承前i-1个项目的状态。代码实现：```pythonimportbisectm,R=map(int,input().split())projects=[]for_inrange(m):s,e,r,p=map(int,input().split())projects.append((e,s,r,p))按结束时间排序projects.sort()按end升序排序end_times=[proj[0]forprojinprojects]预处理每个项目的前驱（最后一个不重叠的项目）prev=[-1]mforiinrange(m):s_i=projects[i][1]当前项目的start找最大的j，使得end_j<=s_ij=bisect.bisect_right(end_times,s_i)1ifj>=0:prev[i]=j动态规划，dp[r]表示当前使用r资源的最大收益dp=[[-1](R+1)for_inrange(m+1)]dp[0][0]=0前0个项目，0资源，收益0foriinrange(1,m+1):e_i,s_i,r_i,p_i=projects[i1]不选第i个项目forrinrange(R+1):dp[i][r]=max(dp[i][r],dp[i1][r])选第i个项目j=prev[i1]前驱项目的索引（0-based）forr_previnrange(R+1r_i):ifdp[j+1][r_prev]!=-1:前驱是前j+1个项目（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)```三、颜色变化限制的最短路径给定有向图，每条边有长度w和颜色c（0、1、2）。求从起点s到终点t的最短路径，要求路径中相邻边颜色变化次数不超过k次。输入格式：第一行四个整数n,m,k,s,t（n≤1e4，m≤2e4，k≤10，s,t≤n-1）。接下来m行，每行四个整数u,v,w,c（0≤u,v≤n-1，w≤1e4，c∈{0,1,2}）。输出格式：一个整数，表示最短路径长度；若无法到达，输出-1。样例输入3：45103012012312342025003102样例输出3：9解答：使用改进的Dijkstra算法，状态包含当前节点、上一条边的颜色（初始为-1）、已用颜色变化次数。优先队列按总长度排序，每次扩展时更新状态。代码实现：```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))状态：(总长度,当前节点,上一颜色,变化次数)INF=float('inf')距离数组：dist[node][last_color][changes]=最短长度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初始状态：没有前驱边，变化次数0，总长度0forchinrange(k+1):dist[s][-1][ch]=0用-1表示无颜色，实际存储时用3代替（避免索引负数）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已找到更短路径，跳过forv,w,cinedges[u]:new_changes=changesiflast_c!=-1:不是初始状态ifc!=last_c:new_changes+=1ifnew_changes>k:continue超过颜色变化限制转换last_c为非负数索引（-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)```四、二维区间查询统计给定数组A，每个元素有属性x和y。进行q次查询，每次查询给出a和b，求满足x_i>a且y_i<b的元素个数。输入格式：第一行两个整数n和q（n≤1e5，q≤1e5）。接下来n行，每行两个整数x_i,y_i。接下来q行，每行两个整数a,b。输出格式：对每个查询，输出一个整数。样例输入4：5235124124522342样例输出4：21解答：采用离线处理+树状数组。步骤如下：1.离散化y值：收集所有y_i和查询的b，排序去重，映射为排名。2.排序元素和查询：元素按x降序排序，查询按a降序排序，并记录原始索引。3.处理查询：用指针遍历元素，将x_i>a的元素的y插入树状数组，查询y<b的数量。代码实现：```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)}树状数组从1开始元素按x降序排序elements.sort(key=lambdax:(-x[0],x[1]))查询按a降序排序，并记录原始索引queries.sort(key=lambdax:(-x[0],x[1]))树状数组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指向当前处理的元素（按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的数量，即离散化后排名小于b的排名的数量b_rank=bisect.bisect_left(y_sorted,b)第一个≥b的位置，左边都是<b的count=ft.query(b_rank)树状数组中排名<=b_rank-1的数量（因为y_sorted[b_rank]是第一个≥b的）ans[idx]=countforainans:print(a)```