2025年算法精英大赛初赛测试题及答案

2025年算法精英大赛初赛测试题及答案项目选择问题。某公司有n个待选项目，每个项目有开始时间s_i、结束时间e_i（s_i<e_i）和收益v_i。若两个项目时间重叠（即一个的开始时间小于另一个的结束时间）则无法同时选择。请选择若干不重叠的项目，使得总收益最大。输入格式：第一行包含一个整数n（1≤n≤200000）。接下来n行，每行包含三个整数s_i、e_i、v_i（1≤s_i<e_i≤1e9，1≤v_i≤1e5）。输出格式：一个整数，表示可以获得的最大收益。样例输入：4135256474683样例输出：9解答思路：将项目按结束时间升序排序，定义dp[i]为前i个项目的最大收益。对于第i个项目，若选择则需找到最大的j使得e_j≤s_i，此时dp[i]=max(dp[i-1],dp[j]+v_i)。通过二分查找快速定位j。代码实现（Python）：```pythonimportbisectn=int(input())projects=[]for_inrange(n):s,e,v=map(int,input().split())projects.append((e,s,v))projects.sort()e_list=[p[0]forpinprojects]s_list=[p[1]forpinprojects]v_list=[p[2]forpinprojects]dp=[0](n+1)foriinrange(1,n+1):s=s_list[i-1]v=v_list[i-1]j=bisect.bisect_right(e_list,s,0,i-1)1dp[i]=max(dp[i-1],dp[j+1]+v)print(dp[n])```运输时间计算。某物流网络由n个节点和m条有向边组成，每条边连接u到v，运输需要l时间，且只能在时间窗口[a,b]内开始运输（即出发时间t需满足a≤t≤b）。从节点1出发，求到达节点n的最早时间。若无法到达，输出-1。输入格式：第一行包含两个整数n和m（2≤n≤1e5，1≤m≤2e5）。接下来m行，每行包含四个整数u,v,l,a,b（1≤u,v≤n，1≤l≤1e5，0≤a≤b≤1e9）。输出格式：一个整数，表示最早到达时间；无法到达则输出-1。样例输入：331220523336137010样例输出：6解答思路：使用Dijkstra算法变种，优先队列存储（到达时间，节点）。维护每个节点的最早到达时间，遍历出边时计算可行出发时间，更新到达时间。代码实现（Python）：```pythonimportheapqn,m=map(int,input().split())adj=[[]for_inrange(n+1)]for_inrange(m):u,v,l,a,b=map(int,input().split())adj[u].append((v,l,a,b))INF=float('inf')earliest=[INF](n+1)earliest[1]=0heap=[]heapq.heappush(heap,(0,1))whileheap:current_time,u=heapq.heappop(heap)ifu==n:print(current_time)exit()ifcurrent_time>earliest[u]:continueforv,l,a,binadj[u]:t_start=max(current_time,a)ift_start>b:continuet_arrive=t_start+lift_arrive<earliest[v]:earliest[v]=t_arriveheapq.heappush(heap,(t_arrive,v))print(-1ifearliest[n]==INFelseearliest[n])```特殊回文子串计数。给定字符串s，统计满足以下条件的回文子串数目：子串长度为奇数；子串中每个字符的出现次数均为奇数。输入格式：一行字符串s（长度≤1e5，仅含小写字母）。输出格式：一个整数，表示符合条件的子串数目。样例输入："aaa"样例输出：4解答思路：中心扩展法遍历每个回文中心，维护字符出现次数的奇偶性位掩码。扩展时检查掩码中1的个数是否为奇数（字符种类数为奇数）。代码实现（Python）：```pythons=input().strip()n=len(s)count=0forcenterinrange(n):mask=0c=s[center]mask^=1<<(ord(c)ord('a'))ifbin(mask).bit_count()%2==1:count+=1radius=1whilecenterradius>=0andcenter+radius<n:ifs[centerradius]!=s[center+radius]:breakleft_char=s[centerradius]right_char=s[center+radius]mask^=1<<(ord(left_char)ord('a'))mask^=1<<(ord(right_char)ord('a'))ifbin(mask).bit_count()%2==1:count+=1radius+=1print(count)```大数组合数取模。给定n、k和质数p，计算组合数C(n,k)modp，其中n可以是1e18，k≤1e5，p≤1e9。输入格式：一行三个整数n,k,p（k≤1e5，p是质数）。输出格式：一个整数，表示C(n,k)modp的值；若k>n，输出0。样例输入：1037样例输出：1解答思路：利用Lucas定理，将n和k分解为p进制数，逐位计算组合数并相乘取模。k较小时直接计算分子分母逆元。代码实现（Python）：```pythondefcomb_mod(n,k,p):ifk<0ork>n:return0ifk==0ork==n:return1%pnumerator=1foriinrange(k):numerator=numerator(ni)%pdenominator=1foriinrange(1,k+1):denominator=denominatori%pinv_denominator=pow(denominator,p-2,p)returnnumeratorinv_denominator%pdeflucas(n,k,p):ifk==0:return1%pni=n%pki=k%pifki>ni:return0return(lucas(n//p,k//p,p)comb_mod(ni,ki,p))%pn,k,p=map(int,input().split())print(lucas(n,k,p))```区间异或和查询。给定数组a，支持区间异或操作和区间异或和查询。输入格式：第一行包含两个整数n和q（1≤n,q≤1e5）。第二行包含n个整数a_1到a_n。接下来q行，每行表示一个操作：类型1为区间异或，类型2为区间查询。输出格式：对于每个类型2的操作，输出查询结果。样例输入：53123452151131215样例输出：1514解答思路：线段树维护区间异或和，懒标记记录待异或值。根据区间长度奇偶性更新异或和，下传标记时处理子节点。代码实现（Python）：```pythonimportsyssys.setrecursionlimit(1<<25)classSegmentTree:def__init__(self,data):self.n=len(data)self.size=1whileself.size<self.n:self.size<<=1self.xor_sum=[0](2self.size)self.lazy=[0](2self.size)foriinrange(self.n):self.xor_sum[self.size+i]=data[i]foriinrange(self.size1,0,-1):self.xor_sum[i]=self.xor_sum[2i]^self.xor_sum[2i+1]defpush(self,node,l,r):ifself.lazy[node]!=0andnode<self.size:mid=(l+r)//2left_len=midl+1right_len=rmidifleft_len%2==1:self.xor_sum[2node]^=self.lazy[node]self.lazy[2node]^=self.lazy[node]ifright_len%2==1:self.xor_sum[2node+1]^=self.lazy[node]self.lazy[2node+1]^=self.lazy[node]self.lazy[node]=0defupdate_range(self,a,b,x,node=1,l=0,r=None):ifrisNone:r=self.size1ifa>rorb<l:returnifa<=landr<=b:length=rl+1iflength%2==1:self.xor_sum[node]^=xself.lazy[node]^=xreturnself.push(node,l,r)mid=(l+r)//2self.update_range(a,b,x,2node,l,mid)self.update_range(a,b,x,2node+1,mid+1,r)self.xor_sum[node]=self.xor_sum[2node]^self.xor_sum[2node+1]defquery_range(self,a,b,node=1,l=0,r=None):ifrisNone:r=self.size1ifa>rorb<l:return0ifa<=landr<=b:returnself.xor_sum[node]