2025年编程比赛考试题型及答案

2025年编程比赛考试题型及答案一、算法基础题题目1：数组中的最长连续子序列给定一个整数数组nums，找出其中最长连续子序列的长度。连续子序列定义为元素在原数组中连续且数值连续递增1的序列。例如，数组[100,4,200,1,3,2]的最长连续子序列是[1,2,3,4]，长度为4。输入格式：第一行输入整数n（1≤n≤200000），表示数组长度；第二行输入n个整数，表示nums数组。输出格式：输出一个整数，表示最长连续子序列的长度。解题思路：使用哈希集合存储数组元素，遍历每个元素时，检查是否存在前一个数（current-1），若不存在则作为起点，向后查找current+1、current+2等，统计连续长度。时间复杂度O(n)，空间复杂度O(n)。示例输入：61004200132示例输出：4Python代码：```pythonn=int(input())nums=list(map(int,input().split()))num_set=set(nums)max_len=0fornuminnum_set:ifnum1notinnum_set:current=numcurrent_len=1whilecurrent+1innum_set:current+=1current_len+=1max_len=max(max_len,current_len)print(max_len)```二、数据结构应用题题目2：二叉树的最近公共祖先给定一棵二叉树的根节点root和两个节点p、q，找出它们的最近公共祖先（LCA）。最近公共祖先定义为同时是p和q的祖先的节点中深度最大的那个。输入格式：第一行按层序遍历输入二叉树节点值（-1表示空节点）；第二行输入p的值；第三行输入q的值。输出格式：输出LCA节点的值。解题思路：递归法。若当前节点是p或q，返回当前节点；否则递归左右子树。若左右子树均返回非空值，说明当前节点是LCA；若仅左或右子树返回非空值，返回该值。示例输入：3516208-1-17451示例输出：3Python代码（假设TreeNode类已定义）：```pythonclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=Nonedefbuild_tree(lst):ifnotlst:returnNoneroot=TreeNode(lst[0])queue=[root]i=1whilequeueandi<len(lst):current=queue.pop(0)iflst[i]!=-1:current.left=TreeNode(lst[i])queue.append(current.left)i+=1ifi<len(lst)andlst[i]!=-1:current.right=TreeNode(lst[i])queue.append(current.right)i+=1returnrootdeflowest_common_ancestor(root,p,q):ifnotrootorroot.val==porroot.val==q:returnrootleft=lowest_common_ancestor(root.left,p,q)right=lowest_common_ancestor(root.right,p,q)ifleftandright:returnrootreturnleftifleftelseright输入处理tree_vals=list(map(int,input().split()))p_val=int(input())q_val=int(input())root=build_tree(tree_vals)lca=lowest_common_ancestor(root,p_val,q_val)print(lca.val)```三、动态规划题题目3：分割等和子集给定一个只包含正整数的非空数组nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。输入格式：第一行输入n（1≤n≤200），第二行输入n个整数（每个数≤100）。输出格式：若是则输出“True”，否则输出“False”。解题思路：转化为0-1背包问题。若数组总和为奇数，直接返回False；否则目标为总和的一半。定义dp[i][j]表示前i个元素能否组成和为j的子集。状态转移方程：dp[i][j]=dp[i-1][j]（不选第i个元素）或dp[i-1][j-nums[i]]（选第i个元素）。空间优化后使用一维数组。示例输入：415115示例输出：TruePython代码：```pythonn=int(input())nums=list(map(int,input().split()))total=sum(nums)iftotal%2!=0:print("False")else:target=total//2dp=[False](target+1)dp[0]=Truefornuminnums:forjinrange(target,num1,-1):ifdp[jnum]:dp[j]=Trueprint("True"ifdp[target]else"False")```四、图论与搜索题题目4：最短路径（带权有向图）给定一个有向图，节点编号为0到n-1，边权为正整数。输入起点src和终点dst，求src到dst的最短路径长度。若不可达，输出-1。输入格式：第一行输入n（节点数，1≤n≤1000），m（边数）；接下来m行，每行输入u、v、w，表示u到v的边权w；最后两行输入src和dst。输出格式：输出最短路径长度或-1。解题思路：Dijkstra算法。使用优先队列（堆）维护当前最短距离，每次取出距离最小的节点，更新其邻接节点的距离。示例输入：5601202512113323134404示例输出：8（路径0→1→2→3→4，总权2+1+1+4=8）Python代码：```pythonimportheapqn,m=map(int,input().split())graph=[[]for_inrange(n)]for_inrange(m):u,v,w=map(int,input().split())graph[u].append((v,w))src=int(input())dst=int(input())INF=float('inf')dist=[INF]ndist[src]=0heap=[]heapq.heappush(heap,(0,src))whileheap:current_dist,u=heapq.heappop(heap)ifcurrent_dist>dist[u]:continueifu==dst:breakforv,wingraph[u]:ifdist[v]>dist[u]+w:dist[v]=dist[u]+wheapq.heappush(heap,(dist[v],v))print(dist[dst]ifdist[dst]!=INFelse-1)```五、字符串处理题题目5：最长回文子串给定一个字符串s，找到s中最长的回文子串。输入格式：输入一个仅包含小写字母的字符串s（长度≤1000）。输出格式：输出最长回文子串。若有多个，输出第一个出现的。解题思路：中心扩展法。遍历每个字符（奇数长度中心）和每对字符（偶数长度中心），向两边扩展，记录最长回文的起始和结束位置。示例输入：babad示例输出：bab（或aba，取第一个出现的）Python代码：```pythons=input().strip()ifnots:print("")n=len(s)start,end=0,0defexpand(left,right):whileleft>=0andright<nands[left]==s[right]:left-=1right+=1returnrightleft1foriinrange(n):len1=expand(i,i)len2=expand(i,i+1)max_len=max(len1,len2)ifmax_len>endstart:start=i(max_len1)//2end=i+max_len//2print(s[start:end+1])```六、数学与数论题题目6：丑数II编写一个程序，找出第n个丑数。丑数是质因数只包含2、3、5的正整数。输入格式：输入一个整数n（1≤n≤1690）。输出格式：输出第n个丑数。解题思路：动态规划。维护三个指针i2、i3、i5，分别指向当前乘以2、3、5后可能成为下一个丑数的位置。每次取三个指针指向值的最小值，更新对应指针。示例输入：10示例输出：12（前10个丑数：1,2,3,4,5,6,8,9,10,12）Python代码：```pythonn=int(input())dp=[1]ni2=i3=i5=0foriinrange(1,n):dp[i]=min(dp[i2]2,dp[i3]3,dp[i5]5)ifdp[i]==dp[i2]2:i2+=1ifdp[i]==dp[i3]3:i3+=1ifdp[i]==dp[i5]5:i5+=1print(dp[-1])```七、高级算法题（贪心+二分）题目7：在D天内送达包裹的能力传送带上的包裹必须在D天内从一个港口运到另一个港口。传送带上的第i个包裹重量为weights[i]。每天的运载能力必须至少为某一值，才能在D天内运完所有包裹。求所需的最小运载能力。输入格式：第一行输入n（包裹数），第二行输入n个整数表示weights数组，第三行输入D（天数）。输出格式：输出最小运载能力。解题思路：二分查找确定运载能力的上下界。下界为最大单个包裹重量（否则无法运），上界为所有包裹总重量（一天运完）。检查函数判断当前运载能力是否能在D天内完成。示例输入：5123456789105示例输出：15（每天运载量分别为15→1+2+3+4+5=15；15→6+7=13；15→8；15→9；15→10，共5天）Python代码：```pythonn=int(input())weights=list(map(int,input().split()))D=int(input())defcan_ship(capacity):days=1current=0forwinweights:ifcurrent+w>capacity:days+=1