清華大學(xué)出版社官方發(fā)貨，當(dāng)天下單第二天發(fā)貨，周五六日下單周一發(fā)貨。兩本書(shū)籍一起包裝封膜。

全網(wǎng)獨(dú)家5折！

基本信息

書(shū)名： 算法競(jìng)賽

書(shū)碼：9787302615217

定價(jià)：168

出版社：清華大學(xué)出版社

內(nèi)容簡(jiǎn)介

本書(shū)是一本全面、深入解析與算法競(jìng)賽有關(guān)的數(shù)據(jù)結(jié)構(gòu)、算法、代碼的計(jì)算機(jī)教材。

本書(shū)包括十個(gè)專(zhuān)題： 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)、基本算法、搜索、高級(jí)數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)規(guī)劃、數(shù)論和線性代數(shù)、組合數(shù)學(xué)、計(jì)算幾何、字符串和圖論。本書(shū)覆蓋了絕大多數(shù)算法競(jìng)賽考點(diǎn)。

本書(shū)解析了算法競(jìng)賽考核的數(shù)據(jù)結(jié)構(gòu)、算法； 組織了每個(gè)知識(shí)點(diǎn)的理論解析和經(jīng)典例題； 給出了簡(jiǎn)潔、精要的模板代碼； 通過(guò)明快清晰的文字、透徹的圖解，實(shí)現(xiàn)了較好的易讀性。

本書(shū)的讀者對(duì)象是參加算法競(jìng)賽的中學(xué)生和大學(xué)生、準(zhǔn)備面試IT企業(yè)算法題的求職者、需要提高算法能力的開(kāi)發(fā)人員，以及對(duì)計(jì)算機(jī)算法有興趣的廣大科技工作者。

目錄

源碼下載

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

1.1鏈表

  1.1.1動(dòng)態(tài)鏈表

  1.1.2靜態(tài)鏈表

  1.1.3STL list

1.2隊(duì)列

  1.2.1STL queue

  1.2.2手寫(xiě)循環(huán)隊(duì)列

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

  1.2.4優(yōu)先隊(duì)列

1.3棧

  1.3.1STL stack

  1.3.2手寫(xiě)棧

  1.3.3單調(diào)棧

1.4二叉樹(shù)和哈夫曼樹(shù)

  1.4.1二叉樹(shù)的概念

  1.4.2二叉樹(shù)的遍歷

  1.4.3哈夫曼樹(shù)和哈夫曼編碼

1.5堆

  1.5.1二叉堆的概念

  1.5.2二叉堆的操作

  1.5.3二叉堆的手寫(xiě)代碼

  1.5.4堆和priority_queue

小結(jié)

第2章基本算法

2.1算法復(fù)雜度

  2.1.1算法的概念

  2.1.2復(fù)雜度和大O記號(hà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í)數(shù)二分

2.4三分法

  2.4.1原理

  2.4.2實(shí)數(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ù)實(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搜索簡(jiǎn)介

  3.1.2搜索算法的基本思路

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

  3.1.4DFS的常見(jiàn)操作和代碼框架

  3.1.5BFS和DFS的對(duì)比

  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雙向廣搜的兩種實(shí)現(xiàn)

  3.5.3雙向廣搜例題

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

3.7BFS與雙端隊(duì)列

3.8A*算法

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

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

  3.8.3 3種算法的對(duì)比

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

  3.8.5A*算法例題

3.9IDDFS和IDA*

  3.9.1IDDFS

  3.9.2IDA*

小結(jié)

第4章高級(jí)數(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ù)狀數(shù)組

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

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

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

4.3線段樹(shù)

  4.3.1線段樹(shù)的概念

  4.3.2區(qū)間查詢

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

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

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

  4.3.6區(qū)間合并

  4.3.7掃描線

  4.3.8二維線段樹(shù)(樹(shù)套樹(shù))

4.4可持久化線段樹(shù)

  4.4.1可持久化線段樹(shù)的思想

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

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

4.5分塊與莫隊(duì)算法

  4.5.1分塊

  4.5.2基礎(chǔ)莫隊(duì)算法

  4.5.3帶修改的莫隊(duì)算法

  4.5.4樹(shù)上莫隊(duì)

4.6塊狀鏈表

4.7簡(jiǎn)單樹(shù)上問(wèn)題

  4.7.1樹(shù)的重心

  4.7.2樹(shù)的直徑

4.8LCA

  4.8.1倍增法求LCA

  4.8.2Tarjan算法求LCA

  4.8.3LCA的應(yīng)用

4.9樹(shù)上的分治

  4.9.1靜態(tài)點(diǎn)分治

  4.9.2動(dòng)態(tài)點(diǎn)分治

4.10樹(shù)鏈剖分

  4.10.1樹(shù)鏈剖分的概念與LCA

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

4.11二叉查找樹(shù)

4.12替罪羊樹(shù)

  4.12.1不平衡率

  4.12.2替罪羊樹(shù)的操作

  4.12.3例題

4.13Treap樹(shù)

  4.13.1Treap樹(shù)的性質(zhì)

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

4.14FHQ Treap樹(shù)

  4.14.1FHQ的基本操作

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

4.15笛卡兒樹(shù)

  4.15.1笛卡兒樹(shù)的概念

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

  4.15.3笛卡兒樹(shù)和RMQ問(wèn)題

4.16Splay樹(shù)

  4.16.1Splay旋轉(zhuǎn)

  4.16.2Splay樹(shù)的平攤分析

  4.16.3Splay樹(shù)的常用操作和代碼

4.17K-D樹(shù)

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

  4.17.2K-D樹(shù)的概念和基本操作

  4.17.3尋找最近點(diǎn)

  4.17.4區(qū)間查詢

4.18動(dòng)態(tài)樹(shù)與LCT

  4.18.1LCT的思想

  4.18.2從原樹(shù)到輔助樹(shù)

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

  4.18.4LCT的操作

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

小結(jié)

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

5.1DP概念和編程方法

  5.1.1DP的概念

  5.1.2DP的兩種編程方法

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

  5.1.4滾動(dòng)數(shù)組

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

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

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

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

  5.3.3數(shù)位統(tǒng)計(jì)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石子合并問(wèn)題和兩種模板代碼

  5.5.2區(qū)間DP例題

  5.5.3二維區(qū)間DP

5.6樹(shù)形DP

  5.6.1樹(shù)形DP的基本操作

  5.6.2背包與樹(shù)形DP

5.7一般優(yōu)化

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

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

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

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

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

  5.9.2求一個(gè)dp［i］

  5.9.3求所有dp［i］

  5.9.4例題

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

  5.10.1應(yīng)用場(chǎng)合

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

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

  5.10.4四邊形不等式定理

  5.10.5例題

小結(jié)

源碼下載

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

6.1模運(yùn)算

6.2快速冪

6.3矩陣的應(yīng)用

  6.3.1矩陣的計(jì)算

  6.3.2矩陣快速冪

  6.3.3矩陣快速冪加速遞推

  6.3.4矩陣乘法與路徑問(wèn)題

6.4高斯消元

  6.4.1高斯消元的基本操作

  6.4.2高斯-約當(dāng)消元法

  6.4.3例題

6.5異或空間線性基

  6.5.1異或空間線性基的概念

  6.5.2線性基的構(gòu)造

  6.5.3線性基的應(yīng)用

6.60/1分?jǐn)?shù)規(guī)劃

  6.6.1二分法與0/1分?jǐn)?shù)規(guī)劃

  6.6.2應(yīng)用場(chǎng)景

6.7GCD和LCM

  6.7.1GCD

  6.7.2LCM

  6.7.3裴蜀定理

6.8線性丟番圖方程

  6.8.1二元線性丟番圖方程

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

  6.8.3多元線性丟番圖方程

6.9同余

  6.9.1同余概述

  6.9.2一元線性同余方程

  6.9.3逆

  6.9.4同余方程組

6.10素?cái)?shù)(質(zhì)數(shù))

  6.10.1小素?cái)?shù)的判定

  6.10.2大素?cái)?shù)的判定

  6.10.3素?cái)?shù)篩

  6.10.4質(zhì)因數(shù)分解

6.11威爾遜定理

6.12積性函數(shù)

6.13歐拉函數(shù)

  6.13.1歐拉函數(shù)的定義和性質(zhì)

  6.13.2求歐拉函數(shù)的通解公式

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

6.14整除分塊(數(shù)論分塊)

6.15狄利克雷卷積

6.16莫比烏斯函數(shù)和莫比烏斯反演

6.17杜教篩

  6.17.1杜教篩的起源

  6.17.2杜教篩公式的推導(dǎo)

  6.17.3杜教篩算法和復(fù)雜度

  6.17.4杜教篩模板代碼

小結(jié)

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

7.1基本概念

7.2鴿巢原理

7.3二項(xiàng)式定理和楊輝三角

7.4盧卡斯定理

7.5容斥原理

7.6Catalan數(shù)和Stirling數(shù)

  7.6.1Catalan數(shù)

  7.6.2Stirling數(shù)

7.7Burnside定理和Polya計(jì)數(shù)

  7.7.1置換群

  7.7.2Burnside定理

  7.7.3Polya計(jì)數(shù)

7.8母函數(shù)

  7.8.1普通型母函數(shù)

  7.8.2指數(shù)型母函數(shù)

  7.8.3母函數(shù)與泰勒級(jí)數(shù)

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

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

  7.9.2尼姆游戲

  7.9.3圖游戲與Sprague-Grundy函數(shù)

  7.9.4威佐夫游戲

小結(jié)

第8章計(jì)算幾何

8.1二維幾何

  8.1.1點(diǎn)和向量

  8.1.2點(diǎn)積和叉積

  8.1.3點(diǎn)和線

  8.1.4多邊形

  8.1.5凸包

  8.1.6最近點(diǎn)對(duì)

  8.1.7旋轉(zhuǎn)卡殼

  8.1.8半平面交

8.2圓

  8.2.1基本的定義和計(jì)算

  8.2.2最小圓覆蓋

8.3三維幾何

  8.3.1三維點(diǎn)和線

  8.3.2三維點(diǎn)積

  8.3.3三維叉積

  8.3.4最小球覆蓋

  8.3.5三維凸包

  8.3.6三維幾何例題

小結(jié)

第9章字符串

9.1進(jìn)制哈希

  9.1.1BKDRHash哈希函數(shù)

  9.1.2進(jìn)制哈希的應(yīng)用

9.2Manacher

  9.2.1暴力法求長(zhǎng)回文子串

  9.2.2Manacher算法

  9.2.3模板代碼

9.3字典樹(shù)

  9.3.1字典樹(shù)的構(gòu)造

  9.3.2模板代碼

9.4回文樹(shù)

  9.4.1回文樹(shù)的關(guān)鍵技術(shù)

  9.4.2模板代碼

9.5KMP

  9.5.1樸素的模式匹配算法

  9.5.2KMP算法

  9.5.3模板代碼和例題

  9.5.4擴(kuò)展KMP

9.6AC自動(dòng)機(jī)

  9.6.1AC自動(dòng)機(jī)算法

  9.6.2模板代碼

9.7后綴樹(shù)和后綴數(shù)組

  9.7.1后綴樹(shù)和后綴數(shù)組的概念

  9.7.2倍增法求后綴數(shù)組

  9.7.3后綴數(shù)組的經(jīng)典應(yīng)用

9.8后綴自動(dòng)機(jī)

  9.8.1后綴自動(dòng)機(jī)的概念

  9.8.2endpos和等價(jià)類(lèi)

  9.8.3后綴自動(dòng)機(jī)的構(gòu)造

  9.8.4模板代碼

  9.8.5后綴自動(dòng)機(jī)的應(yīng)用

小結(jié)

第10章圖論

10.1圖的存儲(chǔ)

  10.1.1鄰接矩陣

  10.1.2鄰接表

  10.1.3鏈?zhǔn)角跋蛐?/font>