算法訓練營：進階篇（全彩版）

第1章  數(shù)據(jù)結構進階    1
1.1  分塊算法    1
1.1.1  預處理    2
1.1.2  區(qū)間更新    2
1.1.3  區(qū)間查詢    3
訓練1  超級馬里奧    4
訓練2  序列操作    7
1.2  跳躍表    9
1.2.1  跳躍表的結構體定義    11
1.2.2  查找    12
1.2.3  插入    13
1.2.4  刪除    14
訓練1  第k大的數(shù)    15
訓練2  郁悶的出納員    21
 
第2章  字符串算法進階    24
2.1  AC自動機    24
2.1.1  創(chuàng)建字典樹    24
2.1.2  創(chuàng)建AC自動機    25
2.1.3  模式匹配    27
訓練1  病毒侵襲    28
訓練2  DNA序列    30
2.2  后綴數(shù)組    34
2.2.1  基數(shù)排序    34
2.2.2  后綴數(shù)組詳解    41
2.2.3  后綴數(shù)組的應用    50
訓練1  牛奶模式    57
訓練2  音樂主題    60
 
第3章  樹上操作    62
3.1  樹鏈剖分    62
3.1.1  預處理    63
3.1.2  求解最近公共祖先    63
3.1.3  樹鏈剖分與線段樹    66
訓練1  樹上距離    71
訓練2  樹上操作    73
3.2  點分治    76
3.2.1  樹的重心    76
3.2.2  重心分解    77
訓練1  樹上兩個節(jié)點之間的路徑數(shù)    77
訓練2  游船之旅    83
3.3  邊分治    88
3.3.1  重建樹    88
3.3.2  求解中心邊    89
3.3.3  中心邊分解    90
訓練1  樹上查詢    91
訓練2  樹上兩個節(jié)點之間的路徑數(shù)    100
 
第4章  復雜樹    104
4.1  KD樹    104
4.1.1  創(chuàng)建KD樹    104
4.1.2  搜索m近鄰    106
訓練1  最近的取款機    107
訓練2  最近鄰m點    110
4.2  左偏樹    112
4.2.1  左偏樹的性質    112
4.2.2  基本操作    114
訓練1  猴王    120
訓練2  小根堆    123
4.3  動態(tài)樹    125
4.3.1  LCT的性質    126
4.3.2  LCT的基本操作    127
訓練1  動態(tài)樹的異或和    136
訓練2  動態(tài)樹的最值    139
4.4  樹套樹    142
4.4.1  線段樹套平衡樹    142
4.4.2  線段樹套線段樹    143
訓練1  動態(tài)區(qū)間問題    143
訓練2  打馬賽克    149
 
第5章  可持久化數(shù)據(jù)結構    156
5.1  可持久化線段樹    156
訓練1  超級馬里奧    163
訓練2  記憶重現(xiàn)    167
5.2  可持久化字典樹    172
訓練  最大異或和    173
 
第6章  圖論算法進階    180
6.1  EK算法    183
訓練  排水系統(tǒng)    188
6.2  Dinic算法    188
訓練  電力網絡    193
6.3  ISAP算法    195
訓練  美味佳肴    200
6.4  二分圖匹配    201
6.4.1  最大匹配算法    202
6.4.2  匈牙利算法    202
訓練1  完美的牛棚    206
訓練2  逃脫    207
6.5  最大流最小割    208
訓練1  最小邊割集    210
訓練2  最小點割集    211
訓練3  最大收益    213
6.6  最小費用最大流    214
訓練1  農場之旅    218
訓練2  航空路線    219
 
第7章  動態(tài)規(guī)劃進階    222
7.1  背包問題進階    222
7.1.1  多重背包問題    222
訓練  硬幣    224
7.1.2  分組背包問題    227
訓練  價值最大化    228
7.1.3  混合背包問題    229
訓練  最少硬幣    230
7.2  樹形DP進階    232
7.2.1  背包類樹形DP    232
訓練1  城堡中的寶物    232
訓練2  蘋果樹    235
7.2.2  不定根樹形DP    238
訓練1  最大累積度    239
訓練2  最遠距離    243
 
第8章  復雜動態(tài)規(guī)劃及其優(yōu)化    247
8.1  數(shù)位DP    247
訓練1  不吉利的數(shù)字    247
訓練2  定時炸彈    253
8.2  插頭DP    255
訓練1  鋪磚    256
訓練2  多回路連通性問題    262
8.3  斜率優(yōu)化    266
訓練1  打印文章    266
訓練2  批處理作業(yè)    270
8.4  四邊不等式優(yōu)化    275
訓練  劃分    277