算法訓(xùn)練營(yíng)：進(jìn)階篇（全彩版）

第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ū)間查詢    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ù)鏈剖分與線段樹(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ù)上查詢    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  線段樹(shù)套平衡樹(shù)    142
4.4.2  線段樹(shù)套線段樹(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  可持久化線段樹(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  航空路線    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