程序设计中常用的解题策略-世界大学生程序设计竞赛

出版时间：2012-7  出版社：中国铁道出版社  作者：吴文虎,王建德  页数：213  
Tag标签：无  

内容概要

　　《世界大学程序设计竞赛（ACM/ICPC）高级教程（第2册）：程序设计中常用的解题策略》是针对世界大学生程序设计竞赛（ACM/ICPC）而编写的第二本参考书。　　ACM/ICPC是大学生智力与计算机解题能力的竞赛，是世界公认的最具影响力的、规模最大的国际顶级赛事，被称为大学生的信息学奥林匹克。　　第一册主要介绍程序设计中解题的常用思维方式。《世界大学程序设计竞赛（ACM/ICPC）高级教程（第2册）：程序设计中常用的解题策略》是第一册的继续，只是换了一个角度，分4方面介绍解题策略：数据关系上的构造策略；数据统计上的二分策略；动态规划中的优化策略；计算几何题的应对策略。　　《世界大学程序设计竞赛（ACM/ICPC）高级教程（第2册）：程序设计中常用的解题策略》面向参加世界大学生程序设计竞赛（ACM/ICPC）的高等院校学生，也可作为程序设计爱好者的参考用书。

作者简介

吴文虎教授1955年—1961年分别就读于清华大学电机工程系及自动控制系，现为计算机系教授、博士生导师，主要研究方向包括语音识别及语言理解、语音合成、语音信号数字处理等。吴教授学术水平精湛、教学水平高超、教学经验丰富，多年来用对学生无私的爱诠释了最好的师恩师德。他于1997年获清华大学优秀教学成果特等奖，1998年获“全国优秀教师一等奖”，1999年获国家科技部(原国家科委)授予的“全国科学普及先进个人奖”，1999年荣获“首都劳动奖章”，2001年获“全国师德先进个人奖”，2001年、2004年获北京市高等教育教学优秀成果一等奖，2003年为本科生讲授的“程序设计基础”课程被列为教育部首批“国家级精品课”，2004年获中国计算机学会颁发的“杰出贡献奖”，2006年获北京市高等教育教学名师奖；吴教授深受清华学子的爱戴，2003年获清华大学教书育人奖，2005年获清华大学第八届“良师益友”荣誉称号，2008年被清华大学学生会评为第一届“我最喜爱的教师”。    从1989年至今，吴教授作为总教练和领队，曾15次带领中国队参加国际信息学奥林匹克竞赛，中国队累计获金牌51块，届届名列前茅，2002年获信息学奥林匹克国际委员会颁发的“特别贡献奖”。1997年—2008年，吴教授连续13年指导清华大学的学生进入ACM世界大学生程序设计大赛总决赛，多次获金牌、银牌，并于2009年被大赛组委会授予“杰出教练奖”。

书籍目录

第7章 利用树状结构解题的策略 7.1 解决树的最大一最小划分问题的一般方法 7.2 利用最小生成树及其扩展形式解题 7.2.1 利用最小生成树解题 7.2.2最小k度限制生成树的思想和应用 7.2.3 次小生成树的思想和应用 7.3 利用线段树解决区间计算问题 7.3.1线段树的基本概念 7.3.2线段树的基本操作 7.3.3应用线段树解题 7.4利用伸展树优化动态集合的操作 7.4.1伸展树的基本操作 7.4.2伸展树的效率分析 7.4.3应用伸展树解题 7.5 利用左偏树实现优先队列的合并 7.5.1左偏树的定义和性质 7.5.2左偏树的操作 7.5.3应用左偏树解题 7.6利用“跳跃表”替代树结构 7.6.1跳跃表的概况 7.6.2跳跃表的基本操作 7.6.3 跳跃表的效率分析 7.6.4应用跳跃表解题 小结 第8章 利用图形（网状）结构解题的策略 8.1 利用网络流算法解题 8.1.1 网络与流的概念 8.1.2最大流算法的核心——增广路径 8.1.3通过求最大流计算最小割切 8.1.4求容量有上下界的最大流问题 8.1.5 网络流的应用 8.2利用图的匹配算法解题 8.2.1匹配的基本概念 8.2.2计算二分图匹配的方法 8.2.3 利用一一对应的匹配性质转化问题 8.2.4优化匹配算法 8.3利用“分层图思想”解题 8.3.1 利用“分层图思想”构建图论模型 8.3.2 利用“分层图思想”优化算法 8.4利用平面图性质解题 8.4.1平面图的概念 8.4.2平面图的应用实例 8.5 正确选择图论模型，优化图的运算 8.5.1 正确选择图论模型 8.5.2在充分挖掘和利用图论模型性质的基础上优化算法 小结 第9章 数据关系上的构造策略 9.1 选择数据逻辑结构的基本原则 9.1.1 充分利用“可直接使用”的信息 9.1.2不记录“无用”信息 9.2选择数据存储结构的基本方法 9.2.1 合理采用顺序存储结构 9.2.2必要时采用链式存储结构 9.3 科学组合多种数据结构 小结 第10章 数据统计上的二分策略 10.1 利用线段树统计数据 10.2一种解决动态统计的静态方法 10.2.1 讨论一维序列的求和问题 10.2.2将一维序列的求和问题推广至二维 10.3 在静态二叉排序树上统计数据 10.3.1 建立静态二叉排序树 10.3.2在静态二叉排序树上进行统计 10.3.3 静态二叉排序树的应用 10.4在虚二叉树上统计数据 小结 第11章 动态规划上的优化策略 11.1 减少状态总数的基本策略 11.1.1改进状态表示 11.1.2选择适当的规划方向 11.2减少每个状态决策数的基本策略 11.2.1 利用最优决策的单调性 11.2.2优化决策量 11.2.3合理组织状态 11.2.4细化状态转移 11.3 减少状态转移时间的基本策略 11.3.1减少决策时间 11.3.2减少计算递推式的时间 小结 第12章 计算几何上的应对策略 12.1应对纯粹计算题的策略探讨 12.1.1 利用二重二叉树计算长方体的体积并 12.1.2 利用多维线段树和矩形切割思想解决平面统计或空间统计问题 12.1.3利用极大化思想解决最大子矩形问题 12.1.4利用半平面交的算法计算凸多边形 12.2应对存在性问题的策略探讨 12.2.1 直接通过几何计算求解 12.2.2转换几何模型求解 12.3 应对最佳值问题的策略探讨 12.3.1 采用高效的几何模型 12.3.2采用极限法 12.3.3采用逼近最佳解的近似算法 小结

章节摘录

版权页：   插图：   以上介绍了解决树的最大一最小划分问题的两种解法，它们通过不同的方式思考问题，从而得到了不同的算法：解法1主要应用了问题转化的思想，将原问题转化为容易解决的问题，在给定下界时如何划分最多子树，如果可以解决这个问题，再通过二分查找下界求得原问题的解。这种算法的目光聚焦在结点的权值上，实现简单，时间效率也不错；而解法2则从另一个角度看问题，将目光集中在分割子树的“割”上面，从而得到了一个复杂度不依赖于结点权值范围的算法，其中起关键作用的是划分问的“上方”关系，这种关系实际上是一种“序”的思想。利用“序”简化问题、建立高效模型是程序设计中一种典型的优化方法。 虽然有了划分树的两种解法，但我们并不满足，还希望能够将算法扩展一下，使它的适用范围更加广泛。 优化方法1：扩展权函数 首先来看一下权函数方面，由“每棵子树的权被定义为子树中所有结点的权之和”想到，对于一些其他的权函数，例如一棵子树中结点权的最大值、子树的直径（子树结点问路径长度的最大值）等，这个算法是不是依然适用呢？我们发现，在解法2的证明过程中，只有②和③的证明用到了子树的权函数，而通过更加深入观察发现，证明中只是利用了权函数的一个性质： 权函数的性质：若T是T的任意一棵子树，则必然有W（T）≥W（T），其中W（T）表示树T中结点的权值和。 也就是说，只要权函数满足这个条件，这个证明就是正确的，这个算法也就是可行的。于是，对于满足特定条件的一类问题都找到了一种通用的解法，这也显示出该算法很强的可扩展性。 有了对权函数的扩展，接下来便想到了对问题的扩展。例如，将树划分为k棵子树，使得子树的最大值最小，或是最大值与最小值的差最小等问题，我们是不是也可以用原算法求解呢？事实证明，单纯地照搬是行不通的，因为算法有自身的特点，不可能适用于所有问题，但解决问题的思路却是可以借鉴的。在解决与这一类型有关的问题时，或许可以改变移动的规则，或修改一下“上方”的定义，从而设计出符合题目特点的算法，这些问题可引起读者思考。 优化方法2：用解法1优化解法2 在解法2中，初始状态是将k—1个割放在与根相连的唯一一条边上得到的，这样做的好处是一定可以保证它在某个最优划分的上方。可是由这个初始状态移动到最优状态往往需要很多步的移动，那么有没有更好的初始状态呢？我们想到了解法1，如果把下界设为树中节点的权和/k—1，则划分出来的子树数一定不超过k—1，我们将剩余的割都放在与根相连的那条边上。可以证明，这个划分状态一定是在某个最优划分的上方的，而由它达到最优状态所需要移动的步数却减少了。于是，只需要一个线性的预处理，便得到了一种更好的初始状态。这样，解法l和解法2便巧妙地结合在一起了。

编辑推荐

《世界大学生程序设计竞赛(ACM/ICPC)高级教程(第2册):程序设计中常用的解题策略》面向参加世界大学生程序设计竞赛（ACM/ICPC）的高等院校学生，也可以作为程序设计爱好者的参考用书。

用户评论 (总计4条)

•   看过第一本，觉得写得和好，当时没有第二本，现在终于有了，刚刚到手，很不错
•   用pascal写的，虽然算法写得不错。
•   竟然是pascal写的，虽然算法静得不错
•   适合对基础算法和数据结构知识熟练掌握的人使用，主要针对竞赛中的实际问题的解决思路上进行分析