挑戰程序設計競賽(第2版)

秋葉拓哉，Google Code Jam 2010第9名；ACM-ICPC World Finals 2012第11名；TopCoder Open 2012 Algorithm第4名，暱稱iwi 
岩田陽一，Google Code Jam 2009第3名；TopCoder Open 2010 Marathon冠軍； IPSC 2010個人組冠軍，暱稱wata 
北川宜稔，ACM-ICPC World Finals 2010第16名，暱稱kita_masa 
巫澤俊，ACM-ICPC World Finals 2009第6名；ACM-ICPC World Finals 2011冠軍；Google Code Jam 2012第7名，暱稱watashi和rejudge 
莊俊元，ACM-ICPC Asia Phuket Regional 2011冠軍；2012年躋身ACM-ICPC World Finals以及百度Astar總決賽，暱稱navi和navimoe 
李津羽，浙江大學2011級計算機系博士生，在浙大CAD&CG實驗室從事科研工作 

第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.1 POJ的提交方法9 
1.4.2 GCJ的提交方法11 
1.5以高效的算法為目標15 
1.5.1什麼是複雜度15 
1.5.2關於運行時間15 
1.6輕鬆熱身16 
1.6.1先從簡單題開始16 
1.6.2 POJ的題目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.1 Minimum Scalar Product 125 
2.7.2 Crazy Rows 127 
2.7.3 Bribe the Prisoners 129 
2.7. 4 Millionaire 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.2 Binary 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.1 Numbers 267 
3.7.2 No Cheating 269 
3.7.3 Stock Charts 271 
3.7.4 Watering Plants 273 
3.7.5 Number Sets 278 
3.7.6 Wi-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.2 Nim 311 
4.2.3 Grundy數315 
4.3成為圖論大師之路320 
4.3.1強連通分量分解320 
4.3.2 2-SAT 324 
4.3.3 LCA 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.2 A*與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.1 Mine Layer 387 
4.8.2 Year of More Code Jam 392 
4.8.3 Football Team 395 
4.8.4 Endless Knight 399 
4.8.5 The Year of Code Jam 403 
本書中未涉及的拓展主題408 
書中例題列表411 
參考文獻413