简介：这份资源是百度公司年度编程竞赛「百度之星」的历年试题合集，面向程序员、计算机专业学生及算法爱好者，用于系统刷题、备赛训练与提升算法与数据结构能力。压缩包共收录116个文件，以jpg图片、css样式表、htm网页、js脚本为主，另有少量png与gif素材，整体约983KB，属于轻量级网页形式整理的赛题资料，便于本地浏览与检索。目前已有629人学习下载，具备一定的参考热度。试题内容覆盖基础编程、数组链表栈队列树图等数据结构、排序搜索动态规划贪心等经典算法，以及逻辑推理、数学应用与字符串处理等方向，可帮助读者熟悉竞赛评分标准与时间限制，通过限时模拟与解题思路分析查漏补缺，逐步建立完整的算法知识体系，为后续竞赛与职业发展打下基础。
1. 从一套历年试题看算法竞赛的底层能力映射
如果你正在准备算法竞赛，或者想通过真题来检验自己的数据结构与算法功底，这套百度之星编程大赛历年试题会是一个很实在的练习入口。百度之星从2005年办到现在，题目风格一直偏重思维密度和工程实现之间的平衡，不是那种纯拼模板的场次。它适合已经掌握基础语法、想从“会写代码”过渡到“能解非常规问题”的开发者，也适合带学生做集训的教练拿来当模拟赛题源。我见过不少人刷了一堆在线判题平台的水题，一到限时赛就卡壳，核心问题不是编码速度，而是缺少对题目意图的快速拆解能力。这套历年试题的价值就在于，它把不同年份的命题思路摊开给你看，让你在反复推演中建立自己的解题决策树。
2. 试题结构拆解：从输入规模反推算法选型
2.1 题目类型分布与难度梯度
百度之星的题目大致可以分成几类：模拟与贪心、动态规划、图论、数论与组合数学、字符串处理，以及少量计算几何。早期年份（2005—2010）题目数量少、单题分值高，一道题往往需要完整实现一个带状态转移的模拟系统；中期（2011—2017）开始引入多组测试数据和更严格的时空限制，动态规划和图论题占比明显上升；近年（2018至今）则偏向多知识点融合，比如一道题同时涉及二分答案和网络流建模。
拿到一套试题后，我一般先做一件事：把每道题的输入规模抄下来，列成表。因为输入规模直接决定了你能不能用某个复杂度的算法。比如 n ≤ 20 大概率是状压或搜索，n ≤ 1000 可能是 O(n²) 的动态规划，n ≤ 10⁵ 基本要求 O(n log n)，n ≤ 10⁶ 就得考虑 O(n) 或带小常数的 O(n log n)。
| 输入规模 | 可接受复杂度 | 常见算法方向 |
|---|---|---|
| n ≤ 20 | O(2ⁿ) | 状压DP、DFS+剪枝 |
| n ≤ 100 | O(n³) | Floyd、区间DP |
| n ≤ 1000 | O(n²) | 朴素DP、二分图匹配 |
| n ≤ 10⁵ | O(n log n) | 排序+贪心、线段树、Dijkstra |
| n ≤ 10⁶ | O(n) | 前缀和、双指针、线性筛 |
这张表不是死规矩，但能帮你快速排除明显不可行的方向。很多翻车现场就是没看规模直接上手写了个 O(n²) 的暴力，结果大数据点全红。
2.2 从题面关键词定位考点
题面里的某些词几乎就是考点信号。看到“最少需要多少步”先想BFS或二分答案；看到“方案数”且模一个大质数，大概率是组合计数或DP；看到“字典序最小”往往要贪心加排序；看到“连通块”“路径”优先考虑并查集或图遍历。百度之星的题面通常不会直接告诉你用什么算法，但关键词密度比一般OJ高，读题时拿笔圈出来能省不少试错时间。
我习惯在本地建一个 Markdown 笔记，每道题记录三行：题面关键词、第一反应算法、实际通过算法。刷完三套之后回看，第一反应的准确率会明显上升。这个习惯比单纯追求AC数量有用得多。
2.3 本地环境搭建与测试数据构造
历年试题通常只提供题面和少量样例，完整测试数据需要自己构造。我一般用 Python 写生成器，因为写起来快，配合 subprocess 调用编译好的 C++ 程序做对拍。
# gen.py：生成随机测试数据 import random import sys seed = int(sys.argv[1]) # 从命令行接收随机种子，方便复现 random.seed(seed) n = random.randint(1, 1000) print(n) # 根据题目要求生成具体数据，这里以n个整数为例 arr = [random.randint(-10**9, 10**9) for _ in range(n)] print(' '.join(map(str, arr)))这个生成器的关键参数是 seed，固定种子后每次生成的数据完全一致，方便定位问题。n 的范围要覆盖题目给的最小和最大边界，数组元素的取值范围也要按题面设定，不要自己随意扩大，否则可能生成题目约束之外的非法数据。
对拍脚本用 bash 写一个循环：
#!/bin/bash # 对拍：比较暴力程序和优化程序的输出 for i in $(seq 1 500); do python3 gen.py $i > input.txt ./brute < input.txt > out_brute.txt ./fast < input.txt > out_fast.txt if ! diff -q out_brute.txt out_fast.txt > /dev/null; then echo "差异出现在种子 $i" break fi done echo "对拍结束"暴力程序不求效率，只求逻辑正确，通常用最直白的递归或多重循环实现。优化程序是你真正要提交的版本。两者输出一致才说明优化没有引入逻辑错误。500 组随机数据能覆盖大部分边界情况，如果时间允许可以加到 2000 组。
3. 核心算法模块的实战写法与参数调优
3.1 动态规划的状态设计与滚动数组
百度之星的DP题很少考裸的背包，更多是让你自己设计状态。以一道典型的“区间合并”类问题为例，状态定义成 dp[i][j] 表示从 i 到 j 的最优值，转移时枚举分割点 k。这种区间DP的复杂度是 O(n³)，n 超过 500 就危险，需要优化。
// 区间DP模板：dp[i][j]表示区间[i,j]的最优解 const int MAXN = 505; int dp[MAXN][MAXN]; int sum[MAXN]; // 前缀和，用于快速计算区间代价 int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; } // 枚举区间长度 for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; dp[i][j] = INF; // 枚举分割点 for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]); } } } cout << dp[1][n] << endl; return 0; }这里 sum 数组是前缀和，把区间代价的计算从 O(n) 降到 O(1)。dp 数组初始化为 INF 表示不可达，len 从 2 开始是因为长度为 1 的区间不需要合并，代价为 0。如果 n 到了 3000，这个 O(n³) 写法必超时，常见优化是用四边形不等式把内层枚举降到 O(n)，但那个推导容易出错，比赛时如果没把握不如换个思路。
滚动数组是另一种常见优化。当 dp[i][j] 只依赖上一层时，可以把第一维压掉。比如 0-1 背包的 dp[j] 从后往前更新，完全背包从前往后更新。这个细节每年都有人写反，写反了不会报错，但答案就是不对，属于典型的玄学翻车点。
3.2 图论建模：从题面到邻接表
图论题的第一步永远是建图。百度之星的图论题经常把图隐藏在一个故事里，比如“城市之间的航线”“任务之间的依赖关系”。识别出节点和边之后，剩下的就是套模板。
// 邻接表建图 + Dijkstra堆优化 vector<pair<int,int>> adj[MAXN]; // {to, weight} int dist[MAXN]; bool visited[MAXN]; void dijkstra(int start) { priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; fill(dist, dist + MAXN, INF); dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (visited[u]) continue; // 跳过已确定最短路的节点 visited[u] = true; for (auto [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }visited 数组的作用是防止重复扩展，没有它算法仍然正确但会变慢。priority_queue 默认是大根堆，用 greater<> 改成小根堆。dist 初始化为 INF 要足够大，一般取 0x3f3f3f3f 而不是 INT_MAX，因为后者在加法时会溢出。这些细节在本地测试时可能看不出问题，一到评测机就出各种奇怪结果。
如果边权有负数，Dijkstra 就失效了，得换 Bellman-Ford 或 SPFA。百度之星出负权图的频率不高，但一旦出现就是区分度所在。判断方法很简单：看题面有没有“消耗”“收益”这类可正可负的描述。
3.3 数论与组合数学的预处理技巧
数论题在百度之星里通常以“求方案数模 1e9+7”的形式出现。核心预处理是阶乘和逆元，用费马小定理在模质数下求逆。
const int MOD = 1e9 + 7; const int MAXN = 1000005; long long fact[MAXN], inv_fact[MAXN]; long long power(long long a, long long b) { long long res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } void init() { fact[0] = 1; for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD; inv_fact[MAXN-1] = power(fact[MAXN-1], MOD - 2); for (int i = MAXN - 2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD; } long long C(int n, int m) { if (m < 0 || m > n) return 0; return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD; }MAXN 要开到题目数据范围的上限，宁可多开一点也不要少开，数组越界在评测机上可能表现为段错误，也可能表现为答案错误，排查起来很痛苦。power 函数是快速幂，复杂度 O(log MOD)。inv_fact 从后往前递推，利用了 inv_fact[i] = inv_fact[i+1] * (i+1) 这个关系。C 函数里先判断 m 的合法性，避免调用方传入非法参数导致数组越界。
4. 避坑与排查：那些年我踩过的评测机红线
4.1 多组数据未清空全局数组
现象：本地跑单组数据完全正确，提交后第一个测试点就WA。 原因：题目要求多组输入，但全局数组残留了上一组的数据。 解决：在每组数据处理前用 fill 或 memset 重置所有全局数组，或者干脆把数组定义在循环内部。我一般用 fill(begin, end, 0) 而不是 memset，因为 fill 对非POD类型也安全。
4.2 整数溢出导致答案错误
现象：小数据对，大数据错，且错误值看起来毫无规律。 原因：中间运算结果超过了 int 范围，比如两个 10⁹ 的数相乘。 解决：把涉及乘法的变量声明为 long long，并且在乘法前就完成类型转换。常见写法是 1LL * a * b，而不是 a * b 之后再转。这个坑在数论题和DP题里出现频率极高。
4.3 递归深度过大导致栈溢出
现象：本地小数据正常，大数据直接崩溃或返回错误结果。 原因：DFS 递归层数超过了系统默认栈大小。 解决：把递归改成显式栈的迭代写法，或者在本地编译时加 -Wl,-stack_size 参数扩大栈空间。但评测机不一定允许你改栈大小，所以最稳妥的还是迭代。我一般在写 DFS 之前先估算最大深度，超过 10⁵ 就直接上迭代。
4.4 输入输出格式与题面要求不一致
现象：答案逻辑正确，但评测返回格式错误。 原因：多输出了空格、换行，或者大小写与题面不符。 解决：严格对照题面的输出格式说明，注意“每个测试点后输出一个空行”这类细节。我习惯在本地用 diff 对比自己的输出和样例输出，肉眼看不出来的空格差异 diff 会直接标出来。
4.5 时间复杂度估算过于乐观
现象：本地跑最大数据用了 3 秒，评测机返回超时。 原因：评测机性能通常比本地开发机差，而且可能有多组数据叠加。 解决：把本地测试时间乘以 3 作为安全余量。如果本地都接近 1 秒，基本必超时。优化方向包括：减少不必要的内存分配、把 vector 换成静态数组、用 scanf/printf 替代 cin/cout。
5. 从刷题到实战：一套可复用的训练节奏
刷历年试题最怕的是“刷完就忘”。我的做法是每套题刷两遍：第一遍限时模拟，第二遍只做第一遍没做出来的题，并且强制自己写题解。题解不要求长篇大论，但必须包含三个部分：题目考什么、我的第一反应为什么不对、正确解法的关键步骤。这个习惯坚持三个月，解题速度会有肉眼可见的提升。
具体节奏可以这样安排：每周一套题，周一到周五每天抽 1 小时做一道，周末抽 3 小时做限时模拟。限时模拟时把手机放远，只留草稿纸和编译器。做完后不要立刻看别人的题解，先自己对着测试数据调，调不出来再去看。这个“卡住”的过程才是能力增长最快的时候。
另外，百度之星的题目有一个特点：很多题的标程并不长，但思维跨度大。这意味着你不需要背很多模板，但需要把每个模板的适用条件和边界条件吃透。比如二分答案，什么时候用左闭右开、什么时候用左闭右闭，check 函数怎么写才能保证单调性，这些细节比模板本身重要得多。
我现在的习惯是，每学一个新算法，先找三道百度之星里对应的真题做，做完再回头补理论。这样理论不是空中楼阁，而是有具体题目作为锚点。从那以后我每次遇到新题，都会先问自己：这题的数据规模允许什么复杂度？题面关键词指向哪个考点？我的第一反应有没有遗漏边界情况？这三个问题问完再动手，翻车概率会低很多。希望帮到你。
本文还有配套的精品资源，点击获取
