本書為百度之星大賽試題集。百度之星由百度公司舉辦，自2005年至今已舉辦16屆，累計(jì)參賽學(xué)生近30萬，涌現(xiàn)出樓天成、戴文淵等明星冠軍選手，被視為國內(nèi)程序員的黃埔軍校和造星工場。
本書匯集2005～2020年初賽、復(fù)賽、決賽試題的解析，提供具有參考價(jià)值的解題思路，有助于編程愛好者提升程序設(shè)計(jì)、算法設(shè)計(jì)能力，是難得的教學(xué)輔助讀物。本書匯集2005～2020年初賽、復(fù)賽、決賽試題的解析，提供具有參考價(jià)值的解題思路，有助于編程愛好者提升程序設(shè)計(jì)、算法設(shè)計(jì)能力，是難得的教學(xué)輔助讀物。
前言
近幾年，伴隨科技發(fā)展，尤其是人工智能時(shí)代的到來，編程作為 人機(jī)對(duì)話的語言，其重要性與日俱增。從2020年9月起，編程已陸續(xù)納入全國大中小學(xué)必修課，在全國范圍內(nèi)的學(xué)校正式推行。由此可以看出，國家對(duì)人工智能、編程技術(shù)的人才需求在擴(kuò)大。
百度作為中國互聯(lián)網(wǎng)乃至全球人工智能領(lǐng)域的知名企業(yè)，一直堅(jiān)持科技創(chuàng)新，為優(yōu)秀編程人才的培養(yǎng)不懈努力。2005年，百度之星大賽開始舉辦，它是一項(xiàng)旨在展示學(xué)生創(chuàng)新能力及編寫程序、分析和解決問題能力的年度型競賽。17年來，大賽累計(jì)參賽學(xué)生已接近30萬名，覆蓋上千所高校，大量優(yōu)秀人才從中脫穎而出，其中不少已成為互聯(lián)網(wǎng)領(lǐng)域的中堅(jiān)力量。大賽也因此被視為國內(nèi)程序員的黃埔軍校和造星工場。
鑒于此，我們編寫了《百度之星題集（20052021年）》。本書匯集了20052021年百度之星大賽大部分的初賽、復(fù)賽、決賽的試題和解析。全書將試題按年度劃分，每一年為一章，提供了具有一定參考價(jià)值的解題思路。
大賽題型主要考察基礎(chǔ)算法和程序設(shè)計(jì)能力等，需要做題者使用程序設(shè)計(jì)語言（包括C、C 、Pascal及Java等）解決挑戰(zhàn)性算法問題。其中，決賽試題由來自百度不同業(yè)務(wù)部門的資深工程師擬定，兼具競技性和趣味性之余，還具備很高的行業(yè)價(jià)值，如最近幾年的語音識(shí)別算法、搜索引擎攻防游戲、貪吃蛇AI算法、躲避擁堵路線規(guī)劃AI算法、深度學(xué)習(xí)計(jì)算圖優(yōu)化、量子電路等。賽題的演化就像一面鏡子，映照出科學(xué)的更迭與技術(shù)的日新月異。
Create for more，是百度之星大賽的理念。編者相信，技術(shù)的力量可以創(chuàng)造更美好的生活； 將技術(shù)之薪火傳遞給更多技術(shù)愛好者、從業(yè)者，也是本書出版的初心。相信本書能提高廣大學(xué)生的編程、創(chuàng)新能力和分析與解決問題的能力，同時(shí)它也能作為教學(xué)輔助讀物，對(duì)程序設(shè)計(jì)、算法等相關(guān)課程的拓展與提升貢獻(xiàn)一份力量。
百度之星大賽已走過17年，感謝所有為百度之星初賽、復(fù)賽、決賽賽題設(shè)計(jì)及系統(tǒng)開發(fā)傾注大量心血的同仁們，沒有你們當(dāng)年自虐般的絞盡腦汁、用心良苦，就沒有如今這部沉甸甸的題集。
感謝所有關(guān)心學(xué)生計(jì)算機(jī)能力提升、熱心組織參賽的領(lǐng)導(dǎo)和老師們，感謝全國高校ACM集訓(xùn)隊(duì)、中小學(xué)NOI集訓(xùn)隊(duì)教練和同學(xué)們的長情陪伴，鞭策和見證了百度之星賽題的不斷升級(jí)。
感謝杭州電子科技大學(xué)OJ平臺(tái)（acm.hdu.edu.cn）多年以來對(duì)百度之星大賽的支持，感謝全國高等學(xué)校計(jì)算機(jī)教學(xué)與產(chǎn)業(yè)實(shí)踐資源建設(shè)專家委員會(huì)（TIPCC）和其指導(dǎo)建設(shè)的碼蹄集OJ平臺(tái)在題集整理及測試過程中的諸多幫助。后續(xù)本題集的內(nèi)容也會(huì)放到碼蹄集平臺(tái)上（matiji.net/baiduzhixing）供編程愛好者們練習(xí)使用。
本書自編寫以來，獲得了眾多朋友的耐心幫助和指導(dǎo)。尤其是清華大學(xué)出版社的盧先和副社長，感謝您對(duì)書籍出版的大力支持； 感謝房鳴、郭嵩山、姜學(xué)峰、劉春英、劉勇、羅國杰、宋友、鄔曉鈞、楊亞、張學(xué)輝等各位老師對(duì)書籍出版工作的關(guān)心； 感謝中國科學(xué)院信息工程研究所的何永全、李開運(yùn)對(duì)本書內(nèi)容的測試反饋； 感謝張倩、劉磊、喬文慧、許超等同事在本書撰寫中發(fā)揮的重要作用。
在此，向所有參加過百度之星大賽的選手、參與過評(píng)獎(jiǎng)工作的老師、加入過組織工作的伙伴，致以誠摯的謝意。也歡迎廣大編程愛好者在OJ社區(qū)交流，一起探求更好的解題思路。
編者
2021年11月
目錄
第1章百度之星 2021
1.1初賽第一場
迷失
愿望幽靈
鴿子
萌新
二分
毒瘤數(shù)據(jù)結(jié)構(gòu)題
流年烹茶
獵人殺
1.2初賽第二場
簽到
隨機(jī)題意
魔怔
凈化
水題
樹上游走
模擬
被 EI 加 0 了
1.3初賽第三場
數(shù)字游戲
網(wǎng)格路徑
蟲族基地
環(huán)上游走
懷舊游戲
二叉樹
數(shù)據(jù)結(jié)構(gòu)
1.4復(fù)賽
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復(fù)賽
Battle for Wosneth
Binary Addition
Range kth 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初賽第二場
度度熊與數(shù)字
度度熊與排列
度度熊與運(yùn)算式1
度度熊與組題
度度熊與整數(shù)集合
度度熊與運(yùn)算式2
3.3初賽第三場
最短路1
最短路2
算術(shù)
反向傳播
Min
權(quán)值
3.4初賽第四場
Strassen
杏杏和正方形和矩形
五教練的教學(xué)
唯一指定樹
wls的樹
Totoris Switching Game
3.5復(fù)賽
Diversity
Transformation
Quasi Binary Search Tree
Maximum or Sum
Expected Remainder
APSP on Cactus
3.6決賽
深度學(xué)習(xí)計(jì)算圖調(diào)度優(yōu)化
第4章百度之星2018
4.1資格賽
調(diào)查問卷
子串查詢
整數(shù)規(guī)劃
點(diǎn)集劃分
序列計(jì)數(shù)
三原色圖
4.2初賽第一場
度度熊拼三角
度度熊學(xué)隊(duì)列
度度熊剪紙條
度度熊看球賽
度度熊玩數(shù)組
度度熊算算術(shù)
4.3初賽第二場
degree
hex
odds
p1m2
ratio
rect
4.4復(fù)賽
沒有兄弟的舞會(huì)
序列期望
帶勁的and和
公共子序列
棋盤上的旅行
帶勁的多項(xiàng)式
4.5決賽
躲避擁堵路線規(guī)劃
第5章百度之星2017
5.1資格賽
度度熊保護(hù)村莊
度度熊的王國戰(zhàn)略
度度熊與邪惡大魔王
度度熊的午飯時(shí)光
尋找母串
5.2初賽第一場
小C的倍數(shù)問題
數(shù)據(jù)分割
路徑交
迷宮出逃
今夕何夕
度度熊的01世界
5.3初賽第二場
Chess
Factory
路徑計(jì)數(shù)
打怪獸2
度度熊的交易計(jì)劃
小小粉絲度度熊
5.4復(fù)賽
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初賽第二場
區(qū)間的價(jià)值
刷題計(jì)劃
瞬間移動(dòng)
貨物運(yùn)輸
區(qū)間交
中位數(shù)計(jì)數(shù)
6.4復(fù)賽
D 游戲
K個(gè)聯(lián)通塊
拍照
XOR游戲
帶可選字符的多字符串匹配
矩陣方程的解
6.5決賽
判斷title與query的相關(guān)性
第7章百度之星2015
7.1資格賽第一場
大搬家
列變位法
IP聚合
放盤子
下棋
單調(diào)區(qū)間
7.2初賽第一場
超級(jí)賽亞ACMer
找連續(xù)數(shù)
序列變換1
KPI
三階魔方
7.3初賽第二場
追星族
連接的管道
棋盤占領(lǐng)
魔法因子
序列變換2
翻轉(zhuǎn)游戲
7.4復(fù)賽
數(shù)長方形
彈吉他
行路難
蜀道難
最強(qiáng)密碼
平衡大師
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復(fù)賽
FindNumbers
Race
The Game of Coins
The Patterns
Query on the tree
8.5決賽
精準(zhǔn)廣告推薦
第9章百度之星2013
9.1區(qū)域賽第一場
平衡負(fù)載
水果忍者
9.2區(qū)域賽第二場
du熊的機(jī)器人
乘法測試
9.3區(qū)域賽第三場
最短路
螺旋困境
糖果
9.4月賽第一場
偽隨機(jī)數(shù)生成器
Sigma
9.5月賽第二場
Fir
Apple
9.6月賽第三場
Spacing
數(shù)列加密
9.7決賽
語音識(shí)別系統(tǒng)
第10章百度之星2012
10.1初賽第一場
度度熊就是要第一個(gè)出場
小小度刷禮品
集合的交并
10.2初賽第二場
度度熊就是要刷排名第一
度度熊的禮物
網(wǎng)頁聚類
小王子的表演
10.3復(fù)賽第一場
蛛網(wǎng)
改變數(shù)字
最右交點(diǎn)
10.4復(fù)賽第二場
輪子上的度度熊
消滅病毒
BD翻譯器
10.5決賽
麻將
第11章百度之星2011
11.1初賽第一場
圖標(biāo)排列
籃球場
度度熊大戰(zhàn)僵尸
11.2初賽第二場
圓環(huán)
園藝布置
數(shù)據(jù)還原
11.3復(fù)賽
跳躍
股票代碼
數(shù)據(jù)校驗(yàn)
11.4決賽
得州撲克游戲
第12章百度之星2010
12.1復(fù)賽第一場
A B問題
URL規(guī)范化
12.2復(fù)賽第二場
購物搜索調(diào)研
內(nèi)存碎片
蝸牛
12.3決賽
植物大戰(zhàn)僵尸
第13章百度之星2009
13.1初賽
火柴游戲
電子商務(wù)平臺(tái)商品推薦問題
葫蘆娃
爭車位
Sorry，打錯(cuò)了
樹形控件
交點(diǎn)覆蓋
我的地盤
13.2復(fù)賽
網(wǎng)頁的相似度計(jì)算
拼車
13.3決賽
Spider
限制性圖靈測試，搜索引擎的
非法用戶檢測
第14章百度之星2008
14.1初賽第一場
廣告排名區(qū)間
LZW網(wǎng)頁判重
釘子與木板
圓面覆蓋
14.2初賽第二場
圓內(nèi)五角星
傳輸方案規(guī)劃
公平數(shù)
成語糾錯(cuò)
14.3復(fù)賽
尋找所有的同構(gòu)象
黑白樹
度度熊與西瓜
14.4決賽
直升機(jī)大戰(zhàn) Air Strike
Helicopters
第15章百度之星2007
15.1初賽
水果開會(huì)時(shí)段
大話西游與數(shù)字游戲
繁忙的會(huì)議室預(yù)定問題
SQL中的SELECT語句
百度時(shí)間
實(shí)習(xí)生小胖的百度網(wǎng)頁
過濾器
Wii游戲開始啦！
百度的高級(jí)搜索方法
15.2復(fù)賽
好心的出租車司機(jī)
15.3決賽
CS1.5AI
第16章百度之星2006
16.1初賽
百度語言翻譯機(jī)
飯團(tuán)的煩惱
變態(tài)的比賽規(guī)則
蟈蟈計(jì)分
座位調(diào)整
剪刀石頭布
16.2復(fù)賽
另類殺人游戲
空中飛猴
星球大戰(zhàn)
彩球游戲
追捕
16.3決賽
俄羅斯方塊
第17章百度之星2005
17.1初賽
連續(xù)正整數(shù)
重疊區(qū)間大小
字符串替換
低頻詞過濾
17.2決賽
八方塊移動(dòng)游戲
感言
感言目錄
百度之星，看神仙打架
樓天城20052006年第一屆、第二屆百度之星程序設(shè)計(jì)大賽冠軍
范智愷2008年第四屆百度之星程序設(shè)計(jì)大賽冠軍
馮國棟2009年第五屆百度之星程序設(shè)計(jì)大賽冠軍
杭航2010年第六屆百度之星程序設(shè)計(jì)大賽冠軍
艾慶興2012年第八屆百度之星程序設(shè)計(jì)大賽冠軍
蒙澎權(quán)2014年第十屆百度之星程序設(shè)計(jì)大賽冠軍
吳卓杰2015年第十一屆百度之星程序設(shè)計(jì)大賽冠軍
黃宇揚(yáng)2016年第十二屆百度之星程序設(shè)計(jì)大賽冠軍
何柱2017年第十三屆百度之星程序設(shè)計(jì)大賽冠軍
畢克2018年第十四屆百度之星程序設(shè)計(jì)大賽冠軍
張哲宇2019年第十五屆百度之星程序設(shè)計(jì)大賽冠軍
李白天2020年第十六屆百度之星程序設(shè)計(jì)大賽冠軍
胡趙陽2021年第十七屆百度之星程序設(shè)計(jì)大賽小星星獎(jiǎng)項(xiàng)冠軍
王思齊2021年第十七屆百度之星程序設(shè)計(jì)大賽常規(guī)獎(jiǎng)項(xiàng)冠軍
施韓原20192021年百度之星程序設(shè)計(jì)大賽命題人
鄧明揚(yáng)2021年第33屆國際信息學(xué)奧林匹克競賽金牌得主
島娘仙女座CEO、Meta Network & GameCreator聯(lián)合創(chuàng)始人
桃李不言，伴大賽成長
鄔曉鈞清華大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
羅國杰北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
郭嵩山中山大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
楊亞北京郵電大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
劉勇北京化工大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
劉春英杭州電子科技大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽集訓(xùn)隊(duì)主教練
技術(shù)信仰，望星辰大海
李瑩百度集團(tuán)副總裁、百度集團(tuán)首席信息官
謝天百度B2B業(yè)務(wù)總經(jīng)理
李盈百度智慧城市事業(yè)部副總經(jīng)理
徐菁前百度副總裁
張高前百度教育事業(yè)部總經(jīng)理
楊斌百度之星程序設(shè)計(jì)大賽早期項(xiàng)目負(fù)責(zé)人
書單推薦
