ACM-ICPC 基本算法

第1章ACM與算法概述1
1.1 ACM-ICPC簡介1
1.1.1歷史1
1.1.2比賽規則2
1.1.3區域和全球決賽2
1.2算法與問題求解2
1.2.1算法的定義3
1.2.2問題求解3
1.3算法的特性5
1.3.1算法的要素5
1.3.2算法的基本特性6
1.4算法的描述6
1.4.1基本控制結構的描述7
1.4.2 C算法描述的約定9
1.5算法分析11
1.5 .1算法的評價標準11
1.5.2算法的時間複雜性12
1.5.3算法的空間複雜性13
1.6算法的優化14
1.6.1全局優化14
1.6.2局部優化15
1.6.3算法優化中的注意事項16

第2章求值法18
2.1算法設計思想18
2.2典型例題18
2.2.1求最大數18
2.2.2中位數和平均數19
2.2.3判斷閏年20
2.2.4素數21
2.2.5判斷天數23
2.2.6大整數階乘24
2.3實戰訓練25
2.3.1求年長者25
2.3.2一元二次方程求根26
2.3.3三角形的面積26
2.3.4最大公約數26
2.3.5求整數的位數27
2.3.6孿生素數27
2.3.7求圓的周長27
2.3.8階乘求和28
2.3.9計算圓周率28
2.3.10求閏年29
2.3.11連續自然數的平方和29
2.3.12大整數求和問題29
2.3.13公牛和母牛30
2.3.14十六進制的運算30
2.3.15親和數31
2.4小結31

第3章遞推法32
3.1算法設計思想32
3.2典型例題33
3.2.1兔子繁殖問題33
3.2. 2最大公約數問題34
3.2.3猴子吃桃問題35
3.2.4楊輝三角問題36
3.2.5穿越沙漠問題37
3.2.6方格塗色問題39
3.3實戰訓練40
3.3.1求年齡40
3.3.2斐波那契數列求和40
3.3.3絕不後退41
3.3.4取數41
3.3.5王小二的刀41
3.3.6蜜蜂回家42
3.3.7富二代的生活費42
3.3.8平面分割問題43
3.3.9特殊性質的數43
3.3.10求天數44
3.3.11上樓梯44
3.3.12開獎44
3.3.13月之數45
3.3.14洗牌45
3.3.15飛躍懸崖46
3.4小結46

第4章遞歸法47
4.1算法設計思想47
4.2典型例題47
4.2.1母牛繁殖問題47
4.2.2輸出各位數字48
4.2.3最大值問題49
4.2.4計算x的n次冪51
4.2.5數組逆置52
4.2.6漢諾塔問題53
4.3實戰訓練54
4.3.1遞歸取數54
4.3.2遞歸拆數55
4.3.3求素數之積55
4.3.4反轉字符串56
4.3.5公共子序列56
4.3.6賣鴨子56
4.3.7進制轉換57
4.3.8角谷定理57
4.3.9楊輝三角58
4.3.10質因數分解58
4.3.11全排列58
4.3.12特殊性質的數59
4.3.13放盤子59
4.3.14無序劃分60
4.3.15回文數60
4.4小結60

第5章枚舉法62
5.1算法設計思想62
5.2典型例題62
5.2.1百雞問題62
5.2.2水仙花數63
5.2.3完數64
5.2.4可逆素數65
5.2.5串匹配問題67
5.2.6最小公倍數問題69
5.2.7獄吏問題71
5.3實戰訓練72
5.3.1素數篩選問題72
5.3.2紙幣換硬幣73
5.3.3勾股數問題73
5.3.4生理週期問題73
5.3.5構造比例數74
5.3.6自守數75
5.3.7誰是竊賊75
5.3.8獨特的數76
5.3.9握手問題76
5.3.10趣味數學77
5.3.11暴力枚舉之絕對值77
5.3.12回文數78
5.3.13逆序對數79
5.3.14放牧79
5.3.15餐廳點餐80
5.4小結81

第6章模擬法82
6.1算法設計思想82
6.2典型例題82
6.2.1電梯問題82
6.2.2撲克洗牌問題83
6.2.3進站時間模擬85
6.2.4消息隊列86
6.2.5清除雜草89
6.2.6機器人的指令92
6.3實戰訓練93
6.3.1報數問題93
6.3.2無限次冪94
6.3.3金幣工資95
6.3.4進制轉換95
6.3.5卡片魔術96
6.3.6木棍上的螞蟻96
6.3.7串聯數字97
6.3.8多連塊覆蓋問題98
6.3.9括號表達式99
6.3.10假幣問題100
6.3.11會議安排101
6.3.12取火柴遊戲102
6.3.13取石子遊戲103
6.3.14偽造的美元103
6.3.15 HTML瀏覽器104
6.4小結105

第7章分治法106
7.1算法設計思想106
7.2典型例題106
7.2.1折半查找106
7.2.2金塊問題108
7.2.3尋找第二的問題110
7.2.4歸併排序112
7.2.5大整數乘法114
7.2.6二叉樹遍歷115
7.3實戰訓練118
7.3.1數組二分求和118
7.3.2子序列最大值118
7.3.3棋盤覆蓋118
7.3.4最接近點對問題120
7.3.5第k小元素問題120
7.3.6循環賽日程表問題121
7.3.7找假幣問題121
7.3.8 n階分形122
7.3.9 m叉樹問題122
7.3.10電話查重123
7.3.11樹的有效點對124
7.3.12回文串交換125
7.3. 13史密斯數125
7.3.14矩陣乘積126
7.3.15士兵排隊問題126
7.4小結127

第8章貪心法128
8.1算法設計思想128
8.2典型例題129
8.2.1找零錢問題129
8.2.2最優裝載130
8.2.3哈夫曼編碼132
8.2.4單源最短路徑136
8.2.5埃及分數問題139
8.2.6多機調度問題141
8.3實戰訓練144
8.3.1小船過河問題144
8.3.2紀念品分組144
8.3 .3數列極差問題145
8.3.4函數求底問題145
8.3.5開心的金明146
8.3.6小明坐車問題147
8.3.7田忌賽馬147
8.3.8裝箱問題148
8.3.9刪數問題148
8.3 .10移動紙牌問題149
8.3.11組合正整數149
8.3.12活動安排問題150
8.3.13多人接水問題1 150
8.3.14多人接水問題2 151
8.3.15搬桌子問題151
8.4小結152

第9章回溯法153
9.1算法設計思想153
9.2典型例題153
9.2.1八皇后問題153
9.2.2圖著色問題155
9.2.3橋本分數式158
9.2.4高逐位整除數160
9.2.5直尺刻度分佈問題162
9.2.6素數環問題164
9.2.7伯努利裝錯信封問題167
9.3實戰訓練169
9.3.1排列問題169
9.3.2低逐位整除數169
9.3.3子集問題170
9.3.4旅行售貨員問題170
9.3.5兩組均分問題171
9.3.6組合數問題171
9.3.7運動員最佳配對問題172
9.3.8任務最佳調度問題172
9.3.9迷宮問題173
9.3.10背包問題174
9.3.11翻幣問題174
9.3.12最長滑雪問題175
9.3.13流水線作業調度問題175
9.3.14組合三角形問題176
9.3.15情侶排列問題176
9.4小結177

第10章構造法178
10.1算法設計思想178
10.2典型例題179
10.2.1計算π值179
10.2.2求n的階乘180
10.2.3求第k大的數181
10.2.4比賽日程表183
10.2.5奇數階魔方185
10.2.6二叉樹操作187
10.3實戰訓練189
10.3.1自然數倒數求和189
10.3.2今夕是何日189
10.3.3計算e值190
10.3.4自數190
10.3.5火星人191
10.3.6整數平方後9位192
10.3.7構造等式192
10.3.8構造回文字符串192
10.3.9開燈問題193
10.3.10 “1”的個數193
10.3.11小明的煩惱194
10.3.12乒乓球賽194
10.3.13自然數拆分問題195
10.3. 14集卡片贏大獎195
10.3.15括號匹配問題196
10.4小結196

第11章動態規劃法198
11.1算法設計思想198
11.2典型例題199
11.2.1數塔問題199
11.2.2矩陣連乘問題201
11.2.3最長公共子序列問題205
11.2.4最長上升子序列問題207
11.2.5陪審團問題209
11.3實戰訓練212
11.3.1最少硬幣問題212
11.3.2編輯距離問題213
11.3.3石子合併問題213
11.3.4最小m段和問題214
11.3.5最大長方體問題214
11.3.6最大k乘積問題215
11.3.7最少費用購物問題215
11.3.8最優時間表問題216
11.3.9矩形嵌套問題217
11.3 .10導彈攔截問題218
11.3.11 C小加問題218
11.3.12完全背包問題219
11.3.13分郵票問題220
11.3.14排列問題220
11.3.15完全覆蓋問題221
11.4小結221

參考文獻223