第1章 程序設(shè)計(jì)競(jìng)賽與在線(xiàn)程序?qū)嵺` ???????????????? 1 1.1 程序設(shè)計(jì)競(jìng)賽 ?????????????????????????????????????????? 1 1.1.1 大學(xué)生程序設(shè)計(jì)競(jìng)賽 ??????????????????? 1 1.1.2 藍(lán)橋杯全國(guó)軟件和信息技術(shù)專(zhuān)業(yè)人才大賽 ??????????????????????????????? 4 1.1.3 中國(guó)高校計(jì)算機(jī)大賽團(tuán)體程序設(shè)計(jì)天梯賽??????????????????????????????????? 7 1.2 在線(xiàn)程序?qū)嵺` ?????????????????????????????????????????? 7 1.3 程序設(shè)計(jì)競(jìng)賽題目的特點(diǎn) ??????????????????????? 9 1.3.1 程序設(shè)計(jì)題目的組成 ??????????????????? 9 1.3.2 從單個(gè)測(cè)試數(shù)據(jù)的處理過(guò)渡到多個(gè)測(cè)試數(shù)據(jù)的處理 ??????????????????? 9 1.3.3 程序設(shè)計(jì)競(jìng)賽題目的輸入/輸出 ??? 11 1.3.4 程序設(shè)計(jì)競(jìng)賽題目的類(lèi)型 ????????? 12 1.4 程序設(shè)計(jì)競(jìng)賽題目解析 ????????????????????????? 13 練習(xí)題 ???????????????????????????????????????????????????? 19 1.5 實(shí)踐進(jìn)階：基本的輸入/輸出的處理 ???? 20 1.5.1 輸入的處理????????????????????????????????? 21 1.5.2 輸出的處理????????????????????????????????? 22 第2章 枚舉 ???????????????????????????????????????????????????????? 24 2.1 枚舉算法及例題解析????????????????????????????? 24 2.1.1 枚舉算法及實(shí)現(xiàn)要點(diǎn) ????????????????? 24 2.1.2 例題解析 ???????????????????????????????????? 25 練習(xí)題 ???????????????????????????????????????????????????? 31 2.2 哥德巴赫猜想 ???????????????????????????????????????? 34 練習(xí)題 ???????????????????????????????????????????????????? 37 2.3 尺取法及應(yīng)用 ???????????????????????????????????????? 38 2.3.1 尺取法的原理及注意事項(xiàng) ????????? 38 2.3.2 例題解析 ???????????????????????????????????? 39 練習(xí)題 ???????????????????????????????????????????????????? 43 2.4 實(shí)踐進(jìn)階：算法及算法復(fù)雜度 ????????????? 44 2.4.1 算法的概念????????????????????????????????? 44 2.4.2 算法的效率及算法復(fù)雜度 ????????? 45 2.4.3 算法時(shí)間復(fù)雜度的漸進(jìn)分析和表示 ????????????????????????????????????????????? 47 2.4.4 最好、最壞和平均情況 ?????????????? 48 2.4.5 基本的算法復(fù)雜度模型 ?????????????? 49 第3章 模擬 ???????????????????????????????????????????????????????? 51 3.1 模擬方法及例題解析 ????????????????????????????? 51 3.1.1 模擬方法及實(shí)現(xiàn)要點(diǎn) ?????????????????? 51 3.1.2 例題解析 ????????????????????????????????????? 52 練習(xí)題 ???????????????????????????????????????????????????? 56 3.2 模擬約瑟夫環(huán) ????????????????????????????????????????? 58 練習(xí)題 ???????????????????????????????????????????????????? 62 3.3 游戲的模擬 ????????????????????????????????????????????? 63 練習(xí)題 ???????????????????????????????????????????????????? 70 3.4 實(shí)踐進(jìn)階：程序測(cè)試 ????????????????????????????? 73 3.4.1 解答程序設(shè)計(jì)競(jìng)賽題目的一般流程 ????????????????????????????????????????????? 73 3.4.2 程序測(cè)試方法 ????????????????????????????? 74 第4章 字符及字符串處理 ????????????????????????????????? 81 4.1 字符轉(zhuǎn)換與編碼 ??????????????????????????????????????? 81 4.1.1 字符轉(zhuǎn)換 ????????????????????????????????????? 81 4.1.2 字符編碼 ????????????????????????????????????? 84 練習(xí)題 ???????????????????????????????????????????????????? 87 4.2 回文的判斷與處理 ????????????????????????????????? 90 練習(xí)題 ???????????????????????????????????????????????????? 94 4.3 子串處理 ???????????????????????????????????????????????? 95 練習(xí)題 ???????????????????????????????????????????????????? 98 4.4 模式匹配問(wèn)題及KMP算法 ??????????????????? 99 4.4.1 字符串的模式匹配問(wèn)題 ?????????????? 99 4.4.2 樸素的模式匹配算法 ?????????????????? 99 4.4.3 KMP算法 ????????????????????????????????? 101 4.4.4 例題解析 ??????????????????????????????????? 109 練習(xí)題 ?????????????????????????????????????????????????? 114 4.5 其他競(jìng)賽題目解析 ??????????????????????????????? 114 練習(xí)題 ??????????????????????????????????????????????????? 118 4.6 實(shí)踐進(jìn)階：特殊的輸入/輸出的處理 ?????? 119 4.6.1 特殊輸入的處理 ??????????????????????? 120 4.6.2 特殊輸出的處理 ??????????????????????? 122 第5章 時(shí)間和日期的處理 ??????????????????????????????? 123 第6章 高精度計(jì)算 ??????????????????????????????????????????? 147 第7章 遞歸、分治、動(dòng)態(tài)規(guī)劃和貪心 ???????????? 171 第8章 搜索 ?????????????????????????????????????????????????????? 217 第9章 排序和檢索 ??????????????????????????????????????????? 260 第10章 數(shù)論基礎(chǔ) ???????????????????????????????????????????? 300 附錄A 程序設(shè)計(jì)競(jìng)賽的100個(gè)技巧 ???????????????? 322 附錄B 本書(shū)例題和練習(xí)題匯總 ???????????????????????? 353 參考文獻(xiàn) ?????????????????????????????????????????????????????????????? 360