信息學競賽寶典 基礎算法

本書的核心是信息學競賽中經常用到的9種基礎算法，包括模擬算法、遞歸算法、枚舉算法、遞推算法、分治算法、貪心算法、排序算法、高精度算法和搜索算法。本書直接以各類競賽真題入手，內容講解上由淺入深，設計合理：對於引入新知識點的題目，書中會提供該題目的完整參考代碼，但隨著讀者對此知識點理解的逐步加深，後續的同類型題目將逐步向僅提供算法思路、提供偽代碼和無任何提示的方式轉變；對於一些思維跨度較大的題目，本書會給出一定的提示；此外，本書還安排了相關習題。

本書中的每一章都分為普及組和提高組兩部分。普及組涉及的內容對應NOIP普及組難度，讀者可初步掌握每種算法的思想和用法；提高組涉及的內容對應 NOIP提高組難度，讀者可復習和提高已講解過的算法內容。

本書既適合作為學習了C++語言和算法入門知識的讀者的進階教材，也適合作為有一定編程基礎的讀者學習算法的獨立用書。

张新华

中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年奥林匹克联赛国家一等奖及亚太与太平洋地区信息学奥林匹克竞赛奖牌。著有《编程竞赛宝典 C++ 语言和算法入门》《青少年编程魔法课堂 C++ 图形化创意编程》

《青少年编程魔法课堂 Python 图形化创意编程》。开发了三维图形化 C++ 编程工具 Dev-C++ 智能开发平台和 Python 可视化界面设计软件 Visual Python。

胡向荣

安徽省信息学竞赛金牌教练。获得中国首届网络管理员大赛亚军，安徽省首届计算机技术大赛一等奖，安徽省信息技术优质课评选一等奖。安庆市教育技术专家、信息技术学科骨干教师、先进教研个人。

葛阳

中学信息技术教师、信息学竞赛教练。曾被评为省级信息技术优秀教师、信息学竞赛优秀辅导员。获得省信息技术优质课比赛一等奖、第二届 CCF 计算机程序设计片段教学比赛二等奖。

第01章 模擬算法

1.1.普及組　/　1

1.1.1.互送禮物　/　1

1.1.2.幽靈粒子　/　3

1.1.3.平臺上的小球　/　4

1.1.4.字符串的展開　/　5

1.1.5.序列變換　/　6

1.1.6.電腦病毒　/　7

1.1.7.貓和老鼠　/　7

1.1.8.推棋子　/　10

1.1.9.奶牛的命運　/　11

1.2.提高組　/　12

1.2.1.蚯蚓　/　12

1.2.2.小球鐘　/　15

1.2.3.立體圖　/　18

1.2.4.時間復雜度　/　20

1.2.5.拱豬游戲　/　23

1.2.6.梭哈　/　25

第02章 遞歸算法

2.1.普及組　/　27

2.1.1.棋子移動　/　27

2.1.2.地盤劃分　/　29

2.1.3.拆分自然數　/　30

2.1.4.魔方陣　/　35

2.1.5.放蘋果　/　36

2.1.6.N皇後問題　/　37

2.1.7.沖突　/　43

2.1.8.油桶問題　/　44

2.1.9.傳球游戲　/　45

2.1.10.全排列問題　/　48

2.1.11.外星人問題　/　50

2.1.12.巡視　/　52

2.1.13.組合問題　/　53

2.1.14.組合與素數　/　54

2.1.15.冪　/　55

2.1.16.Jam記數法　/　56

2.2.提高組　/　57

2.2.1.分形圖１　/　57

2.2.2.分形圖2　/　60

2.2.3.分形之城　/　62

第03章 枚舉算法

3.1.普及組　/　65

3.1.1.火柴棒等式　/　65

3.1.2.求子集　/　67

3.1.3.加急密文　/　68

3.1.4.健康的奶牛　/　69

3.1.5.排隊　/　70

3.1.6.破碎的項鏈　/　72

3.1.7.選擇客棧　/　75

3.1.8.翻轉棋盤　/　78

3.1.9.方塊轉換　/　82

3.1.10.派對燈　/　83

3.2.提高組　/　84

3.2.1.快算24點　/　84

3.2.2.翻轉棋盤2　/　89

3.2.3.時鐘問題　/　89

3.2.4.鋪放矩形塊　/　93

3.2.5.偵探推理　/　95

第04章 遞推算法

4.1.普及組　/　97

4.1.1.儲油點　/　97

4.1.2.數的計數　/　99

4.1.3.過河卒　/　99

4.1.4.挖地雷　/　101

4.1.5.3的個數為偶數　/　102

4.1.6.布陣　/　102

4.1.7.貨幣系統問題　/　104

4.1.8.數的劃分　/　106

4.1.9.樓梯問題　/　107

4.1.10.軍事情報　/　107

4.1.11.極值問題　/　108

4.1.12.x 的出現次數　/　109

4.1.13.貼瓷磚　/　110

4.1.14.二進制計數游戲　/　110

4.2.提高組　/　111

4.2.1.加減取餘　/　111

4.2.2.凸多邊形的三角形剖分　/　113

4.2.3.區域劃分問題　/　114

4.2.4.曲線分割　/　114

4.2.5.二叉樹問題　/　115

4.2.6.雙塔問題　/　116

4.2.7.四塔問題　/　117

4.2.8.青蛙過河　/　118

4.2.9.密文傳送　/　119

4.2.10.安置猛獸　/　120

第05章 分治算法

5.1.普及組　/　122

5.1.1.折半查找法　/　122

5.1.2.逃亡　/　124

5.1.3.解一元三次方程 　/　126

5.1.4.切割金屬棍　/　128

5.1.5.危險的魔法能量　/　129

5.1.6.古代文字　/　129

5.1.7.花費　/　130

5.1.8.跳石頭　/　130

5.1.9.近似整數　/　131

5.1.10.快速冪運算　/　132

5.1.11.單峰排列　/　133

5.1.12.快速模冪　/　134

5.1.13.魔法生物　/　135

5.1.14.後綴樹　/　135

5.1.15.循環比賽　/　136

5.1.16.殘缺棋盤　/　138

5.1.17.電腦組裝　/　141

5.2.提高組　/　142

5.2.1.交叉的梯子　/　142

5.2.2.第k小的數１　/　142

5.2.3.第k小的數2　/　145

5.2.4.第k小的數3　/　146

5.2.5.矩陣中數的查找　/　148

5.2.6.刪除多餘括號　/　149

5.2.7.礦石檢測　/　153

5.2.8.一維最接近點對問題　/　155

5.2.9.二維最接近點對問題　/　157

第06章 貪心算法

6.1.普及組　/　159

6.1.1.刪數問題　/　159

6.1.2.數列極差問題　/　160

6.1.3.均分紙牌　/　161

6.1.4.排座椅　/　162

6.1.5.修理牛棚　/　163

6.1.6.地鼠游戲　/　164

6.1.7.最優分解　/　165

6.1.8.電視節目安排　/　165

6.1.9.閉區間問題　/　167

6.1.10.監測點　/　167

6.1.11.雷達問題　/　168

6.1.12.廣告問題1　/　169

6.1.13.廣告問題2　/　170

6.1.14.空間定位1　/　171

6.1.15.空間定位2　/　172

6.1.16.引水入城　/　173

6.1.17.加工生產調度　/　175

6.1.18.做作業　/　176

6.2.提高組　/　177

6.2.1.預算　/　177

6.2.2.穿越時空　/　177

6.2.3.釣魚　/　178

6.2.4.田忌賽馬　/　182

6.2.5.觀光公交　/　186

第07章 排序算法

7.1.普及組　/　188

7.1.1.常用排序法　/　188

7.1.2.雙關鍵字排序　/　194

7.1.3.緊急集合　/　195

7.2.提高組　/　197

7.2.1.求逆序對數　/　197

7.2.2.絕境求生　/　199

7.2.3.學生排隊　/　201

7.2.4.火柴排隊　/　201

第08章 高精度算法

8.1.普及組　/　203

8.1.1.被限制的加法　/　203

8.1.2.高精度加法　/　204

8.1.3.蜜蜂路線　/　207

8.1.4.高精度減法　/　207

8.1.5.最大值減最小值　/　208

8.1.6.高精度數除以低精度數1　/　208

8.1.7.高精度數除以低精度數2　/　209

8.1.8.高精度乘法　/　210

8.1.9.交流　/　210

8.1.10.最大乘積　/　211

8.1.11.盒子與球　/　212

8.1.12.國王游戲　/　212

8.2.提高組　/.213

8.2.1.萬進制高精度運算　/　213

8.2.2.高精度冪　/　214

8.2.3.分組　/　215

8.2.4.高精度階乘　/　215

8.2.5.國債計算　/　216

8.2.6.組合數的高精度算法　/　217

8.2.7.高精度數除以高精度數　/　219

第09章 搜索算法

9.1.普及組　/　221

9.1.1.四色地圖　/　221

9.1.2.迷宮問題　/　224

9.1.3.騎士遍歷1　/　229

9.1.4.騎士遍歷2　/　232

9.1.5.機器人搬重物　/　234

9.1.6.單詞接龍　/　235

9.1.7.互素組　/　236

9.1.8.最小的木棍　/　236

9.1.9.解藥還是毒藥　/　238

9.1.10.棋盤分割　/　238

9.2.提高組　/　240

9.2.1.數獨游戲　/　240

9.2.2.康托展開　/　242

9.2.3.康托展開逆運算　/　244

9.2.4.八數碼問題　/　246

9.2.5.魔板問題　/　261

9.2.6.蟲食算　/　262

9.2.7.15數碼問題　/　263

9.2.8.靶形數獨　/　264

9.2.9.撲克游戲　/　267

9.2.10.Mayan游戲　/　270