第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.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
· · · · · · (收起)