第1章　引言　　1
1.1　編程競賽　　1
1.1.1　綫上學習網站　　3
1.1.2　綫上裁判的返迴值　　4
1.2　我們的選擇：Python　　5
1.3　輸入輸齣　　6
1.3.1　讀取標準輸入　　6
1.3.2　顯示格式　　9
1.4　復雜度　　9
1.5　抽象類型和基本數據結構　　11
1.5.1　棧　　11
1.5.2　字典　　12
1.5.3　隊列　　12
1.5.4　優先級隊列和最小堆　　13
1.5.5　並查集　　16
1.6　技術　　18
1.6.1　比較　　18
1.6.2　排序　　18
1.6.3　掃描　　19
1.6.4　貪婪算法　　20
1.6.5　動態規劃算法　　20
1.6.6　用整數編碼集閤　　21
1.6.7　二分查找　　23
1.7　建議　　25
1.8　走得更遠　　27
第2章　字符串　　28
2.1　易位構詞　　28
2.2　T9：9 個按鍵上的文字　　29
2.3　使用字典樹進行拼寫糾正　　31
2.4　KMP（Knuth-Morris-Pratt）模式匹配算法　　33
2.5　最大邊的KMP 算法　　35
2.6　字符串的冪　　38
2.7　模式匹配算法：Rabin–Karp 算法　　38
2.8　字符串的最長迴文子串：Manacher 算法　　42
第3章　序列　　44
3.1　網格中的最短路徑　　44
3.2　編輯距離（列文斯登距離）　　45
3.3　最長公共子序列　　47
3.4　升序最長子序列　　49
3.5　兩位玩傢遊戲中的必勝策略　　52
第4章　數組　　53
4.1　閤並已排序列錶　　53
4.2　區間的總和　　54
4.3　區間內的重復內容　　54
4.4　區間的最大總和　　55
4.5　查詢區間中的最小值：綫段樹　　55
4.6　計算區間的總和：樹狀數組（Fenwick 樹）　　57
4.7　有k 個獨立元素的窗口　　59
第5章　區間　　61
5.1　區間樹（綫段樹）　　61
5.2　區間的並集　　64
5.3　區間的覆蓋　　64
第6章　圖　　66
6.1　使用Python 對圖編碼　　66
6.2　使用C++ 或Java 對圖編碼　　67
6.3　隱式圖　　68
6.4　深度優先遍曆：深度優先算法　　69
6.5　廣度優先遍曆：廣度優先算法　　70
6.6　連通分量　　71
6.7　雙連通分量　　74
6.8　拓撲排序　　77
6.9　強連通分量　　79
6.10　可滿足性　　84
第7章　圖中的環　　86
7.1　歐拉路徑　　86
7.2　中國郵差問題　　88
7.3　最小長度上的比率權重環：Karp 算法　　89
7.4　單位時間成本最小比率環　　92
7.5　旅行推銷員問題　　93
第8章　最短路徑　　94
8.1　組閤的屬性　　94
8.2　權重為0 或1 的圖　　96
8.3　權重為正值或空值的圖： Dijkstra 算法　　97
8.4　隨機權重的圖：Bellman-Ford 算法　　100
8.5　所有源點- 目標頂點對：Floyd-Warshall 算法　　101
8.6　網格　　102
8.7　變種問題　　104
8.7.1　無權重圖　　104
8.7.2　有嚮無環圖　　104
8.7.3　最長路徑　　104
8.7.4　樹中的最長路徑　　104
8.7.5　最小化弧上權重的路徑　　105
8.7.6　頂點有權重的圖　　105
8.7.7　令頂點上最大權重最小的路徑　　105
8.7.8　所有邊都屬於一條最短路徑　　105
第9章　耦閤性和流　　106
9.1　二分圖最大匹配　　107
9.2　最大權重的完美匹配： Kuhn-Munkres 算法　　110
9.3　無交叉平麵匹配　　116
9.4　穩定的婚姻：Gale-Shapley 算法　　117
9.5　Ford-Fulkerson 最大流算法　　119
9.6　Edmonds-Karp 算法的最大流　　121
9.7　Dinic 最大流算法　　122
9.8　s-t 最小割　　125
9.9　平麵圖的s-t 最小割　　126
9.10　運輸問題　　127
9.11　在流和匹配之間化簡　　127
9.12　偏序的寬度：Dilworth 算法　　129
第10章　樹　　132
10.1　哈夫曼編碼　　133
10.2　最近的共同祖先　　135
10.3　樹中的最長路徑　　138
10.4　最小權重生成樹：Kruskal 算法　　140
第11章　集閤　　142
11.1　背包問題　　142
11.2　找零問題　　143
11.3　給定總和值的子集　　145
11.4　k 個整數之和　　146
第12章　點和多邊形　　148
12.1　凸包問題　　149
12.2　多邊形的測量　　150
12.3　最近點對　　151
12.4　簡單直綫多邊形　　153
第13章　長方形　　156
13.1　組成長方形　　156
13.2　網格中的最大正方形　　157
13.3　直方圖中的最大長方形　　158
13.4　網格中的最大長方形　　159
13.5　閤並長方形　　160
13.6　不相交長方形的閤並　　164
第14章　計算　　165
14.1　最大公約數　　165
14.2　貝祖等式　　165
14.3　二項式係數　　166
14.4　快速求冪　　167
14.5　素數　　167
14.6　計算算數錶達式　　168
14.7　綫性方程組　　170
14.8　矩陣序列相乘　　174
第15章　窮舉　　176
15.1　激光路徑　　176
15.2　精確覆蓋　　179
15.3　數獨　　184
15.4　排列枚舉　　186
15.5　正確計算　　188
調試工具　　191
參考文獻　　192
· · · · · · (收起)