算法訓(xùn)練營：進(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  超級馬里奧    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自動機(jī)    24
2.1.1  創(chuàng)建字典樹    24
2.1.2  創(chuàng)建AC自動機(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  音樂主題    60
 
第3章  樹上操作    62
3.1  樹鏈剖分    62
3.1.1  預(yù)處理    63
3.1.2  求解最近公共祖先    63
3.1.3  樹鏈剖分與線段樹    66
訓(xùn)練1  樹上距離    71
訓(xùn)練2  樹上操作    73
3.2  點分治    76
3.2.1  樹的重心    76
3.2.2  重心分解    77
訓(xùn)練1  樹上兩個節(jié)點之間的路徑數(shù)    77
訓(xùn)練2  游船之旅    83
3.3  邊分治    88
3.3.1  重建樹    88
3.3.2  求解中心邊    89
3.3.3  中心邊分解    90
訓(xùn)練1  樹上查詢    91
訓(xùn)練2  樹上兩個節(jié)點之間的路徑數(shù)    100
 
第4章  復(fù)雜樹    104
4.1  KD樹    104
4.1.1  創(chuàng)建KD樹    104
4.1.2  搜索m近鄰    106
訓(xùn)練1  最近的取款機(jī)    107
訓(xùn)練2  最近鄰m點    110
4.2  左偏樹    112
4.2.1  左偏樹的性質(zhì)    112
4.2.2  基本操作    114
訓(xùn)練1  猴王    120
訓(xùn)練2  小根堆    123
4.3  動態(tài)樹    125
4.3.1  LCT的性質(zhì)    126
4.3.2  LCT的基本操作    127
訓(xùn)練1  動態(tài)樹的異或和    136
訓(xùn)練2  動態(tài)樹的最值    139
4.4  樹套樹    142
4.4.1  線段樹套平衡樹    142
4.4.2  線段樹套線段樹    143
訓(xùn)練1  動態(tài)區(qū)間問題    143
訓(xùn)練2  打馬賽克    149
 
第5章  可持久化數(shù)據(jù)結(jié)構(gòu)    156
5.1  可持久化線段樹    156
訓(xùn)練1  超級馬里奧    163
訓(xùn)練2  記憶重現(xiàn)    167
5.2  可持久化字典樹    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  最小點割集    211
訓(xùn)練3  最大收益    213
6.6  最小費用最大流    214
訓(xùn)練1  農(nóng)場之旅    218
訓(xùn)練2  航空路線    219
 
第7章  動態(tài)規(guī)劃進(jìn)階    222
7.1  背包問題進(jìn)階    222
7.1.1  多重背包問題    222
訓(xùn)練  硬幣    224
7.1.2  分組背包問題    227
訓(xùn)練  價值最大化    228
7.1.3  混合背包問題    229
訓(xùn)練  最少硬幣    230
7.2  樹形DP進(jìn)階    232
7.2.1  背包類樹形DP    232
訓(xùn)練1  城堡中的寶物    232
訓(xùn)練2  蘋果樹    235
7.2.2  不定根樹形DP    238
訓(xùn)練1  最大累積度    239
訓(xùn)練2  最遠(yuǎn)距離    243
 
第8章  復(fù)雜動態(tài)規(guī)劃及其優(yōu)化    247
8.1  數(shù)位DP    247
訓(xùn)練1  不吉利的數(shù)字    247
訓(xùn)練2  定時炸彈    253
8.2  插頭DP    255
訓(xùn)練1  鋪磚    256
訓(xùn)練2  多回路連通性問題    262
8.3  斜率優(yōu)化    266
訓(xùn)練1  打印文章    266
訓(xùn)練2  批處理作業(yè)    270
8.4  四邊不等式優(yōu)化    275
訓(xùn)練  劃分    277