藍橋杯程序競賽真題解析及學習指導

金百東：東北師範大學，從事程序設計與教學30年，碩士學歷，現任遼寧師範大學副教授。擔任歷屆藍橋杯程序設計競賽指導教師，多年遼寧省大學生ACM程序競賽指導教師。開發了本科生畢業論文選題管理系統、本科生創新創業項目管理系統、課程計算機管理系統，並已獲得應用。。在省級以上雜誌發表論文18篇，已編寫出版《C++ STL基礎及應用》、《Java web編程技術實用教程》、《Java設計模式及應用案例》、《Android簡明程序設計》等多部教材。

目錄

 

第1章競賽預備知識1

1.1C語言常用函數1

1.1.1字符串數值轉換函數1

1.1.2字符串函數1

1.2STL標準模板庫3

1.2.1STL算法函數3

1.2.2STL容器11

第2章基礎題21

2.1窮舉法真題21

【例21】（第7屆）抽簽21

【例22】（第4屆）買不到的數目22

【例23】（第7屆）四平方和23

【例24】（第5屆）拼接平方數23

【例25】（第4屆）帶分數25

2.2中等數學真題26

【例26】（第13屆）因數平方和26

【例27】（第12屆）和與乘積28

【例28】（第12屆）楊輝三角形31

2.3取余真題35

【例29】（第8屆）K倍區間35

【例210】（第13屆）取模36

【例211】（第13屆）近似GCD37

2.4最大公約數40

【例212】（第11屆）循環小數40

【例213】（第10屆）等差數列41

2.5排序真題42

【例214】（第13屆）重新排序42

【例215】（第14屆）平均45

2.6其他基本類型真題47【例216】（第6屆）奇怪的數列47

【例217】（第13屆）X進制減法49

【例218】（第13屆）數的拆分51

【例219】（第14屆）公因數匹配55

【例220】（第14屆）棋盤58

【例221】（第13屆）積木畫59

【例222】（第8屆）小計算器61

第3章時間65

【例31】（第9屆）航班時間65

【例32】（第11屆）回文日期67

【例33】（第8屆）日期問題69

第4章字符串71

【例41】（第10屆）最長子序列71

【例42】（第6屆）密文搜索72

【例43】（第5屆）排列序數73

【例44】（第9屆）等腰三角形74

【例45】（第11屆）重復字符串76

【例46】（第11屆）字符串編碼77

【例47】（第13屆）內存空間79

【例48】（第14屆）子串簡寫82

第5章規律題85

【例51】（第9屆）約瑟夫環85

【例52】（第5屆）生物芯片87

【例53】（第10屆）數正方形88

【例54】（第14屆）平方差90

【例55】（第10屆）後綴表達式91

第6章二分法95

【例61】（第9屆）遞增三元組95

【例62】（第14屆）買二贈一96

【例63】（第8屆二分法）分巧克力98

【例64】（第13屆）第K小的和100

【例65】（第13屆國賽）卡牌101

【例66】（第11屆）整數拼接103

【例67】（第13屆）統計子矩陣105

第7章優先隊列與堆棧109

【例71】(第15屆)爬山109

【例72】（第13屆）砍竹子111

【例73】(第14屆)最大開支114

【例74】(第14屆)整數刪除117

【例75】（第13屆）掃描遊戲120

【例76】（第8屆）正則問題124

第8章基本遞歸127

8.1遞歸引入127

8.2基本例題130

8.3遞歸真題135

【例81】（第13屆）最大數字135

【例82】（第4屆國賽）橫向打印二叉樹137

第9章圖論141

9.1深度優先搜索141

9.2真題分析146

【例91】（第4屆）剪格子146

【例92】（第7屆）路徑之謎148

【例93】（第5屆求割點）危險系數150

【例94】（第9屆）版本分支152

【例95】（第13屆）掃雷155

【例96】（第8屆）發現環160

9.3寬度優先搜索162

9.4真題分析165

【例97】（第6屆BFS）穿越雷區165

【例98】（第9屆）全球變暖167

【例99】（第10屆）大胖子走迷宮169

9.5並查集172

9.6真題分析176

【例910】（第8屆）合根植物176

【例911】（第10屆）修改數組178

【例912】（第13屆）推導部分和180

【例913】（第11屆）網絡分析183

9.7單源最短路徑186

9.7.1Dijkstra算法186

9.7.2SPFA算法188

9.8真題分析191

【例914】（第13屆）出差191

【例915】（第11屆）限高桿193

9.9最小生成樹與最近公共祖先197

9.10真題分析203

【例916】（第14屆）網絡穩定性203

第10章動態規劃208

10.1線性動態規劃208

10.2真題分析208

【例101】（第7屆）密碼脫落208

【例102】（第12屆）砝碼稱重210

【例103】（第8屆）包子湊數211

【例104】（第13屆）李白打酒加強版213

【例105】（第10屆）最優包含216

【例106】（第14屆）接龍數列218

10.3區間動態規劃219

10.4真題分析224

【例107】（第9屆）搭積木224

【例108】（第14屆）更小的數227

【例109】（第14屆）合並石子229

10.5樹形動態規劃232

10.6真題分析233

【例1010】（第12屆）左孩子右兄弟233

【例1011】（第6屆）生命之樹234

10.7數位動態規劃237

10.8真題分析243

【例1012】（第12屆）二進制問題243

第11章區間運算算法246

11.1樹狀數組246

11.1.1引入246

11.1.2原理246

11.1.3示例分析249

11.2線段樹254

11.2.1引入254

11.2.2基本操作255

11.2.3示例分析259

11.3ST表269

11.4真題分析271

【例111】（第13屆）最大公約數271

【例112】（第5屆）小朋友排隊274

【例113】（第8屆）油漆面積276

第12章數論281

12.1快速冪取模281

12.1.1遞歸快速冪281

12.1.2遞推快速冪281

12.2矩陣快速冪282

12.3歐拉函數283

12.4歐拉定理283

12.5擴展歐幾裏得284

12.6中國剩余定理285

12.7典型例題286

【例121】（第14屆）互素數的個數286

【例122】（第5屆）斐波那契288

【例123】（第9屆）倍數問題291

第13章計算幾何294

13.1基礎知識294

13.2進階知識295

13.2.1求任意多邊形面積295

13.2.2皮克定理296

13.2.3辛普森積分297

【例131】（第11屆）平面切分298

【例132】（第4屆）車輪軸跡300

第14章遊戲題305

14.1巴什博弈305

14.2尼姆博弈306

14.3真題分析308

【例141】（第5屆）矩陣翻硬幣308

【例142】（第8屆）填字母遊戲309

參考文獻312