基本信息
叢書名： 圖靈程式設計叢書
上架時間：2013-6-14
版次：2-1
所屬分類：計算機 > 軟體與程式設計 > 綜合 > 綜合
作者簡介
秋葉拓哉，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實驗室從事科研工作
內容簡介
《挑戰程式設計競賽(第2版)》對程式設計競賽中的基礎算法和經典問題進行了匯總，分為準備篇、初級篇、中級篇與高級篇4章。作者結合自己豐富的參賽經驗，對嚴格篩選的110 多道各類試題進行了由淺入深、由易及難的細緻講解，並介紹了許多實用技巧。每章後附有習題，供讀者練習，鞏固所學。
《挑戰程式設計競賽(第2版)》適合程式設計人員、程式設計競賽愛好者以及高校計算機專業師生閱讀。
編輯推薦
世界頂級程式設計高手的經驗總結
【ACM-ICPC全球總冠軍】巫澤俊主譯
日本ACM-ICPC參賽者人手一冊
圖書前言
如今，形形色色的程式設計競賽層出不窮，聽說過Google Code Jam、TopCoder、ACM-ICPC的讀者恐怕不在少數。本書要介紹的正是這類以在規定時間內、又快又準地解決儘可能多的題目為目標的程式設計競賽。
程式設計競賽內涵豐富，即便是經驗老道的程式設計師，要想在比賽中取得好成績也絕非易事。要在程式設計競賽中取勝，不僅需要運用靈活的想像和豐富的知識得出正確的算法，還需要一氣呵成地實現並調試通過。
另一方面，程式設計競賽對新手而言亦非遙不可及。為了讓更多的參賽選手體會到比賽的樂趣，大多數比賽都會準備若干面向初學者的題目。另外，即便未能在比賽中取得好成績，通過比賽，也能夠使自己的能力得到有效的鍛鍊。最重要的是，大家能夠享受到激烈的比賽帶來的樂趣。
本書的作者們參加過眾多程式設計競賽，在平時的練習和學習中，也獲得了各種各樣的知識與技巧，本書將這些知識技巧總結成冊，主要介紹算法及其在相關問題中的套用。本書依照由易及難的順序對問題進行講解，章節的編排也參考了主題的難易程度及其相互的聯繫，內容較多的主題則按難易程度劃分為多個子主題分別介紹。各個主題由算法介紹和例題講解穿插而成。
只要是具有編程基礎知識的讀者，均適合閱讀本書。書中的原始碼均用C++實現，不過只用到了其基本功能，所以即便讀者不熟悉C++也不影響閱讀。
關於再版
令人驚喜的是，本書的第1版受到了廣大讀者的高度評價，在此表示感謝。特別是一些並不熱衷於程式設計競賽的讀者也購買了本書。這是因為通過本書不僅可以學到算法，更能學到其設計和運用的思想。這正是本書劃時代的亮點。
本書第2版追加了計算幾何、搜尋減枝、分治法和字元串相關算法4個主題。此外還追加了方便讀者加深理解的練習題，並為學有餘力的讀者列出了書中未涉及的拓展主題，進一步豐富了本書內容。
目錄
《挑戰程式設計競賽(第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.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
