本书内容涵盖计算机程序设计中常用的算法策略，包括利用树形结构的解题策略，利用图形（网状）结构的解题策略，数据关系上的构造策略，数据统计上的二分策略，动态规划上的优化策略，计算几何上的应对策略。本书适合作为高校计算机及相关专业数据结构及算法课程的实践教材和教学辅助材料。
本书用大量程序设计竞赛的经典试题作为范例，结合程序设计的基础知识，以问题驱动和启发式引导为主要方式，从七个方面详细介绍了49种解题策略和重要算法，培养读者对问题的认知能力和编程解题的能力。本书还提供了试题的英文原版描述和大部分试题的测试数据等资料，详细内容可从华章网站（www.hzbook.com）下载。
本书特点：
从国内外多年程序设计竞赛中精选100道经典试题，启发性地引出相应的解题策略，不仅有知识要点阐述、详尽的试题解析、相应参考程序，还使用大量图表增加直观性和可读性，方便读者的学习和实践。
提供了试题的原版描述、测试数据和解答程序作为参考，读者可以通过学习培养良好的认知结构，提高编程解题能力。
书中的经典试题可用于程序设计相关课程的教学与实践，还可用于辅导学生进行程序设计竞赛的专项训练。
策略即计策和谋略，指一种总体的行为方针和行事方法，即一种可以实现目标的方案集合，而非纠缠于细枝末节的雕虫小技。程序设计的解题策略指的是编程解题过程中所采取的一种基本方法，是对解题方法的综合性、智能性和个性化的认识。尤其是当面对非标准、非模式化的问题时，就更需要发挥创造性思维，求索应对策略和解题艺术。正如古人所言“术谋之人以思谟为度，故能成策畧之奇，而不识遵法之良”。
对于程序设计竞赛选手的培养，教师应注重在两个方面系统地训练选手：①程序设计竞赛的知识体系；②程序设计的解题策略。
对于程序设计竞赛的知识体系，可以用“算法+数据结构=程序”这一著名公式来概括。为此，这两年我们先后在机械工业出版社出版了两本专著（《数据结构编程实验》和《算法设计编程实验》），其中《数据结构编程实验》还由中国台湾碁峰出版社以《提升程式設計的資料結構力：國際程式設計競賽之資料結構原理、題型、解題技巧與重點解析》为书名出版。
上述两本书和本书一起，构成了对程序设计竞赛选手进行“程序设计竞赛的知识体系”和“程序设计的解题策略”系统训练的一个完整系列，本系列也可以作为大学的程序设计实验课程的系列教材。这三本书包含的知识结构和实验选题没有重复且互相联系：前两本书在系统讲述程序设计竞赛知识体系结构的同时，也涉及一些初浅的解题策略，但主要是从知识的角度谈解题方法；而本书所讲述的解题策略虽是在深入数据结构和算法设计知识的基础上展开，但侧重从行为特征的角度谈解题方法。所以，这三本书的知识层次和论述角度有区别、有联系、有递进关系。
为了使读者对编程解题的策略有一个全面了解，我们将这些年国际、国内程序设计竞赛的经典例题进行分门别类，从七个大的方面讨论解题策略。
（1）利用树型数据关系解题的七种基本策略
利用划分树求解整数区间内第k大的值；利用最小生成树原理和拓展形式（最小k度限制生成树和次小生成树）求解带权无向连通图中最佳边权和的生成树；利用一维线段树计算和维护区间的最值（最大或最小值）和总量；利用两种改进型的二叉查找树——伸展树和红黑树来优化动态集合的操作；利用动态树计算和维护一个带权森林；利用左偏树实现优先队列的合并；利用跳跃表实现树的功能。
（2）利用图型数据关系解题的五种基本策略
将图论问题转化成网络流的计算；将一般图转换成二分图，利用匹配算法提高计算效率；通过分层图思想将干扰因素细化为若干状态，通过层的连接将状态联系起来，最终找到算法；从信息原型中挖掘出平面图特征，洞悉有向边蕴含的偏序关系，清晰思路、简化算法；从挖掘和利用图论模型性质的三个思考角度出发，提出选择图论模型和优化算法的三种基本策略（“定义法”、“分析法”、“综合法”）。
（3）数据关系上的构造的三种基本策略
选择逻辑结构的两个基本原则（利用“可直接使用”的信息和不记录“无用”的信息）；选择存储结构的基本思路；科学组合多种数据结构的两种基本方法（并联和嵌套）。
（4）利用二分法进行数据统计的四种策略
一维或二维线段树；动态统计子序列和的树状数组与用于RMQ问题的倍增数组；静态二叉排序树；虚二叉树。
（5）动态规划上的优化的四种策略
从三个角度（减少状态总数、每个状态决策数和每状态转移时间）讨论动态规划（DP）的优化策略；应对连通性问题的DP策略——基于状态压缩的插头DP。
（6）应对计算几何的五种基本策略
用于求解最远、最近或第k近距离问题中的模拟退火算法；用于求解凸性函数极值问题的三分法；应用于复合属性图形计算的剖分优化思想；解决最大子矩形问题的极大化思想；在求解综合性、扩展性几何问题中合理组合基本几何运算的方法。
（7）应对博弈类问题的四种基本策略
动态博弈的思想方法；三个基础博弈（巴什博弈、威佐夫博弈和尼姆博弈）及其扩展形式；在组合游戏中使用SG函数；使用数学工具surreal number应对不平等的组合游戏。
我们以上述七个方面为基本构件，介绍了49种解题策略和重要算法，如下表所示：
序号解题策略和重要算法所在章节
1划分树 第1章 利用树型数据关系的解题策略
2最优比率生成树
3最小k度限制生成树
4次小生成树
5线段树
6伸展树
7红黑树
8动态树
9左偏树
10跳跃表
11Dinic算法 第2章 利用图型数据关系的解题策略
12求容量有上下界的最大流问题
13计算最小费用最大流
14计算二分图的最大匹配
15计算二分图最佳匹配
16利用分层图思想
17偏序集
18优化图论模型的三种方法
19充分利用“可直接使用”的信息 第3章 数据关系上的构造策略
20不记录“无用”的信息
21合理采用顺序存储结构
22必要时采用链式存储结构
23数据结构的“并联”
24数据结构的“嵌套”
25线段树 第4章 数据统计上的二分策略
26树状数组
27倍增算法
28静态二叉排序树
29虚二叉树
（续）序号解题策略和重要算法所在章节
30DP中减少状态总数的基本策略 第5章 动态规划上的优化策略
31DP中减少每个状态决策数的基本策略
32DP中减少状态转移时间的基本策略
33基于状态压缩的插头DP
34模拟退火算法
35三分法 第6章 计算几何上的应对策略
36圆重合其他几何图形时的剖分策略
37三角剖分
38梯形剖分
39矩形切割思想
40利用极大化思想解决最大子矩形问题
41合理组合基本几何运算
42利用动态博弈思想判断输赢 第7章 博弈类问题的应对策略
43巴什博弈
44威佐夫博弈
45尼姆博弈
46k倍动态减法游戏
47尼姆博弈的四种扩展形式
48SG函数
49使用surreal number应对组合游戏
这些策略和算法有的源于程序设计领域的经典成果，但更多的是源于复旦大学程序设计竞赛队的成员在长期编程实践中积淀的策略经验。我们对此进行了认真的整理和提炼，使之由默会知识变成明言知识。书中所述的每个解题策略和算法原理都有必要的分析和证明，定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细，并给出了计算时间复杂度的详细分析。为了帮助读者理解，对其中一些复杂的解题策略和算法附加了图示，使其过程更加具体、直观和形象。
“程序设计解题策略”是一门“实践出真知”的课程，需要大量引入案例教学，通过模拟或者重现现实生活中的一些场景，让读者置身于问题情境之中，通过思考、讨论和上机编程来学习解题策略。为此，我们在浩如烟海的各类程序设计竞赛试题中精选出100道试题作为实验范例，启发性地引出相应的解题策略，为读者学习解题策略的相关知识创设丰富有趣的问题背景。每个实验范例不仅有知识要点阐述和详尽的试题解析，而且还给出了写有详细注释的参考程序；每个常用的解题策略都以经典模型为支撑，每个定理概念都有详尽的说明和推导，并使用大量图表增加直观性和可读性。本书尽力将经典模型推广到具有相同性质的一类问题，让读者熟悉一个经典模型就相当于掌握了解决一类问题的方法。有时还有意在经典模型外加入其他因素，引导读者对被套用的经典模型进行适当修改，加入独特的属性，或者运用已知模型或方法来分析信息原型的属性，在此基础上创造出具有新意的模型或方法。为了让读者能够检验自编程序的正确性和效率，每道题都注明了试题来源和在线测试网址。另外，可登录华章网站（www.hzbook.com）下载所有试题的原版描述和大部分试题的测试数据等资料。
本书试题的在线测试地址主要有：
在线评测系统 简称 网址
北京大学在线评测系统 POJ http://poj.org/
浙江大学在线评测系统 ZOJ http://acm.zju.edu.cn/onlinejudge/
UVA在线评测系统 UVA http://uva.onlinejudge.org/
http://livearchive.onlinejudge.org/
Ural在线评测系统 Ural http://acm.timus.ru/
SGU在线评测系统 SGU http://acm.sgu.ru/
杭州电子科技大学在线评测系统 HDOJ http://acm.hdu.edu.cn/
编程解题离不开建模和解题方法，解题的成功取决于选择正确的数学模型和解题方法，而数学模型和解题方法的正确性源于采用适宜的解题策略。建议读者在学习各种解题策略时，注意以下三个方面的问题。
1）培养良好的认知结构。注重相关理论的学习，并通过不断应用来强化理论知识，形成一个脉络分明、纵横交错的知识网络。同时注意把一些常用的解题技巧和变换方法放在记忆库里，把同类问题“存储在一起”，使知识条理化。
2）提高解题能力。平时要多看书和多解题，从书中和编程实践中寻找再发现、再创造的契机。既要注意运算结果的正确性，也要注意知识产生的过程性（概念、法则被概括的过程，数据关系被抽象的过程，解题策略被探索的过程）。要细化书本知识，如同电视屏幕中体育大赛慢镜头式的分解，真正使自己学有所得。
3）注重解题策略的归类分析。就某个方面的解题策略而言，其形成过程是可以逻辑化、模式化的。因此，要多考虑将解题策略归类，可以选取一些具有代表性的例题，进行系统的、集中的分类解题策略训练，形成一套局部范围内的逻辑化、模式化的解题策略方案。
需要说明的是，张一博、舒天民、王禹、金阳华等同学精心编写了所有程序，每道程序都通过了严格的测试验证，多次修改、精益求精，特别是张一博和王禹同学还对本书的结构和内容提出了系统的、建设性的建议。这几位同学为本书的出版付出了辛勤劳动，做出了不可或缺的贡献，在此向他们表示由衷的感谢。另外，衷心感谢杭州电子科技大学刘春英老师为本书的部分试题在HDOJ上提供了在线测试平台；衷心感谢中国台湾的老师和同学在使用本书书稿过程中提出的宝贵意见和建议。
由于时间和水平所限，书中肯定夹杂了不少缺点和错误，表述不当和笔误更是在所难免，热切欢迎学术界同仁或读者赐正。如果你在阅读中发现了问题，请通过书信或电子邮件告诉我们，以便及时整理成勘误表放在本书的网站上，供广大读者查询更正。我们更期望读者对本书提出建设性意见，以便再版时改进。我们的联系方式如下。
通信地址：上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉
邮编：200433
Email:yhwu@fudan.edu.cn
吴永辉 王建德
2014年10月
计算机\程序设计
本书用大量程序设计竞赛的经典试题作为实验范例，结合程序编程设计的基础知识，以问题驱动和启发式引导为主要方式，从七个方面详细介绍了49种解题策略和重要算法，培养读者对问题的认知能力和编程解题的能力。本书还提供了试题的英文原版描述和大部分试题的测试数据等资料，详细内容可参见华章网站（www.hzbook.com）。
本书特点：
1 从国内外多年程序设计竞赛中精选100道经典试题，启发性地引出相应的解题策略，不仅有知识要点阐述、详尽的试题解析、相应参考程序，还使用大量图表增加直观性和可读性，方便读者的学习和实践。
2 提供了试题的原版描述、测试数据和解答程序作为参考，读者可以通过学习培养良好的认知结构，提高编程解题能力。
3 书中的经典试题可用于程序设计相关课程的教学与实践，还可用于辅导学生进行程序设计竞赛的专项训练。
吴永辉 王建德 编著：暂无简介
前言
第1章 利用树型数据关系的解题策略1
1.1 利用划分树求解整数区间内第k大的值1
1.1.1 离线构建整个查询区间的划分树2
1.1.2 在划分树上查询子区间［l，r］中第k大的数3
1.1.3 应用划分树解题4
1.2 利用最小生成树及其扩展形式解题8
1.2.1 最小生成树的思想和应用8
1.2.2 最优比率生成树的思想和应用23
1.2.3 最小k度限制生成树的思想和应用28
1.2.4 次小生成树的思想和应用35
1.3 利用线段树解决区间计算问题42
1.3.1 线段树的基本概念42
1.3.2 线段树的基本操作和拓展43
1.3.3 应用线段树解题46
1.4 利用改进型的二叉查找树优化动态集合的操作56
1.4.1 改进型1：伸展树57
1.4.2 改进型2：红黑树60
1.4.3 应用改进型的二叉查找树解题64
1.5 利用动态树维护森林的连通性81
1.5.1 动态树的问题背景81
1.5.2 Link-Cut Tree的定义82
1.5.3 Link-Cut Tree的基本操作和时间复杂度分析82
1.5.4 应用动态树解题85
1.6 利用左偏树实现优先队列的合并95
1.6.1 左偏树的定义和性质95
1.6.2 左偏树的操作97
1.6.3 应用左偏树解题103
1.7 利用跳跃表替代树结构106
1.7.1 跳跃表的基本概念107
1.7.2 跳跃表的基本操作107
1.7.3 跳跃表的效率分析109
1.7.4 应用跳跃表解题111
本章小结126
第2章 利用图型数据关系的解题策略128
2.1 利用网络流算法解题128
2.1.1 网络、流与割的概念128
2.1.2 利用Dinic算法计算最大流132
2.1.3 求容量有上下界的最大流问题145
2.1.4 计算最小费用最大流155
2.2 利用图的匹配算法解题161
2.2.1 匹配的基本概念161
2.2.2 计算二分图的最大匹配166
2.2.3 计算二分图最佳匹配的KM算法167
2.2.4 利用一一对应的匹配性质转化问题的实验范例179
2.3 利用分层图思想解题191
2.3.1 利用分层图思想化未知为已知191
2.3.2 利用分层图思想优化算法的实验范例195
2.4 利用平面图性质解题199
2.4.1 平面图的基本概念199
2.4.2 平面图的实验范例200
2.4.3 偏序集的基本概念210
2.4.4 偏序集的实验范例211
2.5 在充分挖掘和利用图论模型性质的基础上优化算法216
2.5.1 优化图论模型的三种方法216
2.5.2 三种优化方法的实验范例217
本章小结224
第3章 数据关系上的构造策略226
3.1 选择数据逻辑结构的基本原则226
3.1.1 充分利用“可直接使用”的信息226
3.1.2 不记录“无用”的信息230
3.2 选择数据存储结构的基本方法235
3.2.1 合理采用顺序存储结构235
3.2.2 必要时采用链式存储结构239
3.3 科学组合多种数据结构245
3.3.1 数据结构的“并联”246
3.3.2 数据结构的“嵌套”252
本章小结259
第4章 数据统计上的二分策略260
4.1 利用线段树统计数据260
4.1.1 利用线段树解决一维数据序列的统计问题260
4.1.2 利用线段树解决二维数据区的统计问题264
4.2 基于数组统计方法268
4.2.1 利用树状数组解决动态统计子序列和问题269
4.2.2 采用倍增算法求解RMQ问题274
4.3 在静态二叉排序树上统计数据284
4.3.1 建立静态二叉排序树285
4.3.2 在静态二叉排序树上进行统计285
4.3.3 静态二叉排序树的应用287
4.4 在虚二叉树上统计数据291
本章小结297
第5章 动态规划上的优化策略298
5.1 减少状态总数的基本策略298
5.1.1 改进状态表示298
5.1.2 选择适当的DP方向302
5.2 减少每个状态决策数的基本策略307
5.2.1 利用最优决策的单调性307
5.2.2 剪枝优化315
5.2.3 合理组织状态327
5.2.4 细化状态转移335
5.3 减少状态转移时间的基本策略340
5.3.1 减少决策时间340
5.3.2 减少计算递推式的时间349
5.4 应对连通性问题的DP策略——基于状态压缩的插头DP353
5.4.1 插头DP的一般模式353
5.4.2 用于简单路径问题上的插头DP361
5.4.3 用于棋盘染色问题上的插头DP365
5.4.4 插头DP中的剪枝优化373
本章小结380
第6章 计算几何上的应对策略382
6.1 用于求解距离问题的模拟退火算法382
6.1.1 模拟退火算法的由来382
6.1.2 模拟退火算法的实现383
6.1.3 模拟退火算法的应用范例384
6.2 用于求解凸性函数极值问题的三分法393
6.2.1 三分法的基本思想393
6.2.2 三分法的应用范例394
6.3 使用剖分优化应对复合属性的几何图形398
6.3.1 圆重合其他几何图形时的剖分策略398
6.3.2 使用三角剖分思想计算几何图形面积413
6.3.3 使用梯形剖分计算多边形面积420
6.3.4 利用矩形切割思想进行几何计算和数据统计425
6.4 利用极大化思想解决最大子矩形问题432
6.4.1 与极大化思想有关的概念432
6.4.2 寻找最大子矩形的两种常用算法432
6.4.3 最大子矩形问题的推广436
6.4.4 利用极大化思想解决最大子矩形问题的范例437
6.5 在求解综合性、扩展性几何问题中合理组合基本几何运算444
6.5.1 在复杂的综合性试题中合理组合基本几何运算445
6.5.2 在空间几何计算中合理组合基本几何运算455
本章小结461
第7章 博弈类问题的应对策略462
7.1 利用动态博弈思想判断输赢462
7.2 基础性博弈中的对抗策略467
7.2.1 巴什博弈468
7.2.2 威佐夫博弈469
7.2.3 尼姆博弈471
7.3 基础性博弈扩展形式中的对抗策略477
7.3.1 巴什博弈的扩展——k倍动态减法游戏477
7.3.2 尼姆博弈的四种扩展形式481
7.4 使用SG函数应对一类组合游戏485
7.4.1 SG-组合游戏问题的特殊性质485
7.4.2 “翻硬币”游戏487
7.4.3 多图游戏491
7.5 使用数学工具surreal number应对不平等的组合游戏498
7.5.1 数学工具surreal number498
7.5.2 surreal number在组合游戏上的应用500
本章小结503
