第1章 程序設計競賽與在線程序實踐 ???????????????? 1 1.1 程序設計競賽 ?????????????????????????????????????????? 1 1.1.1 大學生程序設計競賽 ??????????????????? 1 1.1.2 藍橋杯全國軟件和信息技術專業(yè)人才大賽 ??????????????????????????????? 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 模擬約瑟夫環(huán) ????????????????????????????????????????? 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 第6章 高精度計算 ??????????????????????????????????????????? 147 第7章 遞歸、分治、動態(tài)規(guī)劃和貪心 ???????????? 171 第8章 搜索 ?????????????????????????????????????????????????????? 217 第9章 排序和檢索 ??????????????????????????????????????????? 260 第10章 數論基礎 ???????????????????????????????????????????? 300 附錄A 程序設計競賽的100個技巧 ???????????????? 322 附錄B 本書例題和練習題匯總 ???????????????????????? 353 參考文獻 ?????????????????????????????????????????????????????????????? 360