《挑戰程序設計競賽(第2版)》
第1章 蓄勢待發——準備篇 1 1.1何謂程序設計競賽 2 1.2最負盛名的程序設計競賽 5 1.2.1世界規模的大賽——google code jam（gcj） 5 1.2.2向高排名看齊！——topcoder 5 1.2.3歷史最悠久的競賽—— acm-icpc 6 1.2.4面向中學生的信息學奧林匹克競賽——joi-ioi 6 1.2.5通過網絡自動評測——online judge（oj） 6 1.3本書的使用方法 7 1.3.1本書所涉及的內容 7 1.3.2所用的編程語言 7 1.3.3題目描述的處理 7 1.3.4程序結構 7 1.3.5練習題 8 1.3.6讀透本書後更上壹層樓的練習方法 8 1.4如何提交解答 9 1.4.1poj的提交方法 9 1.4.2gcj的提交方法 11 1.5以高效的算法為目標 15
.1.5.1什麽是復雜度 15 1.5.2關於運行時間 15 1.6輕松熱身 16 1.6.1先從簡單題開始 16 1.6.2poj的題目ants 18 1.6.3難度增加的抽簽問題 20 第2章 初出茅廬——初級篇 25 2.1最基礎的“窮竭搜索” 26 2.1.1遞歸函數 26 2.1.2棧 27 2.1.3隊列 28 2.1.4深度優先搜索 29 2.1.5寬度優先搜索 33 2.1.6特殊狀態的枚舉 37 2.1.7剪枝 38 2.2壹往直前！貪心法 39 2.2.1硬幣問題 39 2.2.2區間問題 40 2.2.3字典序最小問題 43 2.2.4其他例題 45 2.3記錄結果再利用的“動態規劃” 51 2.3.1記憶化搜索與動態規劃 51 2.3.2進壹步探討遞推關系 57 2.3.3有關計數問題的dp 66 2.4加工並存儲數據的數據結構 70 2.4.1樹和二叉樹 70 2.4.2優先隊列和堆 71 2.4.3二叉搜索樹 77 2.4.4並查集 84 2.5它們其實都是“圖” 91 2.5.1圖是什麽 91 2.5.2圖的表示 94 2.5.3圖的搜索 97 2.5.4最短路問題 99 2.5.5最小生成樹 105 2.5.6應用問題 107 2.6數學問題的解題竅門 113 2.6.1輾轉相除法 113 2.6.2有關素數的基礎算法 117 2.6.3模運算 121 2.6.4快速冪運算 122 2.7壹起來挑戰gcj的題目（1） 125 2.7.1minimum scalar product 125 2.7.2crazy rows 127 2.7.3bribe the prisoners 129 2.7.4millionaire 132 第3章 出類拔萃——中級篇 137 3.1不光是查找值！“二分搜索” 138 3.1.1從有序數組中查找某個值 138 3.1.2假定壹個解並判斷是否可行 140 3.1.3最大化最小值 142 3.1.4最大化平均值 143 3.2常用技巧精選（壹） 146 3.2.1尺取法 146 3.2.2反轉（開關問題） 150 3.2.3彈性碰撞 158 3.2.4折半枚舉（雙向搜索） 160 3.2.5坐標離散化 164 3.3活用各種數據結構 167 3.3.1線段樹 167 3.3.2binary indexed tree 174 3.3.3分桶法和平方分割 183 3.4熟練掌握動態規劃 191 3.4.1狀態壓縮dp 191 3.4.2矩陣的冪 199 3.4.3利用數據結構高效求解 206 3.5借助水流解決問題的網絡流 209 3.5.1最大流 209 3.5.2最小割 212 3.5.3二分圖匹配 217 3.5.4壹般圖匹配 220 3.5.5匹配、邊覆蓋、獨立集和頂點覆蓋 221 3.5.6最小費用流 222 3.5.7應用問題 228 3.6與平面和空間打交道的計算幾何 250 3.6.1計算幾何基礎 250 3.6.2極限情況 255 3.6.3平面掃描 258 3.6.4凸包 260 3.6.5數值積分 263 3.7壹起來挑戰gcj的題目（2） 267 3.7.1numbers 267 3.7.2no cheating 269 3.7.3stock charts 271 3.7.4watering plants 273 3.7.5number sets 278 3.7.6wi-fi towers 280 第4章 登峰造極——高級篇 285 4.1更加復雜的數學問題 286 4.1.1矩陣 286 4.1.2模運算的世界 291 4.1.3計數 295 4.1.4具有對稱性的計數 300 4.2找出遊戲的必勝策略 305 4.2.1遊戲與必勝策略 305 4.2.2nim 311 4.2.3grundy數 315 4.3成為圖論大師之路 320 4.3.1強連通分量分解 320 4.3.22-sat 324 4.3.3lca 328 4.4常用技巧精選（二） 335 4.4.1棧的運用 335 4.4.2雙端隊列的運用 337 4.4.3倍增法 345 4.5開動腦筋智慧搜索 350 4.5.1剪枝 350 4.5.2a*與ida* 356 4.6劃分、解決、合並：分治法 359 4.6.1數列上的分治法 359 4.6.2樹上的分治法 360 4.6.3平面上的分治法 364 4.7華麗地處理字符串 368 4.7.1字符串上的動態規劃算法 368 4.7.2字符串匹配 373 4.7.3後綴數組 378 4.8壹起來挑戰gcj的題目（3） 387 4.8.1mine layer 387 4.8.2year of more code jam 392 4.8.3football team 395 4.8.4endless knight 399 4.8.5the year of code jam 403 本書中未涉及的拓展主題 408 書中例題列表 411 參考文獻 413