简介面向准备百度之星等编程竞赛的学生与算法爱好者这份历年试题归档把赛题按网页形式整理可用于熟悉题型、专项训练和赛前查漏补缺。压缩包共116个文件整体约983KB包含62张题目配图、24个CSS样式文件、16个HTM页面、12个JS脚本及少量PNG、GIF素材页面、样式与脚本相互配合便于离线浏览和按主题检索。赛题内容覆盖基础编程、数组链表栈队列树图等数据结构、排序搜索动态规划贪心等算法以及逻辑推理、数学应用和字符串处理能够帮助读者理解竞赛命题思路并积累解题方法。已有636人学习适合希望在C、Java、Python等语言环境下提升问题建模与代码实现能力的读者作为练习资料。1. 先别急着做压轴题这场比赛的分数分散在不同题型里很多人拿到算法编程大赛历年试题后第一件事就是翻到最后一题看自己离最难的那几题还差多远。做了两套下来最容易丢的分数往往在前两题题意已经读懂也觉得自己会做却因为边界没考虑清楚或者多组数据没有清空全局变量交了六七次也没过。这场面向高校学生的算法编程赛事通常四小时八道题每题一百分按通过测试点给分前四题的分值加起来往往超过一半。签到、模拟、二分、动态规划DP、最短路、并查集这几类题目只要板子常用代码模板写得熟、细节处理到位就能稳定拿到分。这套历年试题适合已经能写完整程序、刷过一两百道题、但比赛名次总卡在中游的人与其按难度顺序硬扛压轴题不如按考点把历年题拆开重做一遍。2. 考点地图八道题的难度梯度与分值分布历年题翻多了会发现一个规律题号位置和考点类型高度相关。第 1、2 题几乎固定是模拟与简单数学第 3、4 题集中在贪心、二分、前缀和与基础 DP第 5、6 题开始上图论和数据结构第 7、8 题才是思维题、复杂 DP 或需要组合多个算法的综合题。按这个梯度分配时间比按题目顺序硬做更划算。下表把五类考点在历年题里的出场频次、常见分档和建议用时列了出来可以当作刷题时的优先级参考。考点类型出场频次常见题号位置建议用时目标模拟与签到每场 2 题第 1、2 题25 分钟内一次通过不交罚时贪心、二分、前缀和每场 2 到 3 题第 3、4 题50 分钟至少通过一题另一题拿到部分分动态规划每场 1 到 2 题第 4 到第 6 题40 分钟想出状态定义能写就能拿分图论与并查集每场 1 到 2 题第 5、6 题45 分钟板子默写速度决定成败数学、字符串、综合每场 1 到 2 题第 7、8 题剩余时间能推就推推不出就抓部分分2.1 签到题与模拟题前二十分钟能决定后面怎么做签到题的特征很稳定题意直白数据范围小样例给得全不需要任何算法只需要把规则翻译成代码。历年题里反复出现的有三类日期与时间换算给起止时间求跨越天数、按整点分桶统计、矩阵与坐标变换旋转、螺旋遍历、按对角线输出、规则模拟排队、计分、消除。看起来简单但这类题的通过率并没有想象中高因为它考的是细节闰年规则、跨年跨月、下标从零开始还是从一开始、输出格式要不要保留小数位。看一道典型变形“给定若干个闭区间求被覆盖的总长度重叠部分只算一次”。这题本质是区间合并思路是先把所有区间按左端点排序然后线性扫描维护当前合并段的右端点cur_r如果下一个区间的左端点小于等于cur_r说明有重叠把cur_r更新为两者较大值否则结算当前段长度并开启新段。面试和笔试里它常被包装成“会议安排”“日程冲突检测”“统计在线时长”考点完全一样。写的时候容易忽略的是区间端点是否包含、输入是否保证左端点小于右端点、以及所有区间都不重叠时循环结束后还要补一次结算。提示签到题不要一上来就想着优化。先写最直白的版本样例过了再考虑数据范围是否需要改算法很多翻车都是败在“还没通过样例就开始重构”。2.2 动态规划从一维到树形的三个台阶DP 在历年题里几乎每场都有难度跨度也最大可以分成三个台阶。第一个台阶是一维线性 DP最大子段和、最长上升子序列、打家劫舍这类状态只有一个维度转移只依赖前一个或前几个位置。第二个台阶是二维 DP01 背包、完全背包、区间 DP石子合并、括号匹配、回文分割状态有两个维度写的时候要特别注意遍历顺序背包问题里容量维必须倒着遍历才能保证每个物品只用一次。第三个台阶是树上 DP 与状压 DP最大独立集、换根求最远距离、以位掩码表示集合的 TSP 变种。答题时的固定顺序是先用一句话说清状态含义“dp[i]表示以 i 结尾的最大子段和”再写转移方程最后处理初始化。三步里最容易被跳过的是初始化而它恰恰是失分重灾区。比如“恰好装满容量为 V 的背包”这类题初始化时除了dp[0] 0其余必须是负无穷而不是 0否则“未装满”的状态会被当成合法解传递下去。历年题里有一道很能区分水平的分割问题“把长度为 n 的数组分成 k 段连续子数组使各段和的最大值最小”。这题有两个方向一是二分答案加贪心判定二是区间 DP复杂度 O(n²k)只能过小数据。考场上先看数据范围n 上千、k 较小就走二分答案n 只有几百就走 DP。同一个人在同一场比赛里能不能根据数据范围切换算法比会不会写 DP 更能体现经验。2.3 图论三件套最短路、最小生成树、拓扑排序图论题的分值通常偏高但板子极其固定属于“背下来就能拿分”的模块。最短路要准备三份堆优化的 Dijkstra非负权单源、Floydn 在 500 以内、需要全源、Bellman-Ford 或队列优化的版本带负权时用但要能判断负环。最小生成树准备 Kruskal 加并查集就够稠密图上 Prim 更优但很少考。拓扑排序既是判环工具也是 DAG 上做 DP 的前置步骤。这三个板子加起来不到一百行背熟之后省下的时间可以全部投给后面的题。变形题才是真正拉开差距的地方。历年题里常见三种一是多源最短路做法是建一个超级源点把它到所有起点的边权设为 0然后跑一次单源最短路二是分层图题目说“最多可以免费经过 k 条边”把每个点拆成 k1 层免费边从第 i 层连到第 i1 层且边权为 0答案取各层终点的最小值三是双关键词最短路“在距离最短的前提下花费最少”用距离作为堆比较的第一关键字、花费作为第二关键字即可不需要写两遍。写图论题最容易出的问题不在算法而在建图重边要取最小值、自环要直接忽略、无向图数组要开两倍、节点编号是 0 起始还是 1 起始要统一还有不能到达时的输出约定。这些细节在样例里通常不会暴露交上去才会挂属于典型的血泪经验。2.4 二分、前缀和与数据结构模板的熟练度直接决定速度二分答案的识别信号是“最大化最小值”“最小化最大值”“求第 k 大”这类措辞。判定函数必须满足单调性答案成立时比它更宽松或更严格的一侧也全部成立。写二分的模板要固定下来避免在边界上反复试常用的是左闭右开写法while lo hi: mid (lo hi) // 2根据判定结果移动lo或hi循环结束时lo就是答案。真正容易错的是判定函数内部的贪心策略二分本身反而简单。前缀和与差分是降维工具。一维前缀和把区间求和从 O(n) 降到 O(1)二维前缀和用于子矩阵求和差分把“区间加、最后统一查询”从 O(nm) 降到 O(nm)。历年题里非常常见的“多次区间修改最后输出整个数组”就是差分模板题写起来只有四行。数据结构方面优先级从高到低是单调栈下一个更大元素、柱状图最大矩形、单调队列滑动窗口最值、树状数组单点修改区间查询、逆序对计数、线段树区间修改区间查询。线段树代码长、出错率高赛场上除非确定要用否则优先考虑树状数组或者离线做法。判断标准很简单如果操作可以离线并且能用排序加树状数组解决就不要写线段树。2.5 数学与字符串真正决定名次的分水岭数学题在前四题里也有但通常是浅层的gcd 与 lcm、快速幂取模、组合数取模、素数筛、进制转换。这些必须做到默写级别尤其是快速幂和组合数的预处理很多题只差这一步就能从部分分变成满分。稍微深一点的是扩展欧几里得解同余方程、容斥原理计数出现频率不高但一旦出现会的人十分钟写完不会的人一百分全丢。字符串题的主力是 KMP、字符串哈希和字典序比较。KMP 的next数组除了做匹配还有一个使用频率很高的用途求最短循环节。若长度为 n 的串由某个前缀重复若干次构成最短循环节长度是n - next[n]且当n % (n - next[n]) 0时串是周期串。这个结论在历年题里至少出现过三次不同包装的版本值得直接记住。字符串哈希则用来做多次子串相等判断注意双模数或使用 64 位无符号自然溢出单模数容易被构造数据命中。3. 高频真题六类反复出场的题型与答题思路下面这六类题在历年试题里出现的频率极高几乎每年都能找到对应版本。每一类给出一份可直接默写的实现重点不在代码本身而在于它对应的识别信号和变形方向。3.1 差分区间修改的通用解法题面通常是这样“有 n 个位置初始值为 0进行 m 次操作每次给区间 [l, r] 加上 v最后输出每个位置的值”。朴素做法是每次循环复杂度 O(nm)数据一大就会超时。差分数组d[i] a[i] - a[i-1]对区间加 v 只需要d[l] v和d[r1] - v两次操作最后做一次前缀和就还原出原数组。# 差分数组区间加、最后统一查询 n, m map(int, input().split()) d [0] * (n 2) # 多开两位防止 r1 越界 for _ in range(m): l, r, v map(int, input().split()) d[l] v # 区间起点加 v d[r 1] - v # 区间终点后一位减 v抵消影响 cur 0 res [] for i in range(1, n 1): cur d[i] # 前缀和还原 res.append(cur) print(*res)d数组开n2是为了让r1在r n时也不越界这一位之后不会被输出所以不用清理。若题目是“区间加、区间求和”差分就要升级成树状数组维护两个差分数组属于中等难度题型。注意差分处理的是“先全部修改、最后统一查询”的场景。如果修改和查询交替出现就必须上树状数组或线段树用差分只会得到错误答案。3.2 01 背包三种常见问法的统一写法背包题的三种问法要分清求最大价值、求恰好装满时的最大价值、求方案数。它们的转移方程骨架相同差别只在初始化。一维滚动数组的标准写法是容量维倒序遍历这样dp[j]在被更新时依赖的dp[j-w]还是上一轮的值等价于每个物品只用一次。# 01 背包n 件物品容量 W求最大价值 n, W map(int, input().split()) w [0] * n v [0] * n for i in range(n): w[i], v[i] map(int, input().split()) dp [0] * (W 1) # 求最大价值时全部初始化为 0 for i in range(n): for j in range(W, w[i] - 1, -1): # 倒序遍历保证每件物品只用一次 dp[j] max(dp[j], dp[j - w[i]] v[i]) print(dp[W])如果题目改成“恰好装满”初始化就要换成dp[0] 0、其余为负无穷最后dp[W]若仍是负无穷说明无解。如果改成“求方案数”转移从取 max 变成累加容量维依然倒序。如果改成完全背包每件物品无限件只要把容量维改成正序遍历即可。这三种变形靠改一行就能完成前提是理解倒序和正序背后的含义而不是死记。3.3 分层图最短路k 次免费机会的标准处理方式题面“给定一张带权无向图从 s 到 t最多可以让 k 条边的权值变为 0求最短距离”。这类题如果不熟悉套路很容易写成搜索加剪枝最后超时。标准做法是把状态扩展成(节点, 已用免费次数)共 n×(k1) 个状态跑一次 Dijkstra。实际实现时不一定真去建分层图直接在 dist 数组上多开一维即可。import heapq # dist[u][c]到达 u、已用掉 c 次免费机会时的最短距离 def solve(n, adj, s, t, k): INF float(inf) dist [[INF] * (k 1) for _ in range(n 1)] dist[s][0] 0 pq [(0, s, 0)] # (距离, 节点, 已用次数) while pq: d, u, c heapq.heappop(pq) if d dist[u][c]: continue for v, w in adj[u]: if d w dist[v][c]: # 不使用免费机会 dist[v][c] d w heapq.heappush(pq, (d w, v, c)) if c k and d dist[v][c 1]: # 用掉一次免费机会边权变 0 dist[v][c 1] d heapq.heappush(pq, (d, v, c 1)) return min(dist[t]) # 取终点各层的最小值答案要取min(dist[t])而不是dist[t][k]因为“最多 k 次”意味着用不满也合法。这个模板稍加改动就能应付另外两种常见题把边权换成“通过某类边的次数”“换乘次数”“状态开关”都只是状态维度上的加法。3.4 二分答案把最优化问题变成判定问题识别信号是题目里出现“最大值最小”“最小值最大”“第 k 小”“能否在 X 之内完成”。写法固定外层二分答案内层写一个贪心判定函数。以“把数组分成 k 段连续子数组使最大段和最小”为例判定函数是从左往右累加一旦超过 limit 就另起一段最后统计段数是否不超过 k。def can_split(nums, k, limit): cnt, cur 1, 0 for x in nums: if x limit: # 单个元素就超限直接不可行 return False if cur x limit: cnt 1 cur x else: cur x return cnt k def min_max_sum(nums, k): lo, hi max(nums), sum(nums) # 答案下界是最大元素上界是总和 while lo hi: mid (lo hi) // 2 if can_split(nums, k, mid): hi mid # 可行尝试更小 else: lo mid 1 # 不可行必须放大 return lo下界取max(nums)而不是 0可以少跑几轮这一细节在时间紧张时确实能省下不少时间。判定函数内部一旦发现x limit就直接返回 False避免后续无意义的计算。保存答案的变量要不要单独开取决于你用哪种二分写法左闭右开写法不需要额外变量循环结束的lo就是答案。3.5 并查集连通块与“朋友圈”类问题并查集的出现频率高得惊人而且经常以伪装形式出现“判断两个人是否在同一个圈子”“统计图中连通块数量”“按时间顺序加边问最早何时全部连通”。核心只有两个操作查找根节点带路径压缩、合并两个集合按秩或按大小合并。加上一个 size 数组就能顺便回答“最大连通块有多大”。parent list(range(n 1)) size [1] * (n 1) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路径压缩边走边把节点挂到祖父上 x parent[x] return x def union(a, b): ra, rb find(a), find(b) if ra rb: return False # 已在同一集合可用于判环 if size[ra] size[rb]: ra, rb rb, ra parent[rb] ra size[ra] size[rb] return Trueunion返回 False 说明这条边连接的两个点已经连通加上它就成环这是 Kruskal 判环和“冗余连接”类题目的关键。用并查集统计连通块数量时不要每次都遍历一遍数根而是在合并成功后把计数减一初始计数为 n边界处理更清晰。3.6 单调栈与单调队列区间最值的降维技巧单调栈解决的是“左边或右边第一个比它大、比它小的元素”单调队列解决的是“滑动窗口内的最值”。两者的共同点是用一个栈或双端队列维护候选集合把不可能成为答案的元素及时丢掉复杂度从 O(n²) 降到 O(n)。柱状图中的最大矩形、接雨水、窗口最大值这几道经典题全是从这两个模板长出来的。from collections import deque # 滑动窗口最大值维护一个下标队列对应的值单调递减 def max_sliding_window(nums, k): dq deque() res [] for i, x in enumerate(nums): while dq and nums[dq[-1]] x: dq.pop() # 队尾元素比当前值小永远不可能成为最大值 dq.append(i) if dq[0] i - k: dq.popleft() # 队首滑出窗口 if i k - 1: res.append(nums[dq[0]]) return res队列里存下标而不是值是为了判断队首是否已经滑出窗口这个细节写错的话样例能过、大数据会挂。单调栈的写法与之类似只是弹出条件换成“栈顶元素小于当前值”弹出时即可计算栈顶元素的左右边界。4. 真题实战三道完整题的读题到 AC 全过程会默写模板不等于能在赛场上把题做出来。下面三题覆盖了搜索、构造、树上查询三个方向重点看的是从读题到确定算法的判断过程而不是代码有多长。4.1 网格最大连通块搜索题的通用骨架题面“给定一个 n×m 的网格1 表示陆地0 表示水求最大的四连通陆地面积”。这类题几乎是搜索类题目的固定模式变体包括八连通、统计连通块数量、判断是否被水完全包围。要考虑的关键点有三个是否需要额外标记数组来避免重复访问、是否需要处理边界、递归是否会因为深度过大而爆栈。import sys from collections import deque def max_area(grid): n, m len(grid), len(grid[0]) seen [[False] * m for _ in range(n)] best 0 for i in range(n): for j in range(m): if grid[i][j] 1 and not seen[i][j]: seen[i][j] True q deque([(i, j)]) area 0 while q: x, y q.popleft() area 1 for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny x dx, y dy if 0 nx n and 0 ny m and grid[nx][ny] 1 and not seen[nx][ny]: seen[nx][ny] True q.append((nx, ny)) best max(best, area) return best这里用 BFS 而不是 DFS理由是网格规模通常到达 1000×1000递归写法需要把递归深度设置调大而设置递归深度本身有风险还容易拖慢速度。seen在入队时就置为 True而不是出队时否则同一个格子可能被重复入队队列会变大很多。这套骨架换成八连通只需要改动方向数组换成统计数量只需要把best max(...)改成累加。4.2 字典序第 k 小逐位确定法题面“求 1 到 n 中字典序第 k 小的数”。把数字按字典序排好后它其实构成了一棵十叉树根是空第一层是 1 到 9每个节点下面挂十个子节点。求第 k 小等价于在这棵树上做一次带计数的遍历判断以当前前缀为根的子树有多少个节点如果这个数量小于 k就直接跳过整棵子树否则进入下一层。def count_prefix(prefix, n): # 统计以 prefix 为前缀、且不超过 n 的数字个数 cnt, first, last 0, prefix, prefix while first n: cnt min(last, n) - first 1 first * 10 last last * 10 9 return cnt def kth_number(n, k): cur 1 k - 1 # 第一个数是 1先消耗掉 while k 0: cnt count_prefix(cur, n) if cnt k: k - cnt # 整棵子树都不够跳过 cur 1 else: cur * 10 # 进入子树的第一层 k - 1 return curcount_prefix里用first和last两个变量按层数计算区间长度避免了逐个数枚举这是这道题能否通过大范围数据的关键。整体复杂度是 O(log n × log n)n 到十的九次方也毫无压力。4.3 树上路径查询倍增求 LCA题面“给一棵 n 个节点的树m 次询问每次问两个节点之间路径上的第 k 个点”或者“求两点距离”。这类题的共同前置是最近公共祖先LCA。倍增法最实用预处理每个节点向上 2^j 步的祖先查询时先把深度大的那个节点向上提到同一层再同时向上跳。import sys sys.setrecursionlimit(300000) def build(n, adj): LOG max(1, n.bit_length()) up [[0] * (n 1) for _ in range(LOG)] depth [0] * (n 1) stack [1] visited [False] * (n 1) visited[1] True while stack: # 迭代深搜避免递归过深 u stack.pop() for v in adj[u]: if not visited[v]: visited[v] True depth[v] depth[u] 1 up[0][v] u stack.append(v) for j in range(1, LOG): for i in range(1, n 1): up[j][i] up[j - 1][up[j - 1][i]] return up, depth, LOG def lca(u, v, up, depth, LOG): if depth[u] depth[v]: u, v v, u diff depth[u] - depth[v] for j in range(LOG): if diff j 1: u up[j][u] # 把较深的节点提到同一层 if u v: return u for j in range(LOG - 1, -1, -1): if up[j][u] ! up[j][v]: u, v up[j][u], up[j][v] # 同步上跳直到父节点相同 return up[0][u]建表时用迭代代替递归是为了避开深度一万的链状树。第二次跳出循环时返回的是up[0][u]也就是两个节点共同父节点而不是u本身这一步写反了就必然出错。求出 LCA 后两点距离是depth[u] depth[v] - 2 * depth[lca]路径第 k 个点则先判断 k 小于等于深度差的一半还是位于另一侧按方向逐个上跳。5. 易错点五条最容易丢分的地方5.1 整型溢出数据范围没读全错在哪看到“答案不超过十的九次方”就直接开 int中间计算两个大数相加或者相乘时溢出样例全过、提交全挂。为什么错题目给的是最终答案的范围不是中间过程的取值范围。两个接近十的九次方的数相加中间结果就已经超了涉及乘法时更严重。怎么答对读题时先看数据范围把所有可能超过十的九次方的变量统一换成 64 位整数尤其在 Python 里要注意的是浮点数精度而不是整数但在需要输出整数时不要中途做除法改成先乘后除或直接整数除。5.2 多组输入没清空一组对、多组就错错在哪题目给 T 组数据第一组正确后面几组全错或者答案逐渐累加。为什么错全局数组、列表、计数器在每组数据之间没有重置上一组的结果混进来了。怎么答对固定写成“每组数据处理前重置”的结构把需要清空的变量集中放在循环开头对列表用重新赋值而不是修改元素不要在大数组上做切片清空那样会浪费时间。5.3 浮点比较等于号不能直接用错在哪二分里写if ans mid退出循环或者几何题里用判断共线结果陷入死循环或者误判。为什么错浮点数在计算机里是近似的两个数学上相等的值二进制表示可能有极小差异。怎么答对二分固定迭代次数比如一百次而不是靠相等退出比较用abs(a - b) 1e-9能转成整数运算就转比如把斜率比较改成乘法交叉比较把距离比较改成平方比较。5.4 递归深度一条链就让程序崩溃错在哪树上问题用递归写n 到十万时提交直接出现运行错误样例却完全正常。为什么错链状树的递归深度等于节点数超过了默认的栈空间。怎么答对两种方案一是把递归改成显式栈的迭代写法二是设置递归深度上限。前者更稳尤其在评测环境的栈大小不确定时后者虽然一行搞定但深度特别大时仍可能失败。5.5 特判缺失n 等于一、空集、重边自环错在哪交上去挂了几个测试点一查都是极小规模数据。为什么错常规逻辑在规模为 1、答案为空、图上有重边或自环时会走到特殊分支。怎么答对写完主体逻辑后固定用几组小数据自查n 等于 1、n 等于 2、全部元素相同、没有任何满足条件的答案、图只有一个点和一条自环边。这五组能覆盖绝大多数边界情况花五分钟换几十分。6. 答题技巧四小时的时间分配方案赛场上最亏的不是不会而是会做却没时间写。给出一套经过多次实赛验证的分配方案前 25 分钟扫一遍全部题目边看边把每题按“会写、有思路、完全没思路”分三档并记下每道题的数据范围和样例接下来 40 分钟专攻两题签到题要求一次通过然后 60 分钟处理有思路的中档题优先选分值高、代码短的剩余时间先给“有思路但没写完”的题补完再考虑压轴题的部分分。时间段任务通过标准0 到 25 分钟通读题目标记难度与考点每题的算法方向基本确定25 到 65 分钟两道签到题一次通过不反复提交65 到 125 分钟一到两道中档题至少一道通过另一道拿到部分分125 到 180 分钟攻克思路清晰的难题通过大范围数据的测试点180 到 240 分钟检查边界、补部分分提交前过一遍自测清单两处容易被忽略的动作一是提交前的自测清单写成一个固定流程包含“边界数据、多组数据、极大数据、输出格式”四项逐项检查完才交二是把每道题的算法思路用一行注释写在文件顶部中途换题回来时不用重新读代码。下面这段读取模板建议直接存进自己的代码库遇到输入量大时能省不少时间。import sys def main(): data sys.stdin.buffer.read().split() idx 0 t int(data[idx]); idx 1 out [] for _ in range(t): n int(data[idx]); idx 1 # 业务逻辑写在这里out 里累积答案 out.append(str(n)) sys.stdout.write(\n.join(out)) main()用sys.stdin.buffer.read()一次性读入全部输入再切分比逐行读取快得多尤其是输入里有十万级别整数时差距明显out列表累积后一次性输出避免频繁调用输出函数。注意切分后所有元素都是字节串要显式转成整数。最后说一句个人教训早年我在一场比赛里把会做的第三题拖到最后写结果时间不够只拿到签到题的分排名直接从中间掉到末尾。从那以后我每次开赛都强制走一遍“先扫题、再定档、按档分配时间”的流程写完一题立刻用边界数据自测再决定要不要提交。这个习惯比多背三个算法模板更能提高成绩。希望帮到你。本文还有配套的精品资源点击获取
