注重体验与质量的电子书资源下载网站
分类于: 云计算&大数据 其它
简介
目录
第一部分 开始解决问题
第1 章 解决问题与程序设计竞赛 4
1.1 引言 4
1.2 程序设计竞赛 4
1.3 阅读本书的方法 7
1.4 值得参加的程序设计竞赛 8
1.5 对赛前准备工作的一些建议 9
1.6 续读 12
第2 章 解决问题概述 13
2.1 引言 13
2.2 解决问题的过程 13
2.3 解决问题的策略 17
2.4 续读 26
第3 章 编码与调试 27
3.1 引言:不要忽视编码的重要性 27
3.2 编写优秀代码的原则 27
3.3 常见失误 32
3.4 调试与测试 39
3.5 变量的取值范围 42
3.6 理解实数型数据类型 46
3.7 续读 55
第二部分 算法分析
第4 章 分析算法的时间复杂度 60
4.1 引言 60
4.2 线性时间算法 62
4.3 次线性时间算法 65
4.4 指数时间算法 67
4.5 时间复杂度 70
4.6 推测执行时间 76
4.7 计算复杂度类:P、NP、NP-完备 81
4.8 续读 84
第5 章 算法正确性证明 85
5.1 引言 85
5.2 数学归纳法和循环不变式 86
5.3 归谬法 90
5.4 其他技巧 92
5.5 续读 95
第三部分 算法设计范式
第6 章 暴力解决法 99
6.1 引言 99
6.2 递归调用和穷举搜索法 100
6.3 练习题:郊游(习题 ID:PICNIC,难度:低) 106
6.4 解题:郊游 107
6.5 练习题:盖游戏板(习题 ID:BOARDCOVER,难度:低) 109
6.6 解题:盖游戏板 111
6.7 优化问题 113
6.8 练习题:时钟同步(习题 ID:CLOCKSYNC,难度:中) 116
6.9 解题:时钟同步 117
6.10 常见穷举搜索类型 119
第7 章 分治法 120
7.1 引言 120
7.2 练习题:四叉树问题(题目 ID:QUADTREE,难度:低) 130
7.3 解题:四叉树问题 131
7.4 练习题:切割篱笆(习题 ID:FENCE,难度:中) 134
7.5 解题:切割篱笆 135
7.6 练习题:粉丝见面会(题目 ID:FANMEETING,难度:高) 139
7.7 解题:粉丝见面会 141
第8 章 动态规划法 143
8.1 引言 143
8.2 练习题:通配符(习题 ID:WILDCARD,难度:中) 151
8.3 解题:通配符 152
8.4 典型优化问题 156
8.5 练习题:合并LIS(题目 ID:JLIS,难度:低) 163
8.6 解题:合并LIS 164
8.7 练习题:背诵圆周率(题目 ID:PI,难度:低) 166
8.8 解题:背诵圆周率 167
8.9 练习题:Quantization(题目 ID:QUANTIZE,难度:中) 169
8.10 解题:Quantization 170
8.11 所有可能的个数与概率 174
8.12 练习题:非对称铺设(题目 ID:ASYMTILING,难度:低) 180
8.13 解题:非对称铺设 181
8.14 练习题:多联骨牌(题目 ID:POLY,难度:中) 183
8.15 解题:多联骨牌 185
8.16 练习题:逃狱的韩尼拔博士(题目 ID:NUMB3RS,难度:中) 187
8.17 解题:逃狱的韩尼拔博士 189
第9 章 动态规划技巧 194
9.1 计算优化问题的实际答案 194
9.2 练习题:打包行李(题目 ID:PACKING,难度:中) 195
9.3 解题:打包行李 197
9.4 练习题:光学字符识别(题目 ID:OCR,难度:高) 199
9.5 解题:光学字符识别 201
9.6 计算第k个答案 204
9.7 练习题:第k个最大递增子序列(题目 ID:KLIS,难度:高) 209
9.8 解题:第k个最长递增子序列 210
9.9 练习题:龙曲线(题目 ID:DRAGON,难度:中) 214
9.10 解题:龙曲线 216
9.11 对非整数型输入的制表 219
9.12 练习题:韦布巴津(题目 ID:ZIMBABWE,难度:高) 224
9.13 解题:韦布巴津 225
9.14 练习题:恢复实验数据(题目 ID:RESTORE,难度:中) 230
9.15 解题:恢复实验数据 231
9.16 组合游戏 234
9.17 练习题:数字游戏(题目 ID:NUMBERGAME,难度:低) 239
9.18 解题:数字游戏 240
9.19 练习题:方块游戏(题目 ID:BLOCKGAME,难度:中) 242
9.20 解题:方块游戏 243
9.21 迭代动态规划法 245
9.22 练习题:回转寿司(题目 ID:SUSHI,难度:中) 249
9.23 解题:回转寿司 250
9.24 练习题:Genius(题目 ID:GENIUS,难度:中) 253
9.25 解题:Genius 254
9.26 续读 256
第10 章 贪心法 257
10.1 引言 257
10.2 练习题:加热便当(题目 ID:LUNCHBOX,难度:低) 264
10.3 解题:加热便当 265
10.4 练习题:合并字符串(题目 ID:STRJOIN,难度:中) 268
10.5 解题:合并字符串 269
10.6 练习题:米那斯雅诺(题目 ID:MINASTIRITH,难度:高) 273
10.7 解题:米那斯雅诺 275
第11 章 组合搜索 281
11.1 引言 281
11.2 组合搜索的方法 283
11.3 练习题:盖游戏板2(题目 ID:BOARDCOVER2,难度:低) 298
11.4 解题:盖游戏板2 299
11.5 练习题:患有严重过敏症的朋友们(题目 ID:ALLERGY,难度:中) 303
11.6 解题:患有严重过敏症的朋友们........304
11.7 练习题:数谜(题目 ID:KAKURO2,难度:中) 307
11.8 解题:数谜 309
11.9 续读 315
第12 章 将优化问题转换为决策问题求解 316
12.1 引言 316
12.2 练习题:南极基地(题目 ID:ARCTIC,难度:低) 320
12.3 解题:南极基地 321
12.4 练习题:加拿大旅行(题目 ID:CANADATRIP,难度:中) 323
12.5 解题:加拿大旅行 324
12.6 练习题:退选课程(题目 ID:WITHDRAWAL,难度:高) 326
12.7 解题:退选课程 327
第四部分 一些著名的算法
第13 章 数值分析 331
13.1 引言 331
13.2 二分法 331
13.3 练习题:提高获胜率(题目 ID:RATIO,难度:低) 338
13.4 解题:提高获胜率 339
13.5 三叉搜索 341
13.6 练习题:花粉化石(题目 ID:FOSSIL,难度:高) 346
13.7 解题:花粉化石 347
13.8 其他主题 351
第14 章 整数论 352
14.1 引言 352
14.2 素数 352
14.3 练习题:密码486(题目 ID:PASS486,难度:中) 357
14.4 解题:密码486 357
14.5 欧几里得算法 360
14.6 练习题:魔法药水(题目 ID:POTION,难度:中) 361
14.7 解题:魔法药水 362
14.8 模运算 364
14.9 续读 366
第15 章 计算几何 367
15.1 引言 367
15.2 计算几何的工具 367
15.3 相交、距离、面积 373
15.4 练习题:弹球模拟(题目 ID:PINBALL,难度:高) 377
15.5 解题:弹球模拟 379
15.6 多边形 383
15.7 练习题:金银岛(题目 ID:TREASURE,难度:高) 386
15.8 解题:金银岛 387
15.9 练习题:是呆子?不是呆子?(题目ID:NERDS,难度:中) 390
15.10 解题:是呆子?不是呆子? 392
15.11 计算几何算法设计范式 396
15.12 常见失误与注意事项 403
15.13 续读 404
第五部分 基本数据结构
第16 章 位掩码 410
16.1 引言 410
16.2 利用位掩码实现集合 413
16.3 位掩码应用示例 417
16.4 练习题:毕业学期(题目 ID:GRADUATION,难度:中) 420
16.5 解题:毕业学期 422
16.6 续读 424
第17 章 部分和 425
17.1 引言 425
17.2 练习题:圣诞娃娃(题目 ID:CHRISTMAS,难度:中) 429
17.3 解题:圣诞娃娃 430
17.4 其他学习内容 432
第18 章 线性数据结构 433
18.1 引言 433
18.2 动态数组 433
18.3 链表 437
18.4 动态数组和链表的比较 440
18.5 练习题:约瑟夫斯(题目 ID:JOSEPHUS,难度:低) 440
18.6 解题:约瑟夫斯 441
18.7 续读 442
第19 章 队列、栈以及双端队列 443
19.1 引言 443
19.2 队列、栈以及双端队列的实现方法 444
19.3 队列与栈的应用 445
19.4 练习题:不匹配括号(题目 ID:BRACKETS2,难度:低) 448
19.5 解题:不匹配括号 449
19.6 练习题:分析外星信号(题目 ID:ITES,难度:中) 450
19.7 解题:分析外星信号 451
第20 章 字符串 455
20.1 引言 455
20.2 字符串检索 456
20.3 练习题:宰河的保险箱(题目 ID:JAEHASAFE,难度:中) 466
20.4 解题:宰河的保险箱 467
20.5 后缀数组 468
20.6 练习题:口头禅(题目 ID:HABIT,难度:中) 476
20.7 解题:口头禅 477
20.8 续读 478
第六部分 树
第21 章 树的实现与遍历 481
21.1 引言 481
21.2 树的遍历 483
21.3 练习题:变更树的遍历顺序(题目 ID:TRAVERSAL,难度:低) 484
21.4 解题:变更树的遍历顺序 486
21.5 练习题:要塞(题目 ID:FORTRESS,难度:中) 487
21.6 解题:要塞 488
第22 章 二叉搜索树 493
22.1 引言 493
22.2 二叉搜索树的定义和操作 493
22.3 时间复杂度分析与平衡二叉搜索树 496
22.4 练习题:是呆子?不是呆子?2(题目ID:NERD2,难度:中) 496
22.5 解题:是呆子?不是呆子?2 498
22.6 直接实现平衡二叉搜索树:树堆 501
22.7 练习题:反转插入排序(题目 ID:INSERTION,难度:中) 508
22.8 解题:反转插入排序 509
第23 章 优先级队列和堆 511
23.1 引言 511
23.2 堆的定义与实现方法 512
23.3 练习题:变化的中间值(题目 ID:RUNNINGMEDIAN,难度:低) 518
23.4 解题:变化的中间值 519
第24 章 区间树 521
24.1 区间树:区间相关问题解答 521
24.2 练习题:登山路(题目 ID:MORDDR,难度:中) 527
24.3 解题:登山路 528
24.4 练习题:寻根问祖(题目 ID:FAMILYTREE,难度:高) 529
24.5 解题:寻根问祖 530
24.6 树状数组:快速而简单的区间和 533
24.7 练习题:计算插入排序的时间(题目 ID:MEASURETIME,难度:中) 536
24.8 解题:计算插入排序的时间 537
第25 章 互斥集合 541
25.1 引言 541
25.2 练习题:编辑器之争(题目 ID:EDITORWARS,难度:中) 546
25.3 解题:编辑器之争 548
第26 章 字典树 553
26.1 引言 553
26.2 练习题:再见,谢谢所有的鱼(题目 ID:SOLONG,难度:中) 557
26.3 解题:再见,谢谢所有的鱼 559
26.4 利用字典树检索多重字符串 563
26.5 练习题:安全终结者(题目 ID:NH,难度:高) 569
26.6 解题:安全终结者 570
第七部分 图
第27 章 图的表示方式及定义 576
27.1 引言 576
27.2 图的应用示例 579
27.3 隐式图结构 580
27.4 图的几种表示法 581
第28 章 图的深度优先搜索 585
28.1 引言 585
28.2 练习题:古语词典(习题 ID:DICTIONARY,难度:低) 590
28.3 解题:古语词典 591
28.4 欧拉回路 594
28.5 练习题:有限单词接龙(题目 ID:WORDCHAIN,难度:低) 597
28.6 解题:有限单词接龙 598
28.7 理论背景及应用 602
28.8 练习题:安装监控摄像头(题目 ID:GALLERY,难度:中) 613
28.9 解题:安装监控摄像头 614
28.10 练习题:安排会议室(题目 ID:MEETINGROOM,难度:高) 616
28.11 解题:安排会议室 618
第29 章 图的宽度优先搜索 625
29.1 引言 625
29.2 练习题:排序游戏(题目 ID:SORTGAME,难度:中) 629
29.3 解题:排序游戏 630
29.4 练习题:儿童节(题目 ID:CHILDRENDAY,难度:高) 633
29.5 解题:儿童节 634
29.6 最短路径策略 637
29.7 练习题:汉诺塔(题目 ID:HANOI4B,难度:中) 648
29.8 解题:汉诺塔 650
第30 章 最短路径问题 653
30.1 引言 653
30.2 迪杰斯特拉最短路径算法 654
30.3 练习题:信号路由(题目 ID:ROUTING,难度:低) 661
30.4 解题:信号路由 662
30.5 练习题:消防车(题目 ID:FIRETRUCKS,难度:中) 663
30.6 解题:消防车 664
30.7 练习题:铁人N项比赛(题目 ID:NTHLON,难度:高) 665
30.8 解题:铁人N项比赛 667
30.9 贝尔曼-福特最短路径算法 669
30.10 练习题:时间旅行(题目 ID:TIMETRIP,难度:中) 674
30.11 解题:时间旅行 675
30.12 弗洛伊德多源最短路径算法 677
30.13 练习题:检查酒驾(题目 ID:DRUNKEN,难度:中) 682
30.14 解题:检查酒驾 684
30.15 练习题:竞选承诺(题目 ID:PROMISES,难度:中) 685
30.16 解题:竞选承诺 687
第31 章 最小生成树 689
31.1 引言 689
31.2 克鲁斯克尔最小生成树算法 690
31.3 普里姆最小生成树算法 694
31.4 练习题:局域网(题目 ID:LAN,难度:低) 697
31.5 解题:局域网 698
31.6 练习题:选定旅行路线(题目 ID:TPATH,难度:高) 699
31.7 解题:选定旅行路线 700
第32 章 网络流 705
32.1 引言 705
32.2 福特-富尔克森算法 706
32.3 网络建模 713
32.4 练习题:操纵比赛(题目 ID:MATCHFIX,难度:中) 715
32.5 解题:操纵比赛 717
32.6 练习题:国家项目(题目 ID:PROJECTS,难度:高) 719
32.7 解题:国家项目 720
32.8 二分图匹配 723
32.9 练习题:象(题目 ID:BISHOPS,难度:中) 729
32.10 解题:象 730
32.11 练习题:设置陷阱(题目 ID:TRAPCARD,难度:高) 732
32.12 解题:设置陷阱 734
32.13 其他学习内容 737
第1 章 解决问题与程序设计竞赛 4
1.1 引言 4
1.2 程序设计竞赛 4
1.3 阅读本书的方法 7
1.4 值得参加的程序设计竞赛 8
1.5 对赛前准备工作的一些建议 9
1.6 续读 12
第2 章 解决问题概述 13
2.1 引言 13
2.2 解决问题的过程 13
2.3 解决问题的策略 17
2.4 续读 26
第3 章 编码与调试 27
3.1 引言:不要忽视编码的重要性 27
3.2 编写优秀代码的原则 27
3.3 常见失误 32
3.4 调试与测试 39
3.5 变量的取值范围 42
3.6 理解实数型数据类型 46
3.7 续读 55
第二部分 算法分析
第4 章 分析算法的时间复杂度 60
4.1 引言 60
4.2 线性时间算法 62
4.3 次线性时间算法 65
4.4 指数时间算法 67
4.5 时间复杂度 70
4.6 推测执行时间 76
4.7 计算复杂度类:P、NP、NP-完备 81
4.8 续读 84
第5 章 算法正确性证明 85
5.1 引言 85
5.2 数学归纳法和循环不变式 86
5.3 归谬法 90
5.4 其他技巧 92
5.5 续读 95
第三部分 算法设计范式
第6 章 暴力解决法 99
6.1 引言 99
6.2 递归调用和穷举搜索法 100
6.3 练习题:郊游(习题 ID:PICNIC,难度:低) 106
6.4 解题:郊游 107
6.5 练习题:盖游戏板(习题 ID:BOARDCOVER,难度:低) 109
6.6 解题:盖游戏板 111
6.7 优化问题 113
6.8 练习题:时钟同步(习题 ID:CLOCKSYNC,难度:中) 116
6.9 解题:时钟同步 117
6.10 常见穷举搜索类型 119
第7 章 分治法 120
7.1 引言 120
7.2 练习题:四叉树问题(题目 ID:QUADTREE,难度:低) 130
7.3 解题:四叉树问题 131
7.4 练习题:切割篱笆(习题 ID:FENCE,难度:中) 134
7.5 解题:切割篱笆 135
7.6 练习题:粉丝见面会(题目 ID:FANMEETING,难度:高) 139
7.7 解题:粉丝见面会 141
第8 章 动态规划法 143
8.1 引言 143
8.2 练习题:通配符(习题 ID:WILDCARD,难度:中) 151
8.3 解题:通配符 152
8.4 典型优化问题 156
8.5 练习题:合并LIS(题目 ID:JLIS,难度:低) 163
8.6 解题:合并LIS 164
8.7 练习题:背诵圆周率(题目 ID:PI,难度:低) 166
8.8 解题:背诵圆周率 167
8.9 练习题:Quantization(题目 ID:QUANTIZE,难度:中) 169
8.10 解题:Quantization 170
8.11 所有可能的个数与概率 174
8.12 练习题:非对称铺设(题目 ID:ASYMTILING,难度:低) 180
8.13 解题:非对称铺设 181
8.14 练习题:多联骨牌(题目 ID:POLY,难度:中) 183
8.15 解题:多联骨牌 185
8.16 练习题:逃狱的韩尼拔博士(题目 ID:NUMB3RS,难度:中) 187
8.17 解题:逃狱的韩尼拔博士 189
第9 章 动态规划技巧 194
9.1 计算优化问题的实际答案 194
9.2 练习题:打包行李(题目 ID:PACKING,难度:中) 195
9.3 解题:打包行李 197
9.4 练习题:光学字符识别(题目 ID:OCR,难度:高) 199
9.5 解题:光学字符识别 201
9.6 计算第k个答案 204
9.7 练习题:第k个最大递增子序列(题目 ID:KLIS,难度:高) 209
9.8 解题:第k个最长递增子序列 210
9.9 练习题:龙曲线(题目 ID:DRAGON,难度:中) 214
9.10 解题:龙曲线 216
9.11 对非整数型输入的制表 219
9.12 练习题:韦布巴津(题目 ID:ZIMBABWE,难度:高) 224
9.13 解题:韦布巴津 225
9.14 练习题:恢复实验数据(题目 ID:RESTORE,难度:中) 230
9.15 解题:恢复实验数据 231
9.16 组合游戏 234
9.17 练习题:数字游戏(题目 ID:NUMBERGAME,难度:低) 239
9.18 解题:数字游戏 240
9.19 练习题:方块游戏(题目 ID:BLOCKGAME,难度:中) 242
9.20 解题:方块游戏 243
9.21 迭代动态规划法 245
9.22 练习题:回转寿司(题目 ID:SUSHI,难度:中) 249
9.23 解题:回转寿司 250
9.24 练习题:Genius(题目 ID:GENIUS,难度:中) 253
9.25 解题:Genius 254
9.26 续读 256
第10 章 贪心法 257
10.1 引言 257
10.2 练习题:加热便当(题目 ID:LUNCHBOX,难度:低) 264
10.3 解题:加热便当 265
10.4 练习题:合并字符串(题目 ID:STRJOIN,难度:中) 268
10.5 解题:合并字符串 269
10.6 练习题:米那斯雅诺(题目 ID:MINASTIRITH,难度:高) 273
10.7 解题:米那斯雅诺 275
第11 章 组合搜索 281
11.1 引言 281
11.2 组合搜索的方法 283
11.3 练习题:盖游戏板2(题目 ID:BOARDCOVER2,难度:低) 298
11.4 解题:盖游戏板2 299
11.5 练习题:患有严重过敏症的朋友们(题目 ID:ALLERGY,难度:中) 303
11.6 解题:患有严重过敏症的朋友们........304
11.7 练习题:数谜(题目 ID:KAKURO2,难度:中) 307
11.8 解题:数谜 309
11.9 续读 315
第12 章 将优化问题转换为决策问题求解 316
12.1 引言 316
12.2 练习题:南极基地(题目 ID:ARCTIC,难度:低) 320
12.3 解题:南极基地 321
12.4 练习题:加拿大旅行(题目 ID:CANADATRIP,难度:中) 323
12.5 解题:加拿大旅行 324
12.6 练习题:退选课程(题目 ID:WITHDRAWAL,难度:高) 326
12.7 解题:退选课程 327
第四部分 一些著名的算法
第13 章 数值分析 331
13.1 引言 331
13.2 二分法 331
13.3 练习题:提高获胜率(题目 ID:RATIO,难度:低) 338
13.4 解题:提高获胜率 339
13.5 三叉搜索 341
13.6 练习题:花粉化石(题目 ID:FOSSIL,难度:高) 346
13.7 解题:花粉化石 347
13.8 其他主题 351
第14 章 整数论 352
14.1 引言 352
14.2 素数 352
14.3 练习题:密码486(题目 ID:PASS486,难度:中) 357
14.4 解题:密码486 357
14.5 欧几里得算法 360
14.6 练习题:魔法药水(题目 ID:POTION,难度:中) 361
14.7 解题:魔法药水 362
14.8 模运算 364
14.9 续读 366
第15 章 计算几何 367
15.1 引言 367
15.2 计算几何的工具 367
15.3 相交、距离、面积 373
15.4 练习题:弹球模拟(题目 ID:PINBALL,难度:高) 377
15.5 解题:弹球模拟 379
15.6 多边形 383
15.7 练习题:金银岛(题目 ID:TREASURE,难度:高) 386
15.8 解题:金银岛 387
15.9 练习题:是呆子?不是呆子?(题目ID:NERDS,难度:中) 390
15.10 解题:是呆子?不是呆子? 392
15.11 计算几何算法设计范式 396
15.12 常见失误与注意事项 403
15.13 续读 404
第五部分 基本数据结构
第16 章 位掩码 410
16.1 引言 410
16.2 利用位掩码实现集合 413
16.3 位掩码应用示例 417
16.4 练习题:毕业学期(题目 ID:GRADUATION,难度:中) 420
16.5 解题:毕业学期 422
16.6 续读 424
第17 章 部分和 425
17.1 引言 425
17.2 练习题:圣诞娃娃(题目 ID:CHRISTMAS,难度:中) 429
17.3 解题:圣诞娃娃 430
17.4 其他学习内容 432
第18 章 线性数据结构 433
18.1 引言 433
18.2 动态数组 433
18.3 链表 437
18.4 动态数组和链表的比较 440
18.5 练习题:约瑟夫斯(题目 ID:JOSEPHUS,难度:低) 440
18.6 解题:约瑟夫斯 441
18.7 续读 442
第19 章 队列、栈以及双端队列 443
19.1 引言 443
19.2 队列、栈以及双端队列的实现方法 444
19.3 队列与栈的应用 445
19.4 练习题:不匹配括号(题目 ID:BRACKETS2,难度:低) 448
19.5 解题:不匹配括号 449
19.6 练习题:分析外星信号(题目 ID:ITES,难度:中) 450
19.7 解题:分析外星信号 451
第20 章 字符串 455
20.1 引言 455
20.2 字符串检索 456
20.3 练习题:宰河的保险箱(题目 ID:JAEHASAFE,难度:中) 466
20.4 解题:宰河的保险箱 467
20.5 后缀数组 468
20.6 练习题:口头禅(题目 ID:HABIT,难度:中) 476
20.7 解题:口头禅 477
20.8 续读 478
第六部分 树
第21 章 树的实现与遍历 481
21.1 引言 481
21.2 树的遍历 483
21.3 练习题:变更树的遍历顺序(题目 ID:TRAVERSAL,难度:低) 484
21.4 解题:变更树的遍历顺序 486
21.5 练习题:要塞(题目 ID:FORTRESS,难度:中) 487
21.6 解题:要塞 488
第22 章 二叉搜索树 493
22.1 引言 493
22.2 二叉搜索树的定义和操作 493
22.3 时间复杂度分析与平衡二叉搜索树 496
22.4 练习题:是呆子?不是呆子?2(题目ID:NERD2,难度:中) 496
22.5 解题:是呆子?不是呆子?2 498
22.6 直接实现平衡二叉搜索树:树堆 501
22.7 练习题:反转插入排序(题目 ID:INSERTION,难度:中) 508
22.8 解题:反转插入排序 509
第23 章 优先级队列和堆 511
23.1 引言 511
23.2 堆的定义与实现方法 512
23.3 练习题:变化的中间值(题目 ID:RUNNINGMEDIAN,难度:低) 518
23.4 解题:变化的中间值 519
第24 章 区间树 521
24.1 区间树:区间相关问题解答 521
24.2 练习题:登山路(题目 ID:MORDDR,难度:中) 527
24.3 解题:登山路 528
24.4 练习题:寻根问祖(题目 ID:FAMILYTREE,难度:高) 529
24.5 解题:寻根问祖 530
24.6 树状数组:快速而简单的区间和 533
24.7 练习题:计算插入排序的时间(题目 ID:MEASURETIME,难度:中) 536
24.8 解题:计算插入排序的时间 537
第25 章 互斥集合 541
25.1 引言 541
25.2 练习题:编辑器之争(题目 ID:EDITORWARS,难度:中) 546
25.3 解题:编辑器之争 548
第26 章 字典树 553
26.1 引言 553
26.2 练习题:再见,谢谢所有的鱼(题目 ID:SOLONG,难度:中) 557
26.3 解题:再见,谢谢所有的鱼 559
26.4 利用字典树检索多重字符串 563
26.5 练习题:安全终结者(题目 ID:NH,难度:高) 569
26.6 解题:安全终结者 570
第七部分 图
第27 章 图的表示方式及定义 576
27.1 引言 576
27.2 图的应用示例 579
27.3 隐式图结构 580
27.4 图的几种表示法 581
第28 章 图的深度优先搜索 585
28.1 引言 585
28.2 练习题:古语词典(习题 ID:DICTIONARY,难度:低) 590
28.3 解题:古语词典 591
28.4 欧拉回路 594
28.5 练习题:有限单词接龙(题目 ID:WORDCHAIN,难度:低) 597
28.6 解题:有限单词接龙 598
28.7 理论背景及应用 602
28.8 练习题:安装监控摄像头(题目 ID:GALLERY,难度:中) 613
28.9 解题:安装监控摄像头 614
28.10 练习题:安排会议室(题目 ID:MEETINGROOM,难度:高) 616
28.11 解题:安排会议室 618
第29 章 图的宽度优先搜索 625
29.1 引言 625
29.2 练习题:排序游戏(题目 ID:SORTGAME,难度:中) 629
29.3 解题:排序游戏 630
29.4 练习题:儿童节(题目 ID:CHILDRENDAY,难度:高) 633
29.5 解题:儿童节 634
29.6 最短路径策略 637
29.7 练习题:汉诺塔(题目 ID:HANOI4B,难度:中) 648
29.8 解题:汉诺塔 650
第30 章 最短路径问题 653
30.1 引言 653
30.2 迪杰斯特拉最短路径算法 654
30.3 练习题:信号路由(题目 ID:ROUTING,难度:低) 661
30.4 解题:信号路由 662
30.5 练习题:消防车(题目 ID:FIRETRUCKS,难度:中) 663
30.6 解题:消防车 664
30.7 练习题:铁人N项比赛(题目 ID:NTHLON,难度:高) 665
30.8 解题:铁人N项比赛 667
30.9 贝尔曼-福特最短路径算法 669
30.10 练习题:时间旅行(题目 ID:TIMETRIP,难度:中) 674
30.11 解题:时间旅行 675
30.12 弗洛伊德多源最短路径算法 677
30.13 练习题:检查酒驾(题目 ID:DRUNKEN,难度:中) 682
30.14 解题:检查酒驾 684
30.15 练习题:竞选承诺(题目 ID:PROMISES,难度:中) 685
30.16 解题:竞选承诺 687
第31 章 最小生成树 689
31.1 引言 689
31.2 克鲁斯克尔最小生成树算法 690
31.3 普里姆最小生成树算法 694
31.4 练习题:局域网(题目 ID:LAN,难度:低) 697
31.5 解题:局域网 698
31.6 练习题:选定旅行路线(题目 ID:TPATH,难度:高) 699
31.7 解题:选定旅行路线 700
第32 章 网络流 705
32.1 引言 705
32.2 福特-富尔克森算法 706
32.3 网络建模 713
32.4 练习题:操纵比赛(题目 ID:MATCHFIX,难度:中) 715
32.5 解题:操纵比赛 717
32.6 练习题:国家项目(题目 ID:PROJECTS,难度:高) 719
32.7 解题:国家项目 720
32.8 二分图匹配 723
32.9 练习题:象(题目 ID:BISHOPS,难度:中) 729
32.10 解题:象 730
32.11 练习题:设置陷阱(题目 ID:TRAPCARD,难度:高) 732
32.12 解题:设置陷阱 734
32.13 其他学习内容 737