第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線性丟番圖方程

6.8.2擴展歐幾裡得算丟番圖方程的解

6.8線性丟番圖方程

6.9同餘

6.9.1同餘概述

6.9線性同餘方程

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輸入/輸出

索引

讀者拿到這本書的感覺可能是： 這本書真厚。接下來他有點忐忑和疑惑： 這本書雖然厚，但是它有價值嗎？它的內容和風格適合我嗎？還有其他的一些問題。下面做一個詳細的解答。
為什麼學算法競賽
算法競賽是計算機相關競賽中影響的分支。目前國內影響大的計算機算法類競賽有全國青少年信息學奧林匹克競賽(NOI)、國際大學生程序設計競賽(ICPC)、中國大學生程序設計競賽(CCPC)、藍橋杯全國軟件和信息技術專業人纔大賽(軟件類)、中國高校計算機大賽團體程序設計天梯賽等。每個競賽每年的參賽者，少則幾萬人，多則十幾萬人。

在大學裡，與算法競賽相關的課程有“計算機程序設計”“數據結構與算法”“算法分析與設計”“程序閱讀與編程實踐”“算法與程序設計實踐”“算法藝術與競賽”等。

在算法競賽中獲獎有很多好處。在學校可以獲得獎學金，保研時獲得加分。畢業找工作時更有用，一張算法競賽的獲獎證書
是用人單位判斷求職者能力的重要依據。算法競賽受到學校、學生、用人單位的重視和歡迎。

學習和參加算法競賽，是通往傑出程序員的捷徑。競賽的獲獎者基本上都成長為出色的軟件工程師，並且有很多人是IT公司的創業者。例如當前熱門的自動駕駛公司小馬智行的聯合創始人兼CTO樓天城，是2009年ICPC全球總決賽第二戎啟行公司的員工大多數是ICPC的金牌隊員。

算法競賽在以下幾方面對IT人纔培養起到了關鍵作用： 

(1) 編寫大量代碼。代碼量直接體現了程序員的能力。比爾·蓋茨說： “如果你想雇用一個工程師，看看他寫的代碼，就夠了。如果他沒寫過大量代碼，就不要雇用他。”Linus說： “Talk is cheap，show me the code.”大量編碼是傑出程序員的基本功。算法競賽隊員想獲獎，普遍需要寫5萬~10萬行的代碼。
(2) 掌握豐富的算法知識。算法競賽涉及絕大部分常見的確定性算法，掌握這些知識不僅能在軟件開發中得心應手，而且是進一步探索未知算法的基礎。例如現在非常火爆的、代表了人類未來技術的人工智能研究，涉及許多精深的算法理論，沒有經過基礎算法訓練的人根本無法參與。

(3) 培養計算思維和邏輯思維。一道算法題往往需要綜合多種能力，例如數據結構、算法知識、數學方法、流程和邏輯等，這是計算思維和邏輯思維能力的體現。
(4) 培養團隊合作精神。在軟件行業，團隊合作非常重要。像ICPC、CCPC這樣的團隊賽，把對團隊合作的要求放在了重要位置。一支隊伍的3個人，在同等水平下，配合默契的話可以多做一兩道題，把獲獎等級提高一個檔次。他們在日常訓練中通過長期磨合，互相了解，做到合理分工、優勢互補，從而發揮出的團隊力量。即使是藍橋杯和NOI這樣的個人賽，隊員在學習過程中互助互學，也發揮了團隊的關鍵作用。
為什麼選用這本書

讀者的期望總是很高的。

如果讀者是一名算法競賽的初學者，他非常希望有一本“神書”。讀完這本“神書”之後，他或者在參加大公司的算法題面試時自信滿滿，或者參加算法競賽時代碼噴湧而出，或者在日常工作中能用巧妙的算法解決實際問題……前輩們向他推薦了一些好書，他看了書，做了一些例題，他覺得自己學到了很多算法，掌握了很多競賽技巧，但是遇到實際問題，或者參加競賽時，他還是感覺很暈，發現那些書和例題似乎都用不上。神書在哪裡？

當他跨過初學者的門檻，他會認識到這樣的“神書”其實並不存在。這往往不是書的問題，而是他對書的期望過高了。一些算法競賽相關的教材確實寫得很好，也有很好的口碑，可以說是學習算法競賽的書。但是要將書上的知識轉化為自己的能力，需要經過大量的練習，正如陸遊詩中所說： “紙上得來終覺淺，絕知此事要躬行。”對應到編程這件事上，有兩個重要的學習過程： ①學習經典算法和經典代碼，建立算法思維； ②大量編碼，讓代碼成為自己大腦思維的一部分。

算法競賽的學習難度頗高，它需要一名參賽者掌握以下能力： 豐富的算法知識、快速準確的編碼能力、敏捷的建模能力。
學習算法競賽產生了一個自然的結果： 經過長期深入學習並在算法競賽中得獎的學生，都建立了對自己計算機編程能力的自信，並能順利成為出色的程序員。

算法競賽這樣高難度的學習顯然不是一蹴而就的。算法競賽的學習者分為三個層次： 初學者、中級隊員和高級隊員。本書努力幫助讀者順利度過從初級到高級的學習過程，希望讀者看過本書之後，能說一句： “這本書雖然不神，但是還不錯！”

本書是一本算法競賽“大全”，講解了算法競賽涉及的絕大部分知識點。書中對應的部分也適合這三種層次的學員，陪伴他們從初學者走向高級隊員。

(1) 初學者。一名剛學過C/C 、Java、Python中任意一門編程語言的學生，做了一些編程題目，建立了編碼的興趣，對進一步學習有信心和動力，希望有一本介紹算法競賽知識點的書指導學習，這本書的初級部分正適合他，幫助他了解基礎算法知識點、學習模板代碼、練習基礎題。經過這樣的學習後，他很可能獲得藍橋杯省賽三等獎，甚至更好。不過，他仍沒有獲得ICPC、CCPC銅獎的能力。

(2) 中級隊員。中級隊員順利地跨過了初學者階段，他證明自己已經走上了成為傑出程序員的道路。中級隊員符合這樣的畫像： 精通編程語言，編碼得心應手； 他做過幾百道基礎算法題，並且準備繼續對算法競賽傾心投入； 他有了志同道合、水平相當的隊友一起學習進步； 他遇到了學習瓶頸，計算思維還不夠； 他隻能做簡單題和一些中等題，對難題無從下手。中級隊員可能獲得藍橋杯省賽二等獎、一等獎，也差不多有ICPC、CCPC銅獎的水平。本書的中級部分能幫助他進一步掌握算法知識、提高算法思維能力、練習較難的題目。
(3) 高級隊員。他們獲得了藍橋杯國賽二等獎或一等獎，以及ICPC、CCPC銀牌或金牌。這些獎牌是“高級隊員”的標簽，他們已經足夠被稱為“出色的程序員”，在就業市場上十分搶手。本書的高級部分能幫助他們進一步擴展知識點，增強計算思維。
本書的內容介紹
本書內容的難度涵蓋了初級、中級、高級，下面對本書的章節按難度做一個劃分。

章名初級中級高級