本书为百度之星大赛试题集。百度之星由百度公司举办，自2005年至今已举办16届，累计参赛学生近30万，涌现出楼天成、戴文渊等明星冠军选手，被视为国内程序员的“黄埔军校”和“造星工场”。

本书汇集2005～2020年初赛、复赛、决赛试题的解析，提供具有参考价值的解题思路，有助于编程爱好者提升程序设计、算法设计能力，是难得的教学辅助读物。本书汇集2005～2020年初赛、复赛、决赛试题的解析，提供具有参考价值的解题思路，有助于编程爱好者提升程序设计、算法设计能力，是难得的教学辅助读物。

近几年，伴随科技发展，尤其是人工智能时代的到来，编程作为 “人机对话”的语言，其重要性与日俱增。从2020年9月起，编程已陆续纳入全国大中小学必修课，在全国范围内的学校正式推行。由此可以看出，国家对人工智能、编程技术的人才需求在扩大。

百度作为中国互联网乃至全球人工智能领域的知名企业，一直坚持科技创新，为优秀编程人才的培养不懈努力。2005年，百度之星大赛开始举办，它是一项旨在展示学生创新能力及编写程序、分析和解决问题能力的年度型竞赛。17年来，大赛累计参赛学生已接近30万名，覆盖上千所高校，大量优秀人才从中脱颖而出，其中不少已成为互联网领域的中坚力量。大赛也因此被视为国内程序员的“黄埔军校”和“造星工场”。

鉴于此，我们编写了《百度之星题集（2005—2021年）》。本书汇集了2005—2021年百度之星大赛大部分的初赛、复赛、决赛的试题和解析。全书将试题按年度划分，每一年为一章，提供了具有一定参考价值的解题思路。

大赛题型主要考察基础算法和程序设计能力等，需要做题者使用程序设计语言（包括C、C++、Pascal及Java等）解决挑战性算法问题。其中，决赛试题由来自百度不同业务部门的资深工程师拟定，兼具竞技性和趣味性之余，还具备很高的行业价值，如最近几年的语音识别算法、搜索引擎攻防游戏、贪吃蛇AI算法、躲避拥堵路线规划AI算法、深度学习计算图优化、量子电路等。赛题的演化就像一面镜子，映照出科学的更迭与技术的日新月异。

Create for more，是百度之星大赛的理念。编者相信，技术的力量可以创造更美好的生活；  将技术之薪火传递给更多技术爱好者、从业者，也是本书出版的初心。相信本书能提高广大学生的编程、创新能力和分析与解决问题的能力，同时它也能作为教学辅助读物，对程序设计、算法等相关课程的拓展与提升贡献一份力量。

百度之星大赛已走过17年，感谢所有为百度之星初赛、复赛、决赛赛题设计及系统开发倾注大量心血的同仁们，没有你们当年自虐般的绞尽脑汁、用心良苦，就没有如今这部沉甸甸的题集。

感谢所有关心学生计算机能力提升、热心组织参赛的领导和老师们，感谢全国高校ACM集训队、中小学NOI集训队教练和同学们的长情陪伴，鞭策和见证了百度之星赛题的不断升级。

感谢杭州电子科技大学OJ平台（acm.hdu.edu.cn）多年以来对百度之星大赛的支持，感谢全国高等学校计算机教学与产业实践资源建设专家委员会（TIPCC）和其指导建设的“码蹄集”OJ平台在题集整理及测试过程中的诸多帮助。后续本题集的内容也会放到“码蹄集”平台上（matiji.net/baiduzhixing）供编程爱好者们练习使用。

本书自编写以来，获得了众多朋友的耐心帮助和指导。尤其是清华大学出版社的卢先和副社长，感谢您对书籍出版的大力支持；  感谢房鸣、郭嵩山、姜学峰、刘春英、刘勇、罗国杰、宋友、邬晓钧、杨亚、张学辉等各位老师对书籍出版工作的关心；  感谢中国科学院信息工程研究所的何永全、李开运对本书内容的测试反馈；  感谢张倩、刘磊、乔文慧、许超等同事在本书撰写中发挥的重要作用。

在此，向所有参加过百度之星大赛的选手、参与过评奖工作的老师、加入过组织工作的伙伴，致以诚挚的谢意。也欢迎广大编程爱好者在OJ社区交流，一起探求更好的解题思路。

编者

2021年11月

第1章百度之星 2021

1.1初赛第一场

迷失

愿望幽灵

鸽子

萌新

二分

毒瘤数据结构题

流年烹茶

猎人杀

1.2初赛第二场

签到

随机题意

魔怔

净化

水题

树上游走

模拟

被 EI 加 0 了

1.3初赛第三场

数字游戏

网格路径

虫族基地

环上游走

怀旧游戏

二叉树

数据结构

1.4复赛

Palindrome

Add or Multiply 1

Subtraction

Just a Data Structure Problem

Add or Multiply 2

Just Another Data Structure

Problem

1.5决赛

第2章百度之星2020

2.1初赛第一场

Ant

Chess

Discount

Fight

Game

Graph

Intersection

Permutation

2.2初赛第二场

civilization

dec

drink

function

gpa

matrix

mosquito

rotate

2.3初赛第三场

car

cloth

covid

distance

drink

hanoi

poker

solo

2.4复赛

Battle for Wosneth

Binary Addition

Range kth Maximum Query

Link Cut Tree

Battle for Wosneth2

Query on the Tree

2.5决赛

量子比特（Qubit）

第3章百度之星2019

3.1初赛第一场

Polynomial

Game

Mindis

Str

Seq

Subway

3.2初赛第二场

度度熊与数字

度度熊与排列

度度熊与运算式1

度度熊与组题

度度熊与整数集合

度度熊与运算式2

3.3初赛第三场

最短路1

最短路2

算术

反向传播

Min

权值

3.4初赛第四场

Strassen

杏杏和正方形和矩形

五教练的教学

唯一指定树

wls的树

Totori’s Switching Game

3.5复赛

Diversity

Transformation

Quasi Binary Search Tree

Maximum or Sum

Expected Remainder

APSP on Cactus

3.6决赛

深度学习计算图调度优化

第4章百度之星2018

4.1资格赛

调查问卷

子串查询

整数规划

点集划分

序列计数

三原色图

4.2初赛第一场

度度熊拼三角

度度熊学队列

度度熊剪纸条

度度熊看球赛

度度熊玩数组

度度熊算算术

4.3初赛第二场

degree

hex

odds

p1m2

ratio

rect

4.4复赛

没有兄弟的舞会

序列期望

带劲的and和

公共子序列

棋盘上的旅行

带劲的多项式

4.5决赛

躲避拥堵路线规划

第5章百度之星2017

5.1资格赛

度度熊保护村庄

度度熊的王国战略

度度熊与邪恶大魔王

度度熊的午饭时光

寻找母串

5.2初赛第一场

小C的倍数问题

数据分割

路径交

迷宫出逃

今夕何夕

度度熊的01世界

5.3初赛第二场

Chess

Factory

路径计数

打怪兽2

度度熊的交易计划

小小粉丝度度熊

5.4复赛

Arithmetic of Bomb

Arithmetic of Bomb II

Pokémon GO

Pokémon GO II

Valley Numer

Valley Numer II

5.5决赛

贪吃的度度蛇

第6章百度之星2016

6.1资格赛

Problem A

Problem B

Problem C

Problem D

Problem E

6.2初赛第一场

All X

排排坐

小度爱零食

D游戏

BD串

Gym课

6.3初赛第二场

区间的价值

刷题计划

瞬间移动

货物运输

区间交

中位数计数

6.4复赛

D++游戏

K个联通块

拍照

XOR游戏

带可选字符的多字符串匹配

矩阵方程的解

6.5决赛

判断title与query的相关性

第7章百度之星2015

7.1资格赛第一场

大搬家

列变位法

IP聚合

放盘子

下棋

单调区间

7.2初赛第一场

超级赛亚ACMer

找连续数

序列变换1

KPI

三阶魔方

7.3初赛第二场

追星族

连接的管道

棋盘占领

魔法因子

序列变换2

翻转游戏

7.4复赛

数长方形

弹吉他

行路难

蜀道难

最强密码

平衡大师

7.5决赛

搜索引擎攻防游戏

第8章百度之星2014

8.1资格赛

DiskSchedule

Energy Conversion

Labyrinth

Xor Sum

8.2初赛第一场

BestFinancing

Chess

CycleCocycle

Grids

8.3初赛第二场

Information

JZP Set

party

Scenic Popularity

8.4复赛

FindNumbers

Race

The Game of Coins

The Patterns

Query on the tree

8.5决赛

精准广告推荐

第9章百度之星2013

9.1区域赛第一场

平衡负载

水果忍者

9.2区域赛第二场

du熊的机器人

乘法测试

9.3区域赛第三场

最短路

螺旋困境

糖果

9.4月赛第一场

伪随机数生成器

Sigma

9.5月赛第二场

Fir

Apple

9.6月赛第三场

Spacing

数列加密

9.7决赛

语音识别系统

第10章百度之星2012

10.1初赛第一场

度度熊就是要第一个出场

小小度刷礼品

集合的交并

10.2初赛第二场

度度熊就是要刷排名第一

度度熊的礼物

网页聚类

小王子的表演

10.3复赛第一场

蛛网

改变数字

最右交点

10.4复赛第二场

轮子上的度度熊

消灭病毒

BD翻译器

10.5决赛

麻将

第11章百度之星2011

11.1初赛第一场

图标排列

篮球场

度度熊大战僵尸

11.2初赛第二场

圆环

园艺布置

数据还原

11.3复赛

跳跃

股票代码

数据校验

11.4决赛

得州扑克游戏

第12章百度之星2010

12.1复赛第一场

A+B问题

URL规范化

12.2复赛第二场

购物搜索调研

内存碎片

蜗牛

12.3决赛

植物大战僵尸

第13章百度之星2009

13.1初赛

火柴游戏

电子商务平台商品推荐问题

葫芦娃

争车位

Sorry，打错了

树形控件

交点覆盖

我的地盘

13.2复赛

网页的相似度计算

拼车

13.3决赛

Spider

限制性图灵测试，搜索引擎的

非法用户检测

第14章百度之星2008

14.1初赛第一场

广告排名区间

LZW网页判重

钉子与木板

圆面覆盖

14.2初赛第二场

圆内五角星

传输方案规划

公平数

成语纠错

14.3复赛

寻找所有的同构象

黑白树

度度熊与西瓜

14.4决赛

直升机大战 Air Strike

Helicopters

第15章百度之星2007

15.1初赛

水果开会时段

大话西游与数字游戏

繁忙的会议室预定问题

SQL中的SELECT语句

百度时间

实习生小胖的百度网页

过滤器

Wii游戏开始啦！

百度的高级搜索方法

15.2复赛

好心的出租车司机

15.3决赛

CS1.5AI

第16章百度之星2006

16.1初赛

百度语言翻译机

饭团的烦恼

变态的比赛规则

蝈蝈计分

座位调整

剪刀石头布

16.2复赛

另类杀人游戏

空中飞猴

星球大战

彩球游戏

追捕

16.3决赛

俄罗斯方块

第17章百度之星2005

17.1初赛

连续正整数

重叠区间大小

字符串替换

低频词过滤

17.2决赛

八方块移动游戏

感言

感言

百度之星，看神仙打架

楼天城——2005—2006年第一届、第二届百度之星程序设计大赛冠军

范智恺——2008年第四届百度之星程序设计大赛冠军

冯国栋——2009年第五届百度之星程序设计大赛冠军

杭航——2010年第六届百度之星程序设计大赛冠军

艾庆兴——2012年第八届百度之星程序设计大赛冠军

蒙澎权——2014年第十届百度之星程序设计大赛冠军

吴卓杰——2015年第十一届百度之星程序设计大赛冠军

黄宇扬——2016年第十二届百度之星程序设计大赛冠军

何柱——2017年第十三届百度之星程序设计大赛冠军

毕克——2018年第十四届百度之星程序设计大赛冠军

张哲宇——2019年第十五届百度之星程序设计大赛冠军

李白天——2020年第十六届百度之星程序设计大赛冠军

胡赵阳——2021年第十七届百度之星程序设计大赛“小星星奖项”冠军

王思齐——2021年第十七届百度之星程序设计大赛“常规奖项”冠军

施韩原——2019—2021年百度之星程序设计大赛命题人

邓明扬——2021年第33届国际信息学奥林匹克竞赛金牌得主

岛娘——仙女座CEO、Meta Network & GameCreator联合创始人

桃李不言，伴大赛成长

邬晓钧——清华大学ACM国际大学生程序设计竞赛集训队主教练

罗国杰——北京大学ACM国际大学生程序设计竞赛集训队主教练

郭嵩山——中山大学ACM国际大学生程序设计竞赛集训队主教练

杨亚——北京邮电大学ACM国际大学生程序设计竞赛集训队主教练

刘勇——北京化工大学ACM国际大学生程序设计竞赛集训队主教练

刘春英——杭州电子科技大学ACM国际大学生程序设计竞赛集训队主教练

技术信仰，望星辰大海

李莹——百度集团副总裁、百度集团首席信息官

谢天——百度B2B业务总经理

李盈——百度智慧城市事业部副总经理

徐菁——前百度副总裁

张高——前百度教育事业部总经理

杨斌——百度之星程序设计大赛早期项目负责人

本书提供了具有参考价值的解题思路，有助于编程爱好者提升程序设计、算法设计能力，是难得的教学辅助读物。