基本信息
编辑推荐
总结程序设计教育和竞赛培训活动中涌现的许多有价值的解题方法
从思维方式角度阐释各种类题试题的应对策略
提供大量经典的应用范例
内容简介
书籍
计算机书籍
本书对近年来程序设计教育和竞赛培训活动涌现出的许多有价值的解题方法，进行了理性、概括性和综合性的总结，从思维方式和行为特征的角度阐释了求解各种类型试题的应对策略。全书不仅充分阐释了各种解题策略的理论依据，而且还提供了大量经典的应用范例，帮助读者学会选择适宜的解题方法，掌握正确的解题策略。.
本书既是大学计算机专业算法分析课程的优秀参考书，又是大中学程序设计竞赛不可错过的培训教材。
本书特色
·本书以数据关系上的构造策略、数据统计上的二分策略、动态规划上的优化策略和计算几何问题上的应对策略为4个基本构件，介绍了40余种解题策略和重要算法。..
·各章节之间有紧密的内在联系，但彼此又相对独立。
·对每种解题策略和算法原理进行了必要的分析和证明。定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细，对其中一些复杂的解题策略和算法附加了清晰的图示，并给出了计算时间的详细分析。
·40余种解题策略都有具体的应用例证，70余道例题采用“一题多解”、“多向求解”的方式解析，并给出了由贴近自然语言、结构清晰、移植性强的类程序设计语言表述的程序题解。...
计算机书籍
本书对近年来程序设计教育和竞赛培训活动涌现出的许多有价值的解题方法，进行了理性、概括性和综合性的总结，从思维方式和行为特征的角度阐释了求解各种类型试题的应对策略。全书不仅充分阐释了各种解题策略的理论依据，而且还提供了大量经典的应用范例，帮助读者学会选择适宜的解题方法，掌握正确的解题策略。.
本书既是大学计算机专业算法分析课程的优秀参考书，又是大中学程序设计竞赛不可错过的培训教材。
本书特色
·本书以数据关系上的构造策略、数据统计上的二分策略、动态规划上的优化策略和计算几何问题上的应对策略为4个基本构件，介绍了40余种解题策略和重要算法。..
·各章节之间有紧密的内在联系，但彼此又相对独立。
·对每种解题策略和算法原理进行了必要的分析和证明。定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细，对其中一些复杂的解题策略和算法附加了清晰的图示，并给出了计算时间的详细分析。
·40余种解题策略都有具体的应用例证，70余道例题采用“一题多解”、“多向求解”的方式解析，并给出了由贴近自然语言、结构清晰、移植性强的类程序设计语言表述的程序题解。...
目录
第1章 利用树型结构解题的策略 .1
1.1 解决树的最大/最小划分问题的一般方法 1
1.1.1 解法1——二分查找最大的下界 2
1.1.2 解法2——向下移动“割” 3
1.1.3 在两种解法的基础上进一步优化 8
1.2 利用最小生成树及其扩展形式解题 11
1.2.1 利用最小生成树解题 14
1.2.2 最小k度限制生成树的思想和应用 23
1.2.3 次小生成树的思想和应用 34
1.3 利用线段树解决区间计算问题 37
1.3.1 线段树的基本概念 37
1.3.2 线段树的基本操作 39
1.3.3 应用线段树解题 40
1.4 利用伸展树优化动态集合的操作 49
1.4.1 伸展树的基本操作 50
1.4.2 伸展树的效率分析 52
1.4.3 应用伸展树解题 54
1.5 利用左偏树实现优先队列的合并 58
1.5.1 左偏树的定义和性质 58
1.5.2 左偏树的操作 59
1.1 解决树的最大/最小划分问题的一般方法 1
1.1.1 解法1——二分查找最大的下界 2
1.1.2 解法2——向下移动“割” 3
1.1.3 在两种解法的基础上进一步优化 8
1.2 利用最小生成树及其扩展形式解题 11
1.2.1 利用最小生成树解题 14
1.2.2 最小k度限制生成树的思想和应用 23
1.2.3 次小生成树的思想和应用 34
1.3 利用线段树解决区间计算问题 37
1.3.1 线段树的基本概念 37
1.3.2 线段树的基本操作 39
1.3.3 应用线段树解题 40
1.4 利用伸展树优化动态集合的操作 49
1.4.1 伸展树的基本操作 50
1.4.2 伸展树的效率分析 52
1.4.3 应用伸展树解题 54
1.5 利用左偏树实现优先队列的合并 58
1.5.1 左偏树的定义和性质 58
1.5.2 左偏树的操作 59
前言
策略是指一种总体的行为方针，而非具体方法。心理学家认为，在解决问题的过程中，如果主体所接触到的不是标准的模式化问题，那么就需要进行创造性的思维，需要有一种解题“策略”。程序设计的解题策略是指编程解题时所采取的一种基本方法，是对解题方法的概括性的、综合性的认识。.
前段时间，我们出版了ACM/ICPC竞赛的第一本教程《程序设计中常用的计算思维方式》，本书是第二本教程。我们称这两本教程为“姊妹篇”，因为思维方式和解题策略是互相联系的。从某种意义上讲，第一本教程所述的思维方式也是解题策略，而本教程所述的解题策略也渗透了思维方式。第一本教程主要是从思维方式的角度谈解题方法，而本教程侧重从行为特征的角度谈解题方法，两本教程论述的角度有所不同。
为了使读者对编程解题的策略有全面的了解，我们按照题型和知识点分类，从以下4个方面讨论解题策略。
(1) 数据关系上的构造策略。前两章分别介绍了一些特殊类型的树和图。例如，在树结构上探讨了树的划分问题、最小生成树、线段树及其扩展形式、伸展树和左偏树。利用这些特殊类型的树可优化存储结构和算法效率。另外还引进了一种可取代树结构且不失时空效率、容易编程实现的线性表——“跳跃表”；在图结构上介绍了利用网络流算法、匹配算法、分层图思想、平面图性质和偏序集模型解题的思路和方法，探讨了选择图论模型和优化算法的基本策略。第三章在丰富数据结构知识的基础上，围绕如何合理选择数据结构来优化算法的问题，阐述了构造数据关系的基本原则和方法。
(2) 数据统计上的二分策略。该策略即是在数据统计问题上，将分治思想与相应的数据结构相结合，使得统计过程尽可能模式化，以达到提高效率的目的。
(3) 动态规划上的优化策略。决定动态规划时间复杂度有3个因素：状态总数、每个状态转移的状态数、每次状态转移的时间。我们围绕这3个方面，讨论优化的思路和方法。
(4) 计算几何问题上的应对策略。几何题一般有3种类型：纯粹计算题、存在性问题和最佳值问题。我们结合实例介绍了应对每种类型试题的基本策略，其中穿插计算平面多边形、空间长方体、半平面交和最大子矩形的基本方法。
我们在ACM/ICPC竞赛的第一本教程中已经介绍了缩小搜索范围、确定搜索顺序、合理剪枝等优化策略，因此本教程略去了对搜索问题的讨论。..
我们以上述4个方面为基本构件，介绍了几十种解题策略和重要算法。对每种解题策略和算法的原理进行了必要的分析和证明，其中的定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细，并给出了计算时间的详细分析。为了帮助读者理解，其中一些复杂的解题策略和算法还附加了图示，使其过程更加具体、直观和形象，每种解题策略和算法都有具体的应用例证。全书共解析了70余道例题，大部分例题采用“一题多解”、“多向求解”的方式解析，并且尽量结合实例讲解一些常用的思维方式和解题策略，以拓宽读者的思路，使读者学会应该怎样应用算法知识解题，应该怎样选择有效的算法。
建议读者在学习各种解题策略时，注意以下3个方面的问题。
(1) 培养良好的认知结构。注重相关理论的学习，通过不断应用得以强化，形成一个脉络分明、纵横交错的知识网络。同时注意把一些常用的解题技巧和变换方法放在记忆库里，把同类问题“储存在一起”，使知识条理化。
(2) 提高解题能力。平时要多看书、多解题，从书中和编程实践中寻找再发现、再创造的契机。既要注意运算结果的正确性，也要注意知识产生的过程性（概念、法则被概括的过程，数据关系被抽象的过程，解题思维被探索的过程）。要多体会解题过程，如同反复观看电视屏幕中体育大赛的慢镜头，真正使自己学有所得。
(3) 注重解题策略的归类分析。就某个方面的解题策略而言，其形成过程是可以逻辑化、模式化的。因此，要多考虑将解题策略归类，可以选取一些具有代表性的例题，进行系统的、集中的分类解题策略训练，形成一套局部范围内的逻辑化、模式化的解题策略方案。
编程解题离不开解题方法，成功解题在很大程度上依赖于选择适宜的方法，最适宜的方法来源于正确的解题策略。
最后，由衷地感激复旦大学ACM集训队女队队长林苑。她花费了近一年的时间，为本书的大部分例题编写了题解，为算法实施提供了成功的程序范例。值得庆贺的是，在此期间，她获得了2008“长亮杯”全国大学生程序设计邀请赛、华东区TopCoder算法挑战赛二等奖、最佳女选手和最佳女队等殊荣。当我们向这位“女中豪杰”道喜时，她说，正是这本书开拓了她的算法知识，极大地提高了她的编程解题能力，感谢我们为她提供了这么好的学习机会。我们知道，书中肯定夹有许多瑕疵。但林苑同学的学习经历却道出了这样一个事实：本书虽不完美，但在编程解题的策略开发上，却提供了十分新颖和有用的信息。但愿更多的读者能够像林苑同学一样，通过本书的学习得到启示，获取灵感，拓展新知，提升能力。 ...
王建德 吴永辉
2009年8月
前段时间，我们出版了ACM/ICPC竞赛的第一本教程《程序设计中常用的计算思维方式》，本书是第二本教程。我们称这两本教程为“姊妹篇”，因为思维方式和解题策略是互相联系的。从某种意义上讲，第一本教程所述的思维方式也是解题策略，而本教程所述的解题策略也渗透了思维方式。第一本教程主要是从思维方式的角度谈解题方法，而本教程侧重从行为特征的角度谈解题方法，两本教程论述的角度有所不同。
为了使读者对编程解题的策略有全面的了解，我们按照题型和知识点分类，从以下4个方面讨论解题策略。
(1) 数据关系上的构造策略。前两章分别介绍了一些特殊类型的树和图。例如，在树结构上探讨了树的划分问题、最小生成树、线段树及其扩展形式、伸展树和左偏树。利用这些特殊类型的树可优化存储结构和算法效率。另外还引进了一种可取代树结构且不失时空效率、容易编程实现的线性表——“跳跃表”；在图结构上介绍了利用网络流算法、匹配算法、分层图思想、平面图性质和偏序集模型解题的思路和方法，探讨了选择图论模型和优化算法的基本策略。第三章在丰富数据结构知识的基础上，围绕如何合理选择数据结构来优化算法的问题，阐述了构造数据关系的基本原则和方法。
(2) 数据统计上的二分策略。该策略即是在数据统计问题上，将分治思想与相应的数据结构相结合，使得统计过程尽可能模式化，以达到提高效率的目的。
(3) 动态规划上的优化策略。决定动态规划时间复杂度有3个因素：状态总数、每个状态转移的状态数、每次状态转移的时间。我们围绕这3个方面，讨论优化的思路和方法。
(4) 计算几何问题上的应对策略。几何题一般有3种类型：纯粹计算题、存在性问题和最佳值问题。我们结合实例介绍了应对每种类型试题的基本策略，其中穿插计算平面多边形、空间长方体、半平面交和最大子矩形的基本方法。
我们在ACM/ICPC竞赛的第一本教程中已经介绍了缩小搜索范围、确定搜索顺序、合理剪枝等优化策略，因此本教程略去了对搜索问题的讨论。..
我们以上述4个方面为基本构件，介绍了几十种解题策略和重要算法。对每种解题策略和算法的原理进行了必要的分析和证明，其中的定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细，并给出了计算时间的详细分析。为了帮助读者理解，其中一些复杂的解题策略和算法还附加了图示，使其过程更加具体、直观和形象，每种解题策略和算法都有具体的应用例证。全书共解析了70余道例题，大部分例题采用“一题多解”、“多向求解”的方式解析，并且尽量结合实例讲解一些常用的思维方式和解题策略，以拓宽读者的思路，使读者学会应该怎样应用算法知识解题，应该怎样选择有效的算法。
建议读者在学习各种解题策略时，注意以下3个方面的问题。
(1) 培养良好的认知结构。注重相关理论的学习，通过不断应用得以强化，形成一个脉络分明、纵横交错的知识网络。同时注意把一些常用的解题技巧和变换方法放在记忆库里，把同类问题“储存在一起”，使知识条理化。
(2) 提高解题能力。平时要多看书、多解题，从书中和编程实践中寻找再发现、再创造的契机。既要注意运算结果的正确性，也要注意知识产生的过程性（概念、法则被概括的过程，数据关系被抽象的过程，解题思维被探索的过程）。要多体会解题过程，如同反复观看电视屏幕中体育大赛的慢镜头，真正使自己学有所得。
(3) 注重解题策略的归类分析。就某个方面的解题策略而言，其形成过程是可以逻辑化、模式化的。因此，要多考虑将解题策略归类，可以选取一些具有代表性的例题，进行系统的、集中的分类解题策略训练，形成一套局部范围内的逻辑化、模式化的解题策略方案。
编程解题离不开解题方法，成功解题在很大程度上依赖于选择适宜的方法，最适宜的方法来源于正确的解题策略。
最后，由衷地感激复旦大学ACM集训队女队队长林苑。她花费了近一年的时间，为本书的大部分例题编写了题解，为算法实施提供了成功的程序范例。值得庆贺的是，在此期间，她获得了2008“长亮杯”全国大学生程序设计邀请赛、华东区TopCoder算法挑战赛二等奖、最佳女选手和最佳女队等殊荣。当我们向这位“女中豪杰”道喜时，她说，正是这本书开拓了她的算法知识，极大地提高了她的编程解题能力，感谢我们为她提供了这么好的学习机会。我们知道，书中肯定夹有许多瑕疵。但林苑同学的学习经历却道出了这样一个事实：本书虽不完美，但在编程解题的策略开发上，却提供了十分新颖和有用的信息。但愿更多的读者能够像林苑同学一样，通过本书的学习得到启示，获取灵感，拓展新知，提升能力。 ...
王建德 吴永辉
2009年8月
