算法競賽

本書是一本全面、深入解析與算法競賽有關的數據結構、算法、代碼的電腦教材。 本書包括十個專題： 基礎數據結構、基本算法、搜索、高級數據結構、動態規劃、數論和線性代數、組合數學、計算幾何、字符串和圖論。本書覆蓋了絕大多數算法競賽考點。 本書解析了算法競賽考核的數據結構、算法； 組織了每個知識點的理論解析和經典例題； 給出了簡潔、精要的模板代碼； 通過明快清晰的文字、透徹的圖解，實現了較好的易讀性。 本書的讀者對象是參加算法競賽的中學生和大學生、準備面試IT企業算法題的求職者、需要提高算法能力的開發人員，以及對電腦算法有興趣的廣大科技工作者。

 

目錄

 

 

源碼下載

 

 

第1章基礎數據結構

 

1.1鏈表

 

1.1.1動態鏈表

 

1.1.2靜態鏈表

 

1.1.3STL list

 

1.2隊列

 

1.2.1STL queue

 

1.2.2手寫循環隊列

 

1.2.3雙端隊列和單調隊列

 

1.2.4優先隊列

 

1.3棧

 

1.3.1STL stack

 

1.3.2手寫棧

 

1.3.3單調棧

 

1.4二叉樹和哈夫曼樹

 

1.4.1二叉樹的概念

 

1.4.2二叉樹的遍歷

 

1.4.3哈夫曼樹和哈夫曼編碼

 

1.5堆

 

1.5.1二叉堆的概念

 

1.5.2二叉堆的操作

 

1.5.3二叉堆的手寫代碼

 

1.5.4堆和priority_queue

 

小結

 

 

第2章基本算法

 

2.1算法復雜度

 

2.1.1算法的概念

 

2.1.2復雜度和大O記號

 

2.2尺取法

 

2.2.1尺取法的概念

 

2.2.2反向掃描

 

2.2.3同向掃描

 

 

 

 

 

2.3二分法

 

2.3.1二分法的理論背景

 

2.3.2整數二分

 

2.3.3實數二分

 

2.4三分法

 

2.4.1原理

 

2.4.2實數三分

 

2.4.3整數三分

 

2.5倍增法與ST算法

 

2.5.1倍增法

 

2.5.2ST算法

 

2.6前綴和與差分

 

2.6.1一維差分

 

2.6.2二維差分

 

2.6.3三維差分

 

2.7離散化

 

2.7.1離散化的概念

 

2.7.2離散化手工編碼

 

2.7.3用STL函數實現離散化

 

2.7.4離散化的應用

 

2.8排序與排列

 

2.8.1排序函數

 

2.8.2排列

 

2.9分治法

 

2.9.1漢諾塔和快速冪

 

2.9.2歸並排序

 

2.9.3快速排序

 

2.10貪心法與擬陣

 

2.10.1貪心法

 

2.10.2擬陣

 

小結

 

第3章搜索

 

3.1BFS和DFS基礎

 

3.1.1搜索簡介

 

 

3.1.2搜索算法的基本思路

 

3.1.3BFS的代碼實現

 

3.1.4DFS的常見操作和代碼框架

 

3.1.5BFS和DFS的對比

 

3.1.6連通性判斷

 

3.2剪枝

 

3.2.1BFS判重

 

3.2.2剪枝的應用

 

3.3洪水填充

 

3.4BFS與最短路徑

 

3.5雙向廣搜

 

3.5.1雙向廣搜的原理和復雜度分析

 

3.5.2雙向廣搜的兩種實現

 

3.5.3雙向廣搜例題

 

 

3.6BFS與優先隊列

 

3.7BFS與雙端隊列

 

3.8A*算法

 

3.8.1貪心最優搜索和Dijkstra算法

 

3.8.2A*算法的原理和復雜度

 

3.8.33種算法的對比

 

3.8.4h函數的設計

 

3.8.5A*算法例題

 

3.9IDDFS和IDA*

 

3.9.1IDDFS

 

3.9.2IDA*

 

小結

 

第4章高級數據結構

 

4.1並查集

 

 

4.1.1並查集的基本操作

 

4.1.2合並的優化

 

4.1.3查詢的優化(路徑壓縮)

 

4.1.4帶權並查集

 

4.2樹狀數組

 

4.2.1樹狀數組的概念和基本編碼

 

4.2.2樹狀數組的基本應用

 

4.2.3樹狀數組的擴展應用

 

4.3線段樹

 

4.3.1線段樹的概念

 

4.3.2區間查詢

 

4.3.3區間操作與LazyTag

 

4.3.4線段樹的基礎應用

 

4.3.5區間最值和區間歷史最值

 

4.3.6區間合並

 

4.3.7掃描線

 

4.3.8二維線段樹(樹套樹)

 

4.4可持久化線段樹

 

4.4.1可持久化線段樹的思想

 

4.4.2區間第k大/小問題

 

4.4.3其他經典問題

 

4.5分塊與莫隊算法

 

4.5.1分塊

 

4.5.2基礎莫隊算法

 

4.5.3帶修改的莫隊算法

 

4.5.4樹上莫隊

 

4.6塊狀鏈表

 

4.7簡單樹上問題

 

4.7.1樹的重心

 

4.7.2樹的直徑

 

4.8LCA

 

4.8.1倍增法求LCA

 

4.8.2Tarjan算法求LCA

 

4.8.3LCA的應用

 

4.9樹上的分治

 

4.9.1靜態點分治

 

4.9.2動態點分治

 

4.10樹鏈剖分

 

4.10.1樹鏈剖分的概念與LCA

 

4.10.2樹鏈剖分的典型應用

 

4.11二叉查找樹

 

4.12替罪羊樹

 

4.12.1不平衡率

 

4.12.2替罪羊樹的操作

 

4.12.3例題

 

4.13Treap樹

 

4.13.1Treap樹的性質

 

4.13.2基於旋轉法的Treap樹操作

 

4.14FHQ Treap樹

 

4.14.1FHQ的基本操作

 

4.14.2FHQ Treap樹的應用

 

4.15笛卡兒樹

 

4.15.1笛卡兒樹的概念

 

4.15.2用單調棧建笛卡兒樹

 

4.15.3笛卡兒樹和RMQ問題

 

4.16Splay樹

 

4.16.1Splay旋轉

 

4.16.2Splay樹的平攤分析

 

4.16.3Splay樹的常用操作和代碼

 

4.17KD樹

 

4.17.1從空間到二叉樹的轉換

 

4.17.2KD樹的概念和基本操作

 

4.17.3尋找最近點

 

4.17.4區間查詢

 

4.18動態樹與LCT

 

4.18.1LCT的思想

 

4.18.2從原樹到輔助樹

 

4.18.3LCT的存儲和性質

 

4.18.4LCT的操作

 

4.18.5LCT的基本應用

 

小結

 

第5章動態規劃

 

5.1DP概念和編程方法

 

5.1.1DP的概念

 

5.1.2DP的兩種編程方法

 

5.1.3DP的設計和實現

 

5.1.4滾動數組

 

5.2經典線性DP問題

 

5.3數位統計DP

 

5.3.1數位統計DP的遞推實現

 

5.3.2數位統計DP的記憶化搜索實現

 

5.3.3數位統計DP例題

 

5.4狀態壓縮DP

 

5.4.1引子

 

5.4.2狀態壓縮DP的原理

 

5.4.3狀態壓縮DP例題

 

5.4.4三進制狀態壓縮DP

 

 

5.5區間DP

 

5.5.1石子合並問題和兩種模板代碼

 

5.5.2區間DP例題

 

5.5.3二維區間DP

 

5.6樹形DP

 

5.6.1樹形DP的基本操作

 

5.6.2背包與樹形DP

 

5.7一般優化

 

5.8單調隊列優化

 

5.8.1單調隊列優化的原理

 

5.8.2單調隊列優化例題

 

5.9斜率優化/凸殼優化

 

5.9.1把狀態轉移方程變換為平面的斜率問題

 

5.9.2求一個dp［i］

 

5.9.3求所有dp［i］

 

5.9.4例題

 

5.10四邊形不等式優化

 

5.10.1應用場合

 

5.10.2四邊形不等式優化操作

 

5.10.3四邊形不等式定義和單調性定義

 

5.10.4四邊形不等式定理

 

5.10.5例題

 

小結

 

 

 

 

 

源碼下載

 

第6章數論和線性代數

 

6.1模運算

 

6.2快速冪

 

6.3矩陣的應用

 

6.3.1矩陣的計算

 

6.3.2矩陣快速冪

 

6.3.3矩陣快速冪加速遞推

 

6.3.4矩陣乘法與路徑問題

 

6.4高斯消元

 

6.4.1高斯消元的基本操作

 

6.4.2高斯約當消元法

 

6.4.3例題

 

6.5異或空間線性基

 

6.5.1異或空間線性基的概念

 

6.5.2線性基的構造

 

6.5.3線性基的應用

 

6.60/1分數規劃

 

6.6.1二分法與0/1分數規劃

 

6.6.2應用場景

 

6.7GCD和LCM

 

6.7.1GCD

 

6.7.2LCM

 

6.7.3裴蜀定理

 

6.8線性丟番圖方程

 

6.8.1二元線性丟番圖方程

 

6.8.2擴展歐幾里得算法與二元丟番圖方程的解

 

6.8.3多元線性丟番圖方程

 

6.9同餘

 

6.9.1同餘概述

 

6.9.2一元線性同餘方程

 

6.9.3逆

 

6.9.4同餘方程組

 

6.10素數(質數)

 

6.10.1小素數的判定

 

6.10.2大素數的判定

 

6.10.3素數篩

 

6.10.4質因數分解

 

6.11威爾遜定理

 

6.12積性函數

 

6.13歐拉函數

 

6.13.1歐拉函數的定義和性質

 

6.13.2求歐拉函數的通解公式

 

6.13.3用線性篩(歐拉篩)求1～n內的所有歐拉函數

 

6.14整除分塊(數論分塊)

 

6.15狄利克雷捲積

 

6.16莫比烏斯函數和莫比烏斯反演

 

6.17杜教篩

 

6.17.1杜教篩的起源

 

6.17.2杜教篩公式的推導

 

6.17.3杜教篩算法和復雜度

 

6.17.4杜教篩模板代碼

 

小結

 

第7章組合數學

 

7.1基本概念

 

7.2鴿巢原理

 

 

7.3二項式定理和楊輝三角

 

7.4盧卡斯定理

 

7.5容斥原理

 

7.6Catalan數和Stirling數

 

7.6.1Catalan數

 

7.6.2Stirling數

 

7.7Burnside定理和Plya計數

 

7.7.1置換群

 

7.7.2Burnside定理

 

7.7.3Plya計數

 

7.8母函數

 

7.8.1普通型母函數

 

7.8.2指數型母函數

 

7.8.3母函數與泰勒級數

 

7.9公平組合游戲(博弈論)

 

7.9.1巴什游戲與Pposition、Nposition

 

7.9.2尼姆游戲

 

7.9.3圖游戲與SpragueGrundy函數

 

7.9.4威佐夫游戲

 

小結

 

第8章計算幾何

 

8.1二維幾何

 

8.1.1點和向量

 

8.1.2點積和叉積

 

8.1.3點和線

 

8.1.4多邊形

 

8.1.5凸包

 

8.1.6最近點對

 

8.1.7旋轉卡殼

 

8.1.8半平面交

 

8.2圓

 

8.2.1基本的定義和計算

 

8.2.2最小圓覆蓋

 

8.3三維幾何

 

8.3.1三維點和線

 

8.3.2三維點積

 

8.3.3三維叉積

 

8.3.4最小球覆蓋

 

8.3.5三維凸包

 

8.3.6三維幾何例題

 

小結

 

 

第9章字符串

 

9.1進制哈希

 

9.1.1BKDRHash哈希函數

 

9.1.2進制哈希的應用

 

9.2Manacher

 

9.2.1暴力法求最長迴文子串

 

9.2.2Manacher算法

 

9.2.3模板代碼

 

9.3字典樹

 

9.3.1字典樹的構造

 

9.3.2模板代碼

 

9.4迴文樹

 

9.4.1迴文樹的關鍵技術

 

9.4.2模板代碼

 

9.5KMP

 

9.5.1樸素的模式匹配算法

 

9.5.2KMP算法

 

9.5.3模板代碼和例題

 

9.5.4擴展KMP

 

9.6AC自動機

 

9.6.1AC自動機算法

 

9.6.2模板代碼

 

9.7後綴樹和後綴數組

 

9.7.1後綴樹和後綴數組的概念

 

9.7.2倍增法求後綴數組

 

9.7.3後綴數組的經典應用

 

9.8後綴自動機

 

9.8.1後綴自動機的概念

 

9.8.2endpos和等價類

 

9.8.3後綴自動機的構造

 

9.8.4模板代碼

 

9.8.5後綴自動機的應用

 

小結

 

第10章圖論

 

10.1圖的存儲

 

 

10.1.1鄰接矩陣

 

10.1.2鄰接表

 

10.1.3鏈式前向星

 

10.2拓撲排序

 

10.2.1拓撲排序的概念

 

10.2.2基於BFS的拓撲排序

 

10.2.3基於DFS的拓撲排序

 

10.2.4輸出拓撲排序

 

10.3歐拉路

 

10.3.1歐拉路和歐拉迴路的存在性判斷

 

10.3.2輸出一個歐拉迴路

 

10.4無向圖的連通性

 

10.4.1割點和割邊

 

10.4.2雙連通分量

 

10.5有向圖的連通性

 

10.5.1Kosaraju算法

 

10.5.2Tarjan算法

 

10.6基環樹

 

10.72SAT

 

10.8最短路徑

 

10.8.1FloydWarshall算法

 

10.8.2傳遞閉包

 

10.8.3Dijkstra算法

 

10.8.4BellmanFord算法

 

10.8.5SPFA

 

10.8.6比較BellmanFord算法和Dijkstra算法

 

10.8.7負環和差分約束系統

 

10.9最小生成樹

 

10.9.1Kruskal算法

 

10.9.2Prim算法

 

10.9.3擴展問題

 

10.10最大流

 

10.10.1FordFulkerson方法

 

10.10.2EdmondsKarp算法

 

10.10.3Dinic算法

 

10.10.4ISAP算法

 

10.10.5混合圖的歐拉迴路

 

10.11二分圖

 

10.12最小割

 

10.13費用流

 

小結

 

附錄APython在競賽中的應用

 

A.1大數計算

 

A.2構造測試數據和對拍

 

A.2.1構造隨機數據

 

A.2.2數據去重

 

A.2.3對拍

 

A.3輸入/輸出

 

索引