第1 章 程序設計競賽與在線程序實踐 ······ 1
1.1 程序設計競賽 ······ 1
1.1.1 大學生程序設計競賽 ······ 1
1.1.2 藍橋杯全國軟件和信息技術專業人纔大賽 ····· 4
1.1.3 中國高校計算機大賽團體程序設計天梯賽······ 7
1.2 在線程序實踐 ······ 7
1.3 程序設計競賽題目的特點 ······ 9
1.3.1 程序設計題目的組成 ······ 9
1.3.2 從單個測試數據的處理過渡到多個測試數據的處理 ······ 9
1.3.3 程序設計競賽題目的輸入/輸出 ······ 11
1.3.4 程序設計競賽題目的類型 ······ 12
1.4 程序設計競賽題目解析······ 13
練習題 ······ 19
1.5 實踐進階：基本的輸入/輸出的處理 ······ 20
1.5.1 輸入的處理······ 21
1.5.2 輸出的處理····· 22
第2 章 枚舉 ······ 24
2.1 枚舉算法及例題解析······ 24
2.1.1 枚舉算法及實現要點 ····· 24
2.1.2 例題解析 ······ 25
練習題 ······ 31
2.2 哥德巴赫猜想 ····· 34
練習題 ····· 37
2.3 尺取法及應用 ······ 38
2.3.1 尺取法的原理及注意事項 ····· 38
2.3.2 例題解析 ······ 39
練習題 ····· 43
2.4 實踐進階：算法及算法復雜度 ······ 44
2.4.1 算法的概念······ 44
2.4.2 算法的效率及算法復雜度 ······45
2.4.3 算法時間復雜度的漸進分析和表示 ······ 47
2.4.4 好、壞和平均情況 ······ 48
2.4.5 基本的算法復雜度模型 ····· 49
第3 章 模擬 ······ 51
3.1 模擬方法及例題解析······ 51
3.1.1 模擬方法及實現要點 ······ 51
3.1.2 例題解析 ······ 52
練習題 ······ 56
3.2 模擬約瑟夫環 ······ 58
練習題 ····· 62
3.3 遊戲的模擬 ······ 63
練習題 ······ 70
3.4 實踐進階：程序測試 ····· 73
3.4.1 解答程序設計競賽題目的一般流程 ·····73
3.4.2 程序測試方法 ······ 74
第4 章 字符及字符串處理 ······ 81
4.1 字符轉換與編碼 ······ 81
4.1.1 字符轉換 ····· 81
4.1.2 字符編碼 ······ 84
練習題 ····· 87
4.2 回文的判斷與處理 ······ 90
練習題 ····· 94
4.3 子串處理 ······ 95
練習題 ······ 98
4.4 模式匹配問題及KMP 算法 ······ 99
4.4.1 字符串的模式匹配問題 ······ 99
4.4.2 樸素的模式匹配算法 ······ 99
4.4.3 KMP 算法 ······ 101
4.4.4 例題解析 ······ 109
練習題 ····· 114
4.5 其他競賽題目解析 ······ 114
練習題 ····· 118
4.6 實踐進階：特殊的輸入/輸出的處理 ······ 119
4.6.1 特殊輸入的處理 ····· 120
4.6.2 特殊輸出的處理 ····· 122
第5 章 時間和日期的處理 ····· 123
5.1 相關問題 ····· 123
5.2 例題解析 ····· 127
5.2.1 星期數計算····· 127
5.2.2 天數計算 ····· 131
5.2.3 日期合法性判斷 ····· 133
5.2.4 日歷轉換 ····· 138
5.2.5 時間表示及轉換 ····· 140
練習題 ······ 143
5.3 實踐進階：程序調試······ 145
5.3.1 調試目的 ····· 145
5.3.2 調試步驟和方法 ····· 145
5.3.3 調試技巧 ····· 146
第6 章 高精度計算 ····· 147
6.1 基礎知識 ····· 147
6.1.1 高精度數 ····· 147
6.1.2 進制轉換 ····· 147
6.1.3 用字符型數組或整型數組實現算術運算 ····· 150
練習題 ······ 152
6.2 高精度計算原理及實現要點 ······ 154
6.2.1 高精度計算原理 ····· 154
6.2.2 高精度計算的基本思路 ····· 155
6.2.3 高精度計算要點 ····· 156
練習題 ······ 156
6.3 高精度數的基本運算······ 157
6.3.1 高精度數的加法 ····· 157
6.3.2 高精度數的乘法 ····· 159
6.3.3 高精度數的除法 ····· 161
練習題 ······ 164
6.4 其他高精度題目解析······ 166
6.4.1 數列問題 ····· 166
6.4.2 其他題目 ····· 167
練習題 ······ 169
6.5 實踐進階：代碼優化 ······ 169
第7 章 遞歸、分治、動態規劃和貪心 ······ 171
7.1 將較大規模問題降為較小規模問題 ···· 171
7.2 遞歸算法及例題解析 ······ 175
7.2.1 遞歸算法思想及存在的問題 ···· 175
7.2.2 例題解析 ····· 176
練習題 ······ 182
7.3 分治算法及例題解析 ······ 184
7.3.1 分治算法的思想 ····· 184
7.3.2 例題解析 ····· 188
練習題 ······ 191
7.4 動態規劃算法及例題解析 ····· 193
7.4.1 動態規劃算法的思想 ····· 193
7.4.2 例題解析 ····· 199
練習題 ······ 203
7.5 貪心算法及例題解析 ······ 205
7.5.1 貪心算法的思想 ····· 205
7.5.2 例題解析 ····· 211
練習題 ······ 213
7.6 實踐進階：函數及遞歸函數設計 ····· 214
第8 章 搜索 ····· 217
8.1 深度優先搜索 ······ 217
8.1.1 深度優先搜索的思想 ····· 217
8.1.2 例題解析 ····· 218
練習題 ······ 227
8.2 用深度優先搜索求解排列和組合
問題 ····· 230
8.2.1 排列問題 ····· 230
8.2.2 組合問題 ····· 235
練習題 ······ 242
8.3 廣度優先搜索 ······ 244
8.3.1 廣度優先搜索的思想 ····· 244
8.3.2 例題解析 ····· 245
練習題 ······ 252
8.4 實踐進階：搜索技巧 ······ 256
8.4.1 深度優先搜索技巧 ····· 256
8.4.2 廣度優先搜索技巧 ····· 257
第9 章 排序和檢索 ····· 260
9.1 排序及排序函數的使用 ····· 260
9.1.1 排序及排序算法 ····· 260
9.1.2 排序的應用····· 261
9.1.3 排序函數qsort( )的用法 ····· 262
9.1.4 排序函數sort( )的用法 ····· 264
9.1.5 例題解析 ····· 265
練習題 ······ 268
9.2 排序題目解析 ····· 270
9.2.1 數值型數據的排序 ····· 270
9.2.2 字符型數據的排序 ····· 273
9.2.3 混合數據的排序 ····· 275
練習題 ······ 277
9.3 二分法思想及二分檢索 ····· 280
9.3.1 二分法的思想 ······ 280
9.3.2 二分檢索法及應用 ····· 280
9.3.3 例題解析 ····· 282
練習題 ······ 286
9.4 實踐進階：標準模板庫及常用數據結構的使用 ······ 287
9.4.1 數據結構的基本概念 ······ 287
9.4.2 標準模板庫····· 288
9.4.3 向量 ······ 288
9.4.4 棧 ····· 288
9.4.5 隊列 ······ 293
9.4.6 優先級隊列····· 296
9.4.7 常用算法 ····· 298
練習題 ······ 298
第10 章 數論基礎 ······ 300
10.1 符號說明 ······ 300
10.2 整除理論 ······ 301
10.2.1 自然數與整數 ····· 301
10.2.2 整除 ······ 301
10.2.3 帶餘數除法與輾轉相除法 ···· 304
10.2.4 公約數理論 ····· 306
10.2.5 算術基本定理 ····· 307
10.2.6 符號[x]與n!的分解式 ····· 308
10.2.7 π(x)與歐拉函數 ······ 309
練習題 ····· 310
10.3 同餘理論 ······ 312
10.3.1 同餘 ······ 312
10.3.2 同餘類與剩餘類 ····· 314
10.3.3 同餘方程 ····· 315
練習題 ····· 317
10.4 素數相關問題 ····· 319
10.4.1 相關問題 ····· 319
10.4.2 例題解析 ····· 320
10.5 實踐進階：程序設計競賽技巧 ····· 321
附錄A 程序設計競賽的100 個技巧 ····· 322
附錄B 本書例題和練習題彙總 ······ 353
參考文獻 ······ 360