算法问题实战策略

第一部分 开始解决问题

第1 章 解决问题与程序设计竞赛4

1.1 引言4

1.2 程序设计竞赛4

1.3 阅读本书的方法7

第一部分 开始解决问题

第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 解题：合并LIS164

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 解题：Genius254

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 解题：是呆子？不是呆子？2498

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

参加程序设计竞赛是培养解决问题能力的最佳途径。在目前各式各样的程序设计竞赛当中，本书选取设计要求较少、有运算时间限制、比拼快速设计能力的竞赛。此处的设计要求不同于实际开发中的要求，而是以“读入某个值，然后计算出某个值”的形式给出。 下面针对未接触过程序设计竞赛的读者举个简单的示例。 题目：摇滚音乐节（难度：低，题目ID：FESTIVAL） 要租用一个大的演出场地举办摇滚音乐节。这次音乐节将...

(查看全部试读)