123,123

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

　　本書(shū)圖文并茂、通俗易懂，詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)階知識(shí)，并融入大量的競(jìng)賽實(shí)例和解題技巧，可幫助讀者領(lǐng)悟數(shù)據(jù)結(jié)構(gòu)和算法的精髓，并熟練應(yīng)用其解決實(shí)際問(wèn)題。本書(shū)總計(jì)8章。第1章講解數(shù)據(jù)結(jié)構(gòu)進(jìn)階知識(shí)，涉及分塊算法和跳躍表；第2章講解字符串算法進(jìn)階知識(shí)，涉及AC自動(dòng)機(jī)和后綴數(shù)組；第3章講解樹(shù)上操作，涉及樹(shù)鏈剖分、點(diǎn)分治和邊分治；第4章講解復(fù)雜樹(shù)，涉及KD樹(shù)、左偏樹(shù)、動(dòng)態(tài)樹(shù)和樹(shù)套樹(shù)；第5章講解可持久化數(shù)據(jù)結(jié)構(gòu)，涉及可持久化線(xiàn)段樹(shù)和可持久化字典樹(shù)；第6章講解圖論算法進(jìn)階知識(shí)，涉及EK算法、Dinic算法、ISAP算法、二分圖匹配、最大流最小割和最小費(fèi)用最大流；第7章講解動(dòng)態(tài)規(guī)劃進(jìn)階知識(shí)，涉及背包問(wèn)題進(jìn)階知識(shí)和樹(shù)形DP進(jìn)階知識(shí)；第8章講解復(fù)雜動(dòng)態(tài)規(guī)劃及其優(yōu)化，涉及數(shù)位DP、插頭DP、斜率優(yōu)化和四邊不等式優(yōu)化。本書(shū)面向?qū)?shù)據(jù)結(jié)構(gòu)和算法感興趣的讀者，無(wú)論是想扎實(shí)內(nèi)功或參加算法競(jìng)賽的學(xué)生，還是想進(jìn)入名企的求職者，抑或是想提升核心競(jìng)爭(zhēng)力的在職人員，都可以參考本書(shū)。若想系統(tǒng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，則可參考《算法訓(xùn)練營(yíng)：入門(mén)篇》（全彩版）和《算法訓(xùn)練營(yíng)：提高篇》（全彩版）。

作者簡(jiǎn)介

　　陳小玉高級(jí)程序員，主要研究方向?yàn)樗惴▋?yōu)化和機(jī)器學(xué)習(xí)。出版著作有《算法訓(xùn)練營(yíng)》，所教學(xué)生多次獲得ACM-ICPC、藍(lán)橋杯等算法競(jìng)賽獎(jiǎng)項(xiàng)。

圖書(shū)目錄

第1章數(shù)據(jù)結(jié)構(gòu)進(jìn)階    1
1.1 分塊算法    1
1.1.1 預(yù)處理    2
1.1.2 區(qū)間更新    2
1.1.3 區(qū)間查詢(xún)    3
訓(xùn)練1 超級(jí)馬里奧    4
訓(xùn)練2 序列操作    7
1.2 跳躍表    9
1.2.1 跳躍表的結(jié)構(gòu)體定義    11
1.2.2 查找    12
1.2.3 插入    13
1.2.4 刪除    14
訓(xùn)練1 第k大的數(shù)    15
訓(xùn)練2 郁悶的出納員    21

第2章字符串算法進(jìn)階    24
2.1 AC自動(dòng)機(jī)    24
2.1.1 創(chuàng)建字典樹(shù)    24
2.1.2 創(chuàng)建AC自動(dòng)機(jī)    25
2.1.3 模式匹配    27
訓(xùn)練1 病毒侵襲    28
訓(xùn)練2 DNA序列    30
2.2 后綴數(shù)組    34
2.2.1 基數(shù)排序    34
2.2.2 后綴數(shù)組詳解    41
2.2.3 后綴數(shù)組的應(yīng)用    50
訓(xùn)練1 牛奶模式    57
訓(xùn)練2 音樂(lè)主題    60

第3章樹(shù)上操作    62
3.1 樹(shù)鏈剖分    62
3.1.1 預(yù)處理    63
3.1.2 求解最近公共祖先    63
3.1.3 樹(shù)鏈剖分與線(xiàn)段樹(shù)    66
訓(xùn)練1 樹(shù)上距離    71
訓(xùn)練2 樹(shù)上操作    73
3.2 點(diǎn)分治    76
3.2.1 樹(shù)的重心    76
3.2.2 重心分解    77
訓(xùn)練1 樹(shù)上兩個(gè)節(jié)點(diǎn)之間的路徑數(shù)    77
訓(xùn)練2 游船之旅    83
3.3 邊分治    88
3.3.1 重建樹(shù)    88
3.3.2 求解中心邊    89
3.3.3 中心邊分解    90
訓(xùn)練1 樹(shù)上查詢(xún)    91
訓(xùn)練2 樹(shù)上兩個(gè)節(jié)點(diǎn)之間的路徑數(shù)    100

第4章復(fù)雜樹(shù)    104
4.1 KD樹(shù)    104
4.1.1 創(chuàng)建KD樹(shù)    104
4.1.2 搜索m近鄰    106
訓(xùn)練1 最近的取款機(jī)    107
訓(xùn)練2 最近鄰m點(diǎn)    110
4.2 左偏樹(shù)    112
4.2.1 左偏樹(shù)的性質(zhì)    112
4.2.2 基本操作    114
訓(xùn)練1 猴王    120
訓(xùn)練2 小根堆    123
4.3 動(dòng)態(tài)樹(shù)    125
4.3.1 LCT的性質(zhì)    126
4.3.2 LCT的基本操作    127
訓(xùn)練1 動(dòng)態(tài)樹(shù)的異或和    136
訓(xùn)練2 動(dòng)態(tài)樹(shù)的最值    139
4.4 樹(shù)套樹(shù)    142
4.4.1 線(xiàn)段樹(shù)套平衡樹(shù)    142
4.4.2 線(xiàn)段樹(shù)套線(xiàn)段樹(shù)    143
訓(xùn)練1 動(dòng)態(tài)區(qū)間問(wèn)題    143
訓(xùn)練2 打馬賽克    149

第5章可持久化數(shù)據(jù)結(jié)構(gòu)    156
5.1 可持久化線(xiàn)段樹(shù)    156
訓(xùn)練1 超級(jí)馬里奧    163
訓(xùn)練2 記憶重現(xiàn)    167
5.2 可持久化字典樹(shù)    172
訓(xùn)練最大異或和    173

第6章圖論算法進(jìn)階    180
6.1 EK算法    183
訓(xùn)練排水系統(tǒng)    188
6.2 Dinic算法    188
訓(xùn)練電力網(wǎng)絡(luò)    193
6.3 ISAP算法    195
訓(xùn)練美味佳肴    200
6.4 二分圖匹配    201
6.4.1 最大匹配算法    202
6.4.2 匈牙利算法    202
訓(xùn)練1 完美的牛棚    206
訓(xùn)練2 逃脫    207
6.5 最大流最小割    208
訓(xùn)練1 最小邊割集    210
訓(xùn)練2 最小點(diǎn)割集    211
訓(xùn)練3 最大收益    213
6.6 最小費(fèi)用最大流    214
訓(xùn)練1 農(nóng)場(chǎng)之旅    218
訓(xùn)練2 航空路線(xiàn)   219

第7章動(dòng)態(tài)規(guī)劃進(jìn)階    222
7.1 背包問(wèn)題進(jìn)階    222
7.1.1 多重背包問(wèn)題    222
訓(xùn)練硬幣    224
7.1.2 分組背包問(wèn)題    227
訓(xùn)練價(jià)值最大化    228
7.1.3 混合背包問(wèn)題    229
訓(xùn)練最少硬幣    230
7.2 樹(shù)形DP進(jìn)階    232
7.2.1 背包類(lèi)樹(shù)形DP    232
訓(xùn)練1 城堡中的寶物    232
訓(xùn)練2 蘋(píng)果樹(shù)    235
7.2.2 不定根樹(shù)形DP    238
訓(xùn)練1 最大累積度    239
訓(xùn)練2 最遠(yuǎn)距離    243

第8章復(fù)雜動(dòng)態(tài)規(guī)劃及其優(yōu)化    247
8.1 數(shù)位DP    247
訓(xùn)練1 不吉利的數(shù)字    247
訓(xùn)練2 定時(shí)炸彈    253
8.2 插頭DP    255
訓(xùn)練1 鋪磚    256
訓(xùn)練2 多回路連通性問(wèn)題    262
8.3 斜率優(yōu)化    266
訓(xùn)練1 打印文章    266
訓(xùn)練2 批處理作業(yè)    270
8.4 四邊不等式優(yōu)化    275
訓(xùn)練劃分    277