算法训练营:海量图解+竞赛刷题(进阶篇)

算法训练营:海量图解+竞赛刷题(进阶篇)
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者:
2021-04
版次: 1
ISBN: 9787121408861
定价: 139.80
装帧: 其他
开本: 16开
纸张: 胶版纸
页数: 656页
  • 本书以海量图解的形式,详细讲解常用的数据结构与算法,并结合竞赛实例引导读者进行刷题实战。通过对本书的学习,读者可掌握22种高级数据结构、7种动态规划算法、5种动态规划优化技巧,以及5种网络流算法,并熟练应用各种算法解决实际问题。
      本书总计8章。第1章讲解实用数据结构,包括并查集、优先队列;第2章讲解区间信息维护与查询,包括倍增、ST、RMQ、LCA、树状数组、线段树和分块;第3章讲解字符串处理,包括字典树、AC自动机和后缀数组;第4章讲解树上操作问题,包括点分治、边分治、树链剖分和动态树;第5章讲解各种平衡二叉树,包括Treap、伸展树和SBT;第6章讲解数据结构进阶,包括KD树、左偏树、跳跃表、树套树和可持久化数据结构;第7章讲解动态规划及其优化,包括背包问题、线性DP、区间DP、树形DP、数位DP、状态压缩DP、插头DP和动态规划优化方法;第8章讲解网络流问题,包括常用网络流算法、二分图*匹配、*流*小割定理和*小费用*流。本书对每个算法都进行详细图解并搭配竞赛实例,重点讲解如何分析问题、优化算法,以期读者在短时间内掌握该算法并进行刷题实战。
      本书面向对算法感兴趣的读者,无论是想扎实内功或参加算法竞赛的学生,还是想进入行业领先企业的求职者,抑或是想提升技术的在职人员,都可以参考本书。若读者从未学过数据结构与算法方面的基础知识,则可参考《算法训练营:海量图解 竞赛刷题(入门篇)》。 陈小玉  

    南阳理工学院副教授,高级程序员,主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营:海量图解 竞赛刷题(入门篇)》《算法训练营:海量图解 竞赛刷题(进阶篇)》,所教学生多次获得ACM、蓝桥杯等算法竞赛奖项。 第1章  实用数据结构... 1

    1.1  并查集... 1

    原理  并查集详解... 1

    训练1  畅通工程... 6

    训练2  方块栈... 7

    训练3  食物链... 10

    训练4  帮派... 16

    1.2  优先队列... 19

    原理1  优先队列的实现原理... 19

    原理2  优先队列详解... 23

    训练1  第k大的数... 26

    训练2  围栏修复... 27

    训练3  表演评分... 29

    训练4  丛林探险... 30

     

    第2章  区间信息维护与查询... 33

    2.1  倍增、ST、RMQ.. 33

    原理1  倍增... 33

    原理2  ST. 34

    原理3  RMQ.. 36

    训练1  区间最值差... 36

    训练2  最频繁值... 37

    训练3  最小分段数... 40

    训练4  二维区间最值差.... 41

    2.2  最近公共祖先LCA.. 43

    原理1  暴力搜索法... 44

    原理2  树上倍增法... 45

    原理3  在线RMQ算法... 49

    原理4  Tarjan算法... 51

    训练1  最近公共祖先... 55

    训练2  树上距离... 57

    训练3  距离查询... 59

    训练4  城市之间的联系... 60

    2.3  树状数组... 62

    原理1  一维树状数组... 62

    原理2  多维树状数组... 67

    训练1  数星星... 69

    训练2  公路交叉数... 71

    训练3  子树查询... 74

    训练4  矩形区域查询... 76

    2.4  线段树... 78

    原理1  线段树的基本操作... 78

    原理2  线段树中的“懒操作”... 83

    训练1  敌兵布阵... 87

    训练2  简单的整数问题... 89

    训练3  数据结构难题... 91

    训练4  颜色统计... 97

    2.5  分块... 102

    原理  分块详解... 102

    训练1  简单的整数问题... 105

    训练2  数字序列... 106

    训练3  区间最值差... 107

    训练4  超级马里奥... 109

    训练5  序列操作... 111

     

    第3章  字符串处理... 115

    3.1  字典树... 115

    原理  字典树详解... 115

    训练1  单词翻译... 120

    训练2  电话表... 122

    训练3  统计难题... 123

    训练4  彩色的木棒... 124

    训练5  最长xor路径... 127

    3.2  AC自动机... 129

    原理  AC自动机详解... 129

    训练1  关键字检索... 132

    训练2  病毒侵袭... 134

    训练3  DNA序列... 136

    训练4  单词情结... 140

    3.3  后缀数组... 145

    原理1  基数排序... 145

    原理2  后缀数组详解... 152

    训练1  牛奶模式... 169

    训练2  口吃的外星人... 171

    训练3  音乐主题... 173

    训练4  星际迷航... 175

     

    第4章  树上操作... 178

    4.1  点分治... 178

    原理  重心分解... 178

    训练1  树上两点之间的路径数... 179

    训练2  游船之旅... 185

    训练3  摩天大树... 189

    训练4  查询子树... 194

    4.2  边分治... 200

    原理  边分治详解... 200

    训练1  树上查询I 203

    训练2  树上查询II 212

    训练3  树上两点之间的路径数... 217

    4.3  树链剖分... 221

    原理  树链剖分详解... 221

    训练1  树上距离... 230

    训练2  树的统计... 231

    训练3  家庭主妇... 232

    训练4  树上操作... 233

    4.4  动态树... 236

    原理  动态树详解... 236

    训练1  距离查询... 247

    训练2  动态树xor和... 249

    训练3  动态树的最值... 252

    训练4  动态树的第2大值... 255

    训练5  树上操作... 261

     

    第5章  平衡二叉树... 263

    5.1  Treap. 263

    原理  Treap详解... 263

    训练1  双重队列... 270

    训练2  普通平衡树... 272

    训练3  黑盒子... 276

    训练4  少林功夫... 279

    5.2  伸展树... 283

    原理  伸展树详解... 283

    训练1  双重队列... 291

    训练2  玩链子... 293

    训练3  超强记忆... 300

    训练4  循环... 310

    5.3  SBT. 324

    原理  SBT详解... 324

    训练1  双重队列... 331

    训练2  第k小的数... 333

    训练3  第k大的数... 334

    训练4  区间第k小... 334

    训练5  郁闷的出纳员... 336

     

    第6章  数据结构进阶... 339

    6.1  KD树... 339

    原理  KD树详解... 339

    训练1  最近的取款机... 343

    训练2  找旅馆... 346

    训练3  最近邻M点... 348

    训练4  蚁巢... 349

    6.2  左偏树... 352

    原理  左偏树详解... 352

    训练1  猴王... 360

    训练2  小根堆... 363

    训练3  路面修整... 365

    训练4  K-单调... 369

    6.3  跳跃表... 373

    原理  跳跃表详解... 373

    训练1  双重队列... 379

    训练2  第k大的数... 381

    训练3  郁闷的出纳员... 386

    6.4  树套树... 388

    原理  树套树详解... 388

    训练1  动态区间问题... 389

    训练2  动态区间第k小... 395

    训练3  矩形区域查询... 396

    训练4  马赛克处理... 400

    6.5  可持久化数据结构... 406

    原理1  可持久化线段树详解... 406

    原理2  可持久化Trie详解... 413

    训练1  超级马里奥... 415

    训练2  记忆重现... 419

    训练3  最大异或和... 424

     

    第7章  动态规划及其优化... 431

    7.1  动态规划求解原理... 431

    原理1  动态规划的三个要素... 432

    原理2  动态规划设计方法... 432

    7.2  背包问题... 433

    原理1  01背包... 433

    训练1  骨头收藏家... 441

    原理2  完全背包... 443

    训练2  存钱罐... 443

    原理3  多重背包... 445

    训练3  硬币... 447

    原理4  分组背包... 449

    训练4  价值最大化... 450

    原理5  混合背包... 452

    训练5  最少的硬币... 452

    7.3  线性DP. 455

    训练1  超级楼梯... 455

    训练2  数字三角形... 456

    训练3  最长上升子序列... 458

    训练4  最长公共子序列... 461

    训练5  最大连续子段和... 462

    7.4  区间DP. 464

    训练1  回文... 464

    训练2  括号匹配... 466

    训练3  猴子派对... 468

    训练4  乘法难题... 470

    7.5  树形DP. 472

    训练1  别墅派对... 473

    训练2  战略游戏... 476

    训练3  工人请愿书... 478

    训练4  完美的服务... 480

    训练5  背包类树形DP. 484

    训练6  苹果树... 487

    训练7  二次扫描与换根... 490

    训练8  最远距离... 494

    7.6  数位DP. 497

    训练1  不吉利的数字... 498

    训练2  定时炸弹... 503

    训练3  Round Numbers. 506

    训练4  计数问题... 508

    训练5  数字权值... 511

    7.7  状态压缩DP. 513

    训练1  旅行商问题... 514

    训练2  旅行商变形1. 520

    训练3  旅行商变形2. 521

    训练4  玉米田... 523

    训练5  炮兵阵地... 525

    训练6  马车旅行... 528

    7.8  插头DP. 531

    训练1  铺砖... 531

    训练2  方格取数... 537

    训练3  多回路连通性问题... 539

    训练4  单回路连通性问题... 543

    训练5  单通路连通性问题... 550

    7.9  动态规划优化... 552

    原理1  倍增优化... 552

    原理2  数据结构优化... 552

    训练1  最长公共上升子序列... 552

    训练2  有序子序列... 554

    训练3  最大化器... 557

    训练4  洒水装置... 559

    原理3  单调队列优化... 562

    训练5  滑动窗口... 563

    训练6  洒水装置... 564

    训练7  股票交易... 565

    原理4  斜率优化... 568

    训练8  打印文章... 569

    训练9  覆盖走道... 573

    训练10  批处理调度... 575

    训练11  划分... 580

    训练12  劳伦斯... 583

    原理5  四边不等式优化... 587

    训练13  划分... 590

     

    第8章  网络流... 592

    8.1  EK算法... 595

    原理  EK算法详解... 595

    训练1  最大流问题... 600

    训练2  排水系统... 600

    8.2  Dinic算法... 601

    原理  Dinic算法详解... 601

    训练1  最大销售量... 605

    训练2  电力网络.... 606

    8.3  ISAP算法... 608

    原理  ISAP算法详解... 608

    训练1  岛屿运输... 613

    训练2  美味佳肴... 614

    训练3  跳跃蜥蜴... 615

    训练4  计算机工厂... 618

    8.4  二分图匹配... 619

    原理1  最大匹配算法... 620

    原理2  匈牙利算法... 621

    训练1  完美的牛棚... 624

    训练2  机器调度... 625

    训练3  逃脱... 626

    8.5  最大流最小割... 627

    原理  最大流最小割定理... 627

    训练1  最小边割集... 629

    训练2  最小点割集... 631

    训练3  双核CPU.. 632

    训练4  最大收益... 633

    8.6  最小费用最大流... 635

    原理  最小费用路算法... 635

    训练1  农场之旅... 639

    训练2  航空路线... 640

    训练3  区间覆盖... 642

    训练4  疏散计划... 643
  • 内容简介:
    本书以海量图解的形式,详细讲解常用的数据结构与算法,并结合竞赛实例引导读者进行刷题实战。通过对本书的学习,读者可掌握22种高级数据结构、7种动态规划算法、5种动态规划优化技巧,以及5种网络流算法,并熟练应用各种算法解决实际问题。
      本书总计8章。第1章讲解实用数据结构,包括并查集、优先队列;第2章讲解区间信息维护与查询,包括倍增、ST、RMQ、LCA、树状数组、线段树和分块;第3章讲解字符串处理,包括字典树、AC自动机和后缀数组;第4章讲解树上操作问题,包括点分治、边分治、树链剖分和动态树;第5章讲解各种平衡二叉树,包括Treap、伸展树和SBT;第6章讲解数据结构进阶,包括KD树、左偏树、跳跃表、树套树和可持久化数据结构;第7章讲解动态规划及其优化,包括背包问题、线性DP、区间DP、树形DP、数位DP、状态压缩DP、插头DP和动态规划优化方法;第8章讲解网络流问题,包括常用网络流算法、二分图*匹配、*流*小割定理和*小费用*流。本书对每个算法都进行详细图解并搭配竞赛实例,重点讲解如何分析问题、优化算法,以期读者在短时间内掌握该算法并进行刷题实战。
      本书面向对算法感兴趣的读者,无论是想扎实内功或参加算法竞赛的学生,还是想进入行业领先企业的求职者,抑或是想提升技术的在职人员,都可以参考本书。若读者从未学过数据结构与算法方面的基础知识,则可参考《算法训练营:海量图解 竞赛刷题(入门篇)》。
  • 作者简介:
    陈小玉  

    南阳理工学院副教授,高级程序员,主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营:海量图解 竞赛刷题(入门篇)》《算法训练营:海量图解 竞赛刷题(进阶篇)》,所教学生多次获得ACM、蓝桥杯等算法竞赛奖项。
  • 目录:
    第1章  实用数据结构... 1

    1.1  并查集... 1

    原理  并查集详解... 1

    训练1  畅通工程... 6

    训练2  方块栈... 7

    训练3  食物链... 10

    训练4  帮派... 16

    1.2  优先队列... 19

    原理1  优先队列的实现原理... 19

    原理2  优先队列详解... 23

    训练1  第k大的数... 26

    训练2  围栏修复... 27

    训练3  表演评分... 29

    训练4  丛林探险... 30

     

    第2章  区间信息维护与查询... 33

    2.1  倍增、ST、RMQ.. 33

    原理1  倍增... 33

    原理2  ST. 34

    原理3  RMQ.. 36

    训练1  区间最值差... 36

    训练2  最频繁值... 37

    训练3  最小分段数... 40

    训练4  二维区间最值差.... 41

    2.2  最近公共祖先LCA.. 43

    原理1  暴力搜索法... 44

    原理2  树上倍增法... 45

    原理3  在线RMQ算法... 49

    原理4  Tarjan算法... 51

    训练1  最近公共祖先... 55

    训练2  树上距离... 57

    训练3  距离查询... 59

    训练4  城市之间的联系... 60

    2.3  树状数组... 62

    原理1  一维树状数组... 62

    原理2  多维树状数组... 67

    训练1  数星星... 69

    训练2  公路交叉数... 71

    训练3  子树查询... 74

    训练4  矩形区域查询... 76

    2.4  线段树... 78

    原理1  线段树的基本操作... 78

    原理2  线段树中的“懒操作”... 83

    训练1  敌兵布阵... 87

    训练2  简单的整数问题... 89

    训练3  数据结构难题... 91

    训练4  颜色统计... 97

    2.5  分块... 102

    原理  分块详解... 102

    训练1  简单的整数问题... 105

    训练2  数字序列... 106

    训练3  区间最值差... 107

    训练4  超级马里奥... 109

    训练5  序列操作... 111

     

    第3章  字符串处理... 115

    3.1  字典树... 115

    原理  字典树详解... 115

    训练1  单词翻译... 120

    训练2  电话表... 122

    训练3  统计难题... 123

    训练4  彩色的木棒... 124

    训练5  最长xor路径... 127

    3.2  AC自动机... 129

    原理  AC自动机详解... 129

    训练1  关键字检索... 132

    训练2  病毒侵袭... 134

    训练3  DNA序列... 136

    训练4  单词情结... 140

    3.3  后缀数组... 145

    原理1  基数排序... 145

    原理2  后缀数组详解... 152

    训练1  牛奶模式... 169

    训练2  口吃的外星人... 171

    训练3  音乐主题... 173

    训练4  星际迷航... 175

     

    第4章  树上操作... 178

    4.1  点分治... 178

    原理  重心分解... 178

    训练1  树上两点之间的路径数... 179

    训练2  游船之旅... 185

    训练3  摩天大树... 189

    训练4  查询子树... 194

    4.2  边分治... 200

    原理  边分治详解... 200

    训练1  树上查询I 203

    训练2  树上查询II 212

    训练3  树上两点之间的路径数... 217

    4.3  树链剖分... 221

    原理  树链剖分详解... 221

    训练1  树上距离... 230

    训练2  树的统计... 231

    训练3  家庭主妇... 232

    训练4  树上操作... 233

    4.4  动态树... 236

    原理  动态树详解... 236

    训练1  距离查询... 247

    训练2  动态树xor和... 249

    训练3  动态树的最值... 252

    训练4  动态树的第2大值... 255

    训练5  树上操作... 261

     

    第5章  平衡二叉树... 263

    5.1  Treap. 263

    原理  Treap详解... 263

    训练1  双重队列... 270

    训练2  普通平衡树... 272

    训练3  黑盒子... 276

    训练4  少林功夫... 279

    5.2  伸展树... 283

    原理  伸展树详解... 283

    训练1  双重队列... 291

    训练2  玩链子... 293

    训练3  超强记忆... 300

    训练4  循环... 310

    5.3  SBT. 324

    原理  SBT详解... 324

    训练1  双重队列... 331

    训练2  第k小的数... 333

    训练3  第k大的数... 334

    训练4  区间第k小... 334

    训练5  郁闷的出纳员... 336

     

    第6章  数据结构进阶... 339

    6.1  KD树... 339

    原理  KD树详解... 339

    训练1  最近的取款机... 343

    训练2  找旅馆... 346

    训练3  最近邻M点... 348

    训练4  蚁巢... 349

    6.2  左偏树... 352

    原理  左偏树详解... 352

    训练1  猴王... 360

    训练2  小根堆... 363

    训练3  路面修整... 365

    训练4  K-单调... 369

    6.3  跳跃表... 373

    原理  跳跃表详解... 373

    训练1  双重队列... 379

    训练2  第k大的数... 381

    训练3  郁闷的出纳员... 386

    6.4  树套树... 388

    原理  树套树详解... 388

    训练1  动态区间问题... 389

    训练2  动态区间第k小... 395

    训练3  矩形区域查询... 396

    训练4  马赛克处理... 400

    6.5  可持久化数据结构... 406

    原理1  可持久化线段树详解... 406

    原理2  可持久化Trie详解... 413

    训练1  超级马里奥... 415

    训练2  记忆重现... 419

    训练3  最大异或和... 424

     

    第7章  动态规划及其优化... 431

    7.1  动态规划求解原理... 431

    原理1  动态规划的三个要素... 432

    原理2  动态规划设计方法... 432

    7.2  背包问题... 433

    原理1  01背包... 433

    训练1  骨头收藏家... 441

    原理2  完全背包... 443

    训练2  存钱罐... 443

    原理3  多重背包... 445

    训练3  硬币... 447

    原理4  分组背包... 449

    训练4  价值最大化... 450

    原理5  混合背包... 452

    训练5  最少的硬币... 452

    7.3  线性DP. 455

    训练1  超级楼梯... 455

    训练2  数字三角形... 456

    训练3  最长上升子序列... 458

    训练4  最长公共子序列... 461

    训练5  最大连续子段和... 462

    7.4  区间DP. 464

    训练1  回文... 464

    训练2  括号匹配... 466

    训练3  猴子派对... 468

    训练4  乘法难题... 470

    7.5  树形DP. 472

    训练1  别墅派对... 473

    训练2  战略游戏... 476

    训练3  工人请愿书... 478

    训练4  完美的服务... 480

    训练5  背包类树形DP. 484

    训练6  苹果树... 487

    训练7  二次扫描与换根... 490

    训练8  最远距离... 494

    7.6  数位DP. 497

    训练1  不吉利的数字... 498

    训练2  定时炸弹... 503

    训练3  Round Numbers. 506

    训练4  计数问题... 508

    训练5  数字权值... 511

    7.7  状态压缩DP. 513

    训练1  旅行商问题... 514

    训练2  旅行商变形1. 520

    训练3  旅行商变形2. 521

    训练4  玉米田... 523

    训练5  炮兵阵地... 525

    训练6  马车旅行... 528

    7.8  插头DP. 531

    训练1  铺砖... 531

    训练2  方格取数... 537

    训练3  多回路连通性问题... 539

    训练4  单回路连通性问题... 543

    训练5  单通路连通性问题... 550

    7.9  动态规划优化... 552

    原理1  倍增优化... 552

    原理2  数据结构优化... 552

    训练1  最长公共上升子序列... 552

    训练2  有序子序列... 554

    训练3  最大化器... 557

    训练4  洒水装置... 559

    原理3  单调队列优化... 562

    训练5  滑动窗口... 563

    训练6  洒水装置... 564

    训练7  股票交易... 565

    原理4  斜率优化... 568

    训练8  打印文章... 569

    训练9  覆盖走道... 573

    训练10  批处理调度... 575

    训练11  划分... 580

    训练12  劳伦斯... 583

    原理5  四边不等式优化... 587

    训练13  划分... 590

     

    第8章  网络流... 592

    8.1  EK算法... 595

    原理  EK算法详解... 595

    训练1  最大流问题... 600

    训练2  排水系统... 600

    8.2  Dinic算法... 601

    原理  Dinic算法详解... 601

    训练1  最大销售量... 605

    训练2  电力网络.... 606

    8.3  ISAP算法... 608

    原理  ISAP算法详解... 608

    训练1  岛屿运输... 613

    训练2  美味佳肴... 614

    训练3  跳跃蜥蜴... 615

    训练4  计算机工厂... 618

    8.4  二分图匹配... 619

    原理1  最大匹配算法... 620

    原理2  匈牙利算法... 621

    训练1  完美的牛棚... 624

    训练2  机器调度... 625

    训练3  逃脱... 626

    8.5  最大流最小割... 627

    原理  最大流最小割定理... 627

    训练1  最小边割集... 629

    训练2  最小点割集... 631

    训练3  双核CPU.. 632

    训练4  最大收益... 633

    8.6  最小费用最大流... 635

    原理  最小费用路算法... 635

    训练1  农场之旅... 639

    训练2  航空路线... 640

    训练3  区间覆盖... 642

    训练4  疏散计划... 643
查看详情
12
相关图书 / 更多
算法训练营:海量图解+竞赛刷题(进阶篇)
算法趣学
英昌盛、董延华、李闯、滕泰 著
算法训练营:海量图解+竞赛刷题(进阶篇)
算法与数据结构
漆涛 著;漆涛 编
算法训练营:海量图解+竞赛刷题(进阶篇)
算法通关之路
路志鹏
算法训练营:海量图解+竞赛刷题(进阶篇)
算法竞赛入门经典——训练指南
刘汝佳 陈锋
算法训练营:海量图解+竞赛刷题(进阶篇)
算法设计与分析(第4版)—微课视频版
吕国英;李茹;王文剑;曹付元;钱宇华;郭丽峰
算法训练营:海量图解+竞赛刷题(进阶篇)
算法竞赛入门经典——算法实现
陈锋
算法训练营:海量图解+竞赛刷题(进阶篇)
算法漫步 乐在其中的计算思维
陈道蓄 李晓明
算法训练营:海量图解+竞赛刷题(进阶篇)
算法设计基础与应用
杨中秋 编著;朱立军;杨威;肖明霞
算法训练营:海量图解+竞赛刷题(进阶篇)
算法训练营:海量图解+竞赛刷题(入门篇)(博文视点出品) 
陈小玉 著
算法训练营:海量图解+竞赛刷题(进阶篇)
算法详解(C++11语言描述)
日沉云起
算法训练营:海量图解+竞赛刷题(进阶篇)
算法领导:如何比机器更优秀
迈克·沃尔什(Mike Walsh)
算法训练营:海量图解+竞赛刷题(进阶篇)
算法设计与分析(大数据与人工智能技术丛书)
王秋芬 著
您可能感兴趣 / 更多
算法训练营:海量图解+竞赛刷题(进阶篇)
算法训练营:海量图解+竞赛刷题(入门篇)(博文视点出品) 
陈小玉 著
算法训练营:海量图解+竞赛刷题(进阶篇)
趣学数据结构
陈小玉 著
算法训练营:海量图解+竞赛刷题(进阶篇)
趣学算法
陈小玉 著