高效算法 競賽 應試與提高必修128例 高效算法 竞赛 应试与提高必修128例

本書旨在探討如何優化算法效率，詳細闡述了經典算法和特殊算法的實現、應用技巧和復雜度驗證過程，內容由淺入深，能幫助讀者快速掌握復雜度適當、正確率高的高效編程方法以及自檢、自測技巧，是參加ACM/ICPC、Google Code Jam等國際編程競賽、備戰編程考試、提高編程效率、優化編程方法的參考書目。

作者:[法]克里斯托弗·杜爾(Christoph Dürr)吉爾-讓·維（Jill-Jênn Vie）譯者:史世強

Christoph Dürr，法國國家科學研究院研究員，巴黎皮埃爾-瑪麗·居里大學博士生導師，Operation Research科研組研究主任。

Jill-Jênn Vie，法國高等電力學院博士、算法講師，擔任法國高等師範學院Paris-Saclay團隊在ACM競賽中的算法導師；曾任法國國際編程大賽Prologin主席，並於2014年獲Google RISE Award。

第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 st最小割125 
9 9平面圖的st最小割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