鏈接：pan.baidu.com/s/1nCBflsAaF6NH6beZ40gxew?pwd=go2w?

提取碼：go2w

第1章基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

1.1鏈表

1.1.1動態(tài)鏈表

1.1.2靜態(tài)鏈表

1.1.3STL list

1.2隊列

1.2.1STL queue

1.2.2手寫循環(huán)隊列

1.2.3雙端隊列和單調(diào)隊列

1.2.4優(yōu)先隊列

1.3棧

1.3.1STL stack

1.3.2手寫棧

1.3.3單調(diào)棧

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

小結(jié)

第2章基本算法

2.1算法復(fù)雜度

2.1.1算法的概念

2.1.2復(fù)雜度和大O記號

2.2尺取法

2.2.1尺取法的概念

2.2.2反向掃描

2.2.3同向掃描

2.3二分法

2.3.1二分法的理論背景

2.3.2整數(shù)二分

2.3.3實數(shù)二分

2.4三分法

2.4.1原理

2.4.2實數(shù)三分

2.4.3整數(shù)三分

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函數(shù)實現(xiàn)離散化

2.7.4離散化的應(yīng)用

2.8排序與排列

2.8.1排序函數(shù)

2.8.2排列

2.9分治法

2.9.1漢諾塔和快速冪

2.9.2歸并排序

2.9.3快速排序

2.10貪心法與擬陣

2.10.1貪心法

2.10.2擬陣

小結(jié)

第3章搜索

3.1BFS和DFS基礎(chǔ)

3.1.1搜索簡介

3.1.2搜索算法的基本思路

3.1.3BFS的代碼實現(xiàn)

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

3.1.5BFS和DFS的對比

3.1.6連通性判斷

3.2剪枝

3.2.1BFS判重

3.2.2剪枝的應(yīng)用

3.3洪水填充

3.4BFS與最短路徑

3.5雙向廣搜

3.5.1雙向廣搜的原理和復(fù)雜度分析

3.5.2雙向廣搜的兩種實現(xiàn)

3.5.3雙向廣搜例題

3.6BFS與優(yōu)先隊列

3.7BFS與雙端隊列

3.8A*算法

3.8.1貪心最優(yōu)搜索和Dijkstra算法

3.8.2A*算法的原理和復(fù)雜度

3.8.33種算法的對比

3.8.4h函數(shù)的設(shè)計

3.8.5A*算法例題

3.9IDDFS和IDA*

3.9.1IDDFS

3.9.2IDA*

小結(jié)

第4章高級數(shù)據(jù)結(jié)構(gòu)

4.1并查集

4.1.1并查集的基本操作

4.1.2合并的優(yōu)化

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

4.1.4帶權(quán)并查集

4.2樹狀數(shù)組

4.2.1樹狀數(shù)組的概念和基本編碼

4.2.2樹狀數(shù)組的基本應(yīng)用

4.2.3樹狀數(shù)組的擴展應(yīng)用

4.3線段樹

4.3.1線段樹的概念

4.3.2區(qū)間查詢

4.3.3區(qū)間操作與LazyTag

4.3.4線段樹的基礎(chǔ)應(yīng)用

4.3.5區(qū)間最值和區(qū)間歷史最值

4.3.6區(qū)間合并

4.3.7掃描線

4.3.8二維線段樹(樹套樹)

4.4可持久化線段樹

4.4.1可持久化線段樹的思想

4.4.2區(qū)間第k大/小問題

4.4.3其他經(jīng)典問題

4.5分塊與莫隊算法

4.5.1分塊

4.5.2基礎(chǔ)莫隊算法

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的應(yīng)用

4.9樹上的分治

4.9.1靜態(tài)點分治

4.9.2動態(tài)點分治

4.10樹鏈剖分

4.10.1樹鏈剖分的概念與LCA

4.10.2樹鏈剖分的典型應(yīng)用

4.11二叉查找樹

4.12替罪羊樹

4.12.1不平衡率

4.12.2替罪羊樹的操作

4.12.3例題

4.13Treap樹

4.13.1Treap樹的性質(zhì)

4.13.2基于旋轉(zhuǎn)法的Treap樹操作

4.14FHQ Treap樹

4.14.1FHQ的基本操作

4.14.2FHQ Treap樹的應(yīng)用

4.15笛卡兒樹

4.15.1笛卡兒樹的概念

4.15.2用單調(diào)棧建笛卡兒樹

4.15.3笛卡兒樹和RMQ問題

4.16Splay樹

4.16.1Splay旋轉(zhuǎn)

4.16.2Splay樹的平攤分析

4.16.3Splay樹的常用操作和代碼

4.17KD樹

4.17.1從空間到二叉樹的轉(zhuǎn)換

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

4.17.3尋找最近點

4.17.4區(qū)間查詢

4.18動態(tài)樹與LCT

4.18.1LCT的思想

4.18.2從原樹到輔助樹

4.18.3LCT的存儲和性質(zhì)

4.18.4LCT的操作

4.18.5LCT的基本應(yīng)用

小結(jié)

第5章動態(tài)規(guī)劃

5.1DP概念和編程方法

5.1.1DP的概念

5.1.2DP的兩種編程方法

5.1.3DP的設(shè)計和實現(xiàn)

5.1.4滾動數(shù)組

5.2經(jīng)典線性DP問題

5.3數(shù)位統(tǒng)計DP

5.3.1數(shù)位統(tǒng)計DP的遞推實現(xiàn)

5.3.2數(shù)位統(tǒng)計DP的記憶化搜索實現(xiàn)

5.3.3數(shù)位統(tǒng)計DP例題

5.4狀態(tài)壓縮DP

5.4.1引子

5.4.2狀態(tài)壓縮DP的原理

5.4.3狀態(tài)壓縮DP例題

5.4.4三進(jìn)制狀態(tài)壓縮DP

5.5區(qū)間DP

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

5.5.2區(qū)間DP例題

5.5.3二維區(qū)間DP

5.6樹形DP

5.6.1樹形DP的基本操作

5.6.2背包與樹形DP

5.7一般優(yōu)化

5.8單調(diào)隊列優(yōu)化

5.8.1單調(diào)隊列優(yōu)化的原理

5.8.2單調(diào)隊列優(yōu)化例題

5.9斜率優(yōu)化/凸殼優(yōu)化

5.9.1把狀態(tài)轉(zhuǎn)移方程變換為平面的斜率問題

5.9.2求一個dp［i］

5.9.3求所有dp［i］

5.9.4例題

5.10四邊形不等式優(yōu)化

5.10.1應(yīng)用場合

5.10.2四邊形不等式優(yōu)化操作

5.10.3四邊形不等式定義和單調(diào)性定義

5.10.4四邊形不等式定理

5.10.5例題

小結(jié)

源碼下載

第6章數(shù)論和線性代數(shù)

小結(jié)

第7章組合數(shù)學(xué)

第8章計算幾何

小結(jié)

第9章字符串

小結(jié)

第10章圖論

小結(jié)

附錄APython在競賽中的應(yīng)用

A.1大數(shù)計算

A.2構(gòu)造測試數(shù)據(jù)和對拍

A.2.1構(gòu)造隨機數(shù)據(jù)

A.2.2數(shù)據(jù)去重

A.2.3對拍

A.3輸入/輸出

索引

查看全部↓

前言/序言

讀者拿到這本書的第一感覺可能是： 這本書真厚。接下來他有點忐忑和疑惑： 這本書雖然厚，但是它有價值嗎？它的內(nèi)容和風(fēng)格適合我嗎？還有其他的一些問題。下面做一個詳細(xì)的解答。

為什么學(xué)算法競賽

算法競賽是計算機相關(guān)競賽中影響最大的分支。目前國內(nèi)影響大的計算機算法類競賽有全國青少年信息學(xué)奧林匹克競賽(NOI)、國際大學(xué)生程序設(shè)計競賽(ICPC)、中國大學(xué)生程序設(shè)計競賽(CCPC)、藍(lán)橋杯全國軟件和信息技術(shù)專業(yè)人才大賽(軟件類)、中國高校計算機大賽團(tuán)體程序設(shè)計天梯賽等。每個競賽每年的參賽者，少則幾萬人，多則十幾萬人。

在大學(xué)里，與算法競賽相關(guān)的課程有“計算機程序設(shè)計”“數(shù)據(jù)結(jié)構(gòu)與算法”“算法分析與設(shè)計”“程序閱讀與編程實踐”“算法與程序設(shè)計實踐”“算法藝術(shù)與競賽”等。

在算法競賽中獲獎有很多好處。在學(xué)?？梢垣@得獎學(xué)金，保研時獲得加分。畢業(yè)找工作時更有用，一張算法競賽的獲獎證書

是用人單位判斷求職者能力的重要依據(jù)。算法競賽受到學(xué)校、學(xué)生、用人單位的重視和歡迎。

學(xué)習(xí)和參加算法競賽，是通往杰出程序員的捷徑。競賽的獲獎?wù)呋旧隙汲砷L為出色的軟件工程師，并且有很多人是IT公司的創(chuàng)業(yè)者。例如當(dāng)前熱門的自動駕駛公司小馬智行的聯(lián)合創(chuàng)始人兼CTO樓天城，是2009年ICPC全球總決賽第二名； 元戎啟行公司的員工大多數(shù)是ICPC的金牌隊員。