《算法问题实战策略》收录程序设计竞赛经典试题，在解题过程中讲解各种算法设计技巧和数据结构，培养读者的解题能力。读者可亲自编写各章习题程序并获得评分，所有示例均附有解题过程及详细说明。

　　具宗万 ，
　　毕业于韩国延世大学计算机科学系，曾在innotive公司和NHN公司任软件工程师，现在芝加哥高频交易（HFT）公司从事算法交易开发工作。2007年开始参与运营韩国程序设计竞赛参赛者网络社交平台algospot。
　　获奖经历
　　2002年、2003年 韩国大学生程序设计竞赛 金奖
　　2003年、2004年 世界大学生程序设计竞赛 入围决赛
　　2004年、2006年、2008年 Google Code Jam 入围决赛
　　2007年 Top Coder Open 亚军，2006年 入围决赛
　　2008年、2009年 Java算法竞赛 冠军

　　《算法问题实战策略》收录程序设计竞赛经典试题，在解题过程中讲解各种算法设计技巧和数据结构，培养读者的解题能力。读者可亲自编写各章习题程序并获得评分，所有示例均附有解题过程及详细说明。 本书主要内容 第一部分 开始解决问题 第二部分 算法分析 第三部分 算法设计范式 第四部分 一些著名的算法 第五部分 基本数据结构 第六部分 树 第七部分 图。
　　《算法问题实战策略》是学习解题技巧时必不可少的经典，不仅适合准备参赛的人阅读，书中对现有算法的检验和优化后的代码等，都对实际业务有非常大的帮助。本书作者是算法竞赛领域的人士，他利用自己多年积累的经验，通过多个解题示例帮助大家轻松学习算法。

　　★本书是学习解题技巧时必不可少的经典。
　　——刘元和（KAIST，2009年韩国大学生程序设计竞赛冠军）
　　 
　　★本书不仅适合准备参赛的人阅读，书中对现有算法的检验和优化后的代码等，都对实际业务有非常大的帮助。
　　——崔如民（EA Korea Lead Software工程师，2005年世界大学生程序设计竞赛第13名）
　　 
　　★我有14年程序设计竞赛参赛经验，如果12年前看到这本书就好了。
　　——李后然（斯坦福大学，国际信息学奥林匹克竞赛冠军）
　　 
　　★本书作者是算法竞赛领域的人士，看到他利用自己多年积累的经验，通过多个解题示例帮助大家轻松学习算法，我感到非常高兴。
　　——吴时英（卡耐基梅隆大学，国际信息学奥林匹克竞赛亚军）

第一部分开始解决问题
第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解题：Quantization170
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解题：盖游戏板2299
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解题：密码486357
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