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