简介：这份压缩包收录了百度之星编程大赛历年试题，面向备战算法竞赛的程序员、计算机专业学生以及希望系统提升编程与算法能力的开发者。资源共116个文件，以jpg、css、htm、js等类型为主，压缩包整体仅983KB，其中htm页面便于直接浏览赛题页面，css与js辅助呈现样式和交互，jpg则保存了试题截图或样例图片，结构清晰便于检索。目前已有624人学习下载。内容覆盖基础编程、数据结构、排序与搜索、动态规划、贪心算法、逻辑推理、数学应用以及字符串处理等经典题型，能帮助读者通过历年真题熟悉百度之星的出题风格、难度梯度和考察重点。学习者既可对照题目逐题训练，也可以借此总结常见算法模板与解题策略，从而在备赛和日常算法学习中更有方向。 很多人准备百度之星的时候，第一反应就是到处翻历年试题，然后按年份一套一套往下刷。但我带队这几年，看过太多人用这个姿势复习，最后复赛止步。刷真题本身没有错，错的是不知道百度之星和ACM/ICPC这类传统竞赛的命题思路有明显区别。这篇文章我就从历年试题的命题规律、考点分布、备考节奏、以及我实际做题和带选手踩过的坑这几个角度，把这事彻底讲透。无论你是在校大学生、备战高中信息学竞赛的学生，还是工作后想通过竞赛提升算法能力的开发者，只要你打算认真打一次百度之星，这篇应该能帮你少走大半年的弯路。
1. 先搞清楚对手：百度之星的赛制和题目长什么样
1.1 从报名到决赛的完整流程
百度之星（Astar）从2005年办到现在，中间虽然经历过一些赛制调整，但主线一直是：初赛、复赛、决赛三个阶段。初赛通常在线进行，题目难度贴近校赛到省赛之间，题量在5到8题，比赛时间2到3小时。复赛还是线上，但难度明显上了一个台阶，题型更接近区域赛的中低档题。决赛则是现场赛，时长通常在4到5小时，除了纯算法题，偶尔会有偏工程、偏场景的题目出现，比如模拟一个搜索排序流程、设计一个路线规划策略等等，这也是百度之星和企业竞赛联系最紧密的地方。
很多第一次参赛的同学会问一个问题：百度之星到底算不算ACM？我的看法是，它保留了大量ACM的核心考点，但比纯粹的ACM竞赛更看重“读题能力”和“场景建模能力”。题目会把算法包在一个业务故事里，比如“外卖骑手要在多个商家取餐再送到多个用户手里，怎么规划最短路径”——剥掉这个故事外壳，底下就是一道状态压缩动态规划或者最短路变形。想拿高分，第一步不是冲算法模板，而是练习一眼看懂外壳下到底考什么。
1.2 和传统ACM竞赛的三个核心差异
第一，数据范围并没有想象中那么吓人。很多题卡的是“你会不会想到这个解法”，而不是“你能不能手搓一个高级数据结构”。早年有些真题的标答其实就是朴素动态规划加一两个小优化。第二，部分分设计更明显。线上赛的评测规则里，常常会存在“小数据点过一部分就给一部分分”的情况，这意味着暴力写得稳也能捞到不少分，这点和ACM的“要么AC要么零分”完全不同。第三，题面长度普遍偏长，场景描述多，不仔细读题真的会漏条件。我见过一个选手把一道模拟题当成图论题做了半小时，发现样例跑不出来，回头再看题面才发现漏了这个业务分支。
所以，备考百度之星的核心思路应该是：把历年真题按“知识点+场景建模”两条线去拆，而不是按年份一套套刷完就完事。
2. 历年真题里的常客：按知识点盘点
2.1 高频考点分布表
我根据近几年选手回忆和公开题解，把百度之星题目里最常出现的考点整理成了一份优先级清单。这里的“优先级”是基于投入产出比给出的，不是绝对的难度排序。
| 知识点 | 出现频率 | 典型考法 | 备考优先级 |
|---|---|---|---|
| 动态规划 | 极高 | 背包、区间DP、树形DP、状态压缩DP | 最高 |
| 图论 | 高 | 最短路、最小生成树、拓扑排序 | 高 |
| 贪心与排序 | 高 | 任务调度、区间选择、价值排序 | 高 |
| 基础数学 | 高 | 快速幂、GCD/LCM、素数筛、逆元 | 高 |
| 字符串处理 | 中 | KMP、Trie、字符串哈希 | 中 |
| 数据结构 | 中 | 线段树、树状数组、并查集 | 中 |
| 思维/构造 | 中 | 找规律、反证、极值构造 | 中 |
| 高级图论 | 低 | 网络流、二分图匹配 | 低 |
这个表其实反映了一个很关键的事实：动态规划在百度之星里的地位几乎是不可撼动的。原因很简单，动态规划是一种能同时考察“模型抽取能力”和“代码实现能力”的题型，一个题从暴力到记忆化到状态优化，区分度非常自然。所以准备这个比赛，动态规划绝对不能只背模板，一定要练到“看到一个题能自己设计出状态定义和转移方程”的程度。
2.2 动态规划的具体考法变化
早年的百度之星DP题，背包和区间DP比较多，比如给你一堆物品、一个容量，求最大价值；或者给你一个序列，让你切分成若干段，每段有个代价函数，求总代价最小。这类题属于“穿上马甲也认识”的类型，靠模板能应付。
但近几年的真题明显在往两个方向倾斜：一是DP和数据结构结合，比如需要你用线段树或单调队列优化转移，这就不光是会写状态方程的问题了；二是DP的状态设计本身变得隐蔽，很多题第一眼看上去像贪心，或者像模拟，你需要先证明贪心是错的，才能倒逼自己往DP的方向想。我刷题经验是，当你觉得一个题“贪心好像能过但样例总有一个不对”的时候，大概率就是DP题，而且往往需要压缩一维状态。
2.3 图论与场景建模的绑定
图论同样是高频考点，但它和ACM的区域赛图论题有个区别：百度之星的图论题特别喜欢套“路线规划”和“资源分配”的壳。比如给出一个城市的地铁线路图，每个站点的换乘时间不同，求从起点到终点的最短时间。这个题本质是最短路，但边权的计算可能要写一个函数，而不是直接读入。这种包装对于习惯了裸题的选手来说很容易慌，所以我建议备考时多练习“先建模、再套板子”的节奏。
3. 一道“真题型”的完整拆解：把思路过程摊开来讲
3.1 题目描述（与历年风格一致的典型模型）
我不拿某一年具体原题出来，因为很多题目只存在于参赛者的记忆里，公开版本的描述可能不准确。但我可以给你一道和历年风格高度一致的代表性题目，它综合了最短路、状态压缩DP和业务场景建模三个点，这类题在复赛和决赛中反复出现。
题目大意：小明要在一个城市里完成送货任务。城市有 n 个地点（编号1到n），和 m 条双向道路，每条道路有一个通行时间。小明从地点1出发，需要在 k（k ≤ 8）个指定的地点各完成一次送货，完成所有送货后回到地点1。另外，每个送货地点有一个最早可到达时间限制，如果到达得太早，需要等到限制时间才能交付。请问完成全部任务并返回起点所需的最短时间是多少？
数据范围：n ≤ 10000，m ≤ 50000，k ≤ 8。
3.2 拿到题之后的前几分钟该怎么想
先把业务外壳剥掉。这个题不管说的是送货、巡检还是打卡，底层就是“起点 + k个必经点 + 回到起点，求最短路径”。k 只有8，这是一个极其强烈的信号，基本就是状态压缩DP没跑了。为什么？因为 k 小到可以做 2^k 的枚举，而 n 和 m 又太大，不允许你直接搜索全排列。
接下来要解决的核心问题是：任意两个关键点之间，以及起点和每个关键点之间的最短距离是多少。这个子问题用最短路来解决，跑 k+1 次 Dijkstra 就够了。这里有个细节容易被忽略：k=8，意味着关键点总共9个，哪怕每个点都跑一次全图最短路径，复杂度是 9 * O((n+m)logn)，对10000个点和50000条边来说完全不是问题。但如果 k 很小时你选择用 Floyd，复杂度直接 O(n^3) = 10^12，当场爆炸。这个选型差距，就是能不能AC的分水岭。
更有经验的选手会再往前多想一步：既然关键点只有9个，那真正参与“排列枚举”的路径，只有 9×9 = 81 条，而不是整张图。所以做法就清晰了：先用Dijkstra预处理出关键点之间的两两最短路，然后把问题变成一个规模只有9个点的“旅行商问题”，用状压DP解决。
3.3 从暴力到满分的三条路径
第一步：暴力枚举所有访问顺序。
k 个点全排列，最多 8! = 40320 种，每个排列算一遍路径长度，对每个排列再查表累加。配合预处理出来的关键点两两距离，这个暴力的总操作量其实才 40320 × 8 ≈ 30万，完全能跑。如果时间限制紧，这已经能拿不少分。
第二步：状态压缩DP。
状态设计成 dp[mask][i]，mask 表示已经访问过的关键点集合，i 表示当前最后停在第 i 个关键点。转移就枚举下一个要访问的关键点 j（不在mask里），把 dp[mask][i] 加上 d[i][j] 更新到 dp[mask | (1 << j)][j] 上。初始化 dp[1 << i][i] = d[起点][i]，最终答案取所有 dp[全部mask][i] + d[i][起点] 的最小值。这一步的复杂度是 2^8 × 8 × 8 = 16384 量级，低到不可思议，配合最短路预处理，满分稳稳的。
第三步：处理“最早可到达时间”。
这题的隐藏难点在于那个最早可到达时间。如果到早了要等待，意味着把“到达时间限制”计算进走这段路的真实花费。这里正确的做法是把等待时间也折算进边权里：如果通过最短路预计算出从 i 到 j 的理论最短时间是 t，但到达 j 的时刻早于限制 time[j]，那实际用时就是 time[j] - 当前时刻。所以预处理的距离矩阵不能在原图上直接算，要在期望到达时刻的约束下调。实现时可以先忽略等待时间，跑出 d[i][j]，然后在DP转移时再统一补上“到达 j 时刻若早于限制时间则等待”的差额。这个细节，就是典型的不看数据终究会踩空的点。
下面是核心DP部分的参考代码：
#include <bits/stdc++.h> using namespace std; const long long INF = 4e18; long long d[12][12]; // 关键点之间的最短时间（启动前已用Dijkstra算出） long long limit[12]; // 每个关键点的最早可交付时间，limit[0]为起点，设为0 long long dp[1 << 9][12]; int keyPoint[12]; // 关键点在原图中的节点编号，keyPoint[0]为起点 long long solve(int k) { for (int mask = 0; mask < (1 << k); mask++) for (int i = 0; i < k; i++) dp[mask][i] = INF; for (int i = 1; i < k; i++) { // 从起点直接到第 i 个关键点，如果提前到达就等待 long long arr = d[0][i]; if (arr < limit[i]) arr = limit[i]; dp[1 << i][i] = arr; } for (int mask = 1; mask < (1 << k); mask++) { for (int i = 1; i < k; i++) { if (!(mask & (1 << i))) continue; if (dp[mask][i] >= INF) continue; for (int j = 1; j < k; j++) { if (mask & (1 << j)) continue; long long arr = dp[mask][i] + d[i][j]; if (arr < limit[j]) arr = limit[j]; dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], arr); } } } long long ans = INF; int full = (1 << k) - 1; for (int i = 1; i < k; i++) { if (dp[full][i] >= INF) continue; ans = min(ans, dp[full][i] + d[i][0]); } return ans; }关键点有两个：一个是等待时间的补算是发生在“到达关键点”时，不是发生在“离开关键点”时；另一个是起点（第0号关键点）不参与mask的压缩，只作为源点，这样代码处理起来干净得多。这个题的完整思路就是百度之星中“中高难度题”的典型套路：一个常规算法套一层业务约束，剥壳顺利就是模板题，剥壳失败就是无从下手的难题。
4. 用真题备考的三个阶段
4.1 第一阶段：按知识点纵向突破
不要一上来就整套卷限时做。正确做法是把近五年的真题先按知识点拆开。比如你打算花两周补DP，那就把历年真题里所有和DP相关的题全部挑出来，一天一道，每题不仅要把代码写AC，还要把状态定义、转移方程、初始化过程和边界条件写在笔记里。这阶段的核心目标不是量，而是“同类题的共性提取”。你至少得总结出：哪些题适合用区间DP，哪些题适合状压，哪些题需要用数据结构优化转移。
我在带选手时还要求他们做一件事：每道题写一行“它为什么不是别的算法”。比如这道题为什么不是贪心？因为局部最优不等于全局最优，可以举一个反例。这一行字，会在复赛考场上救你很多次。
4.2 第二阶段：按年份限时模拟
到了中后期，开始整套做题。时间节奏我建议这样定：初赛套题按比赛时长的80%来限时，复赛套题按比赛时长100%来限时。为什么要压缩初赛时间？因为线上初赛时你一定会紧张，紧张会让你的手速下降，平时练得比比赛时间更紧，上场才不会慌。
模拟的时候要严格遵守一条纪律：不AC完整套题不看题解。很多人模拟赛变成“写一半卡住，然后打开题解看一眼思路，关掉继续写”，这等于给自己作弊。脑子记不住独立解题的路径，考场上很容易断片。宁可一套题只AC两题，也要是真正自己想出来的两题。
4.3 第三阶段：复盘错题和读题训练
模拟赛之后的复盘价值超过刷三套新题。复盘时不要只看“这题解法是什么”，要重点问自己：“我在什么位置开始偏的？”是没看懂题？是看懂题但不知道用什么模型？还是知道模型但代码写错了？每道错题都要把偏差点标出来，再用一句话总结成提醒，比如“看到k≤10，必须想状压”“看到最短路+数量少的关键点，先预处理好近邻矩阵”。
同时，在冲刺期保留一个习惯：每天读5道真题题面，不写代码，只写“这个题考什么、用什么复杂度能过、大致思路是什么”。这个训练便宜但极其有效，因为百度之星读题门槛高，很多人挂在第一步。
5. 那些真题里学过但我还是踩空的坑
5.1 数据范围陷阱和输入输出细节
第一个常见坑是int爆炸。很多题目路径长度加起来会超过2^31-1，看似不大，但你在写代码时随手用int就会WA。我的建议非常朴素：所有涉及距离、代价、累加和的变量一律用 long long，不要在比赛时赌“这题不会超int”。
第二个坑是初始化INF。很多人习惯用0x3f3f3f3f，这个值在ACM里很常用，但如果你的算法里有“数组值加和”的转移，比如 dp[u] + d[i][j]，两个INF相加变成大于INF的诡异值，比较大小的时候就会出问题。稳妥做法是设 INF = 4e18 或 1e18，转移时先判断一下前驱状态是否大于等于 INF 再决定要不要继续。代码块里我已经用了这个写法，这不是风格问题，是细节决定AC还是WA的问题。
第三个坑是输入输出的性能。n到10000、m到50000的题，用 cin 流输入只要忘了关同步就可能TLE。每次比赛开始前，把下面三行当成肌肉记忆：
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);5.2 线上赛的时间分配和提交策略
很多选手线上赛有个坏习惯：一道题卡了四十分钟还死磕不放，总想着“再想五分钟就能出来”，结果一道题做不出来，后面的题也没时间看。合理的策略是开赛先花五分钟把所有题都读一遍，给每道题标一个“我会/我可能想得出来/我不会”的标记。前十到二十分钟，先把“会”的题全部AC；剩下时间优先做“可能”的题；最后半小时，如果什么思路都没有，就不要追求AC纯正解了，用暴力、模拟、甚至直接枚举拿部分分，哪怕多捞一个测试点都是赚的。
百度之星这类企业竞赛，部分分机制比ACM友好得多，你不需要每道题都AC。功利一点说，把中档题做满、难题拿部分分，名次比死磕一道压轴题高得多。
5.3 考场上最容易被忽略的边界条件
最后提醒一批我在复盘时看到过无数次的边界：n=1的时候，整个图只有起点一个点，你的最短路还能跑吗？k=0的时候，没有关键点，答案直接是0，但是 if 判断漏了怎么办？所有关键点里包含起点的情况你处理了吗？有些题关键点列表中可能包含起点或重复点，题目不会明确提醒你，你需要自己判重。
从刷第一套题开始，就养成“每次提交前把边界列出来检查一遍”的习惯。这跟你背了多少模板无关，纯粹是纪律问题。百度之星真正的难度往往不在算法的上限，而在你能不能把所有细节都处理干净。历年真题刷到最后的境界是：看到任何一道题，你脑子里立刻浮现出它可能埋下的坑和对应的处理方案。等你有了这种反射，初赛拿高名次、复赛稳住阵脚就都不是问题了。
本文还有配套的精品资源，点击获取
