世界大学生程序设计竞赛（ACM/ICPC）高级教程（第二册）程序设计中常用的解题策略
书号：9787113146054 套系名称：无
作者：吴文虎 王建德 出版日期：2012-07-01
定价：48.00 页码 / 开本：224 /16
策划编辑：秦绪好 责任编辑：翟玉峰
适用专业：无 适用层次：高等学校
最新印刷时间：
本书是针对世界大学生程序设计竞赛（ACM/ICPC）而编写的第二本参考书。ACM/ICPC是大学生智力与计算机解题能力的竞赛，是世界公认的最具影响力的、规模最大的国际顶级赛事，被称为大学生的信息学奥林匹克。
第一册主要介绍程序设计中解题的常用思维方式。本书是第一册的继续，只是换了一个角度，分4方面介绍解题策略：数据关系上的构造策略；数据统计上的二分策略；动态规划中的优化策略；计算几何题的应对策略。
本书面向参加世界大学生程序设计竞赛（ACM/ICPC）的高等院校学生，也可作为程序设计爱好者的参考用书。ACM/ICPC是国际计算机协会（Association for Computing Machinery）组织的国际大学生程序设计竞赛（International Collegiate Programming Contest）的英文简称。这项赛事始于1976年的计算机学科竞赛，随着信息科技的迅猛发展，世界各国对计算机科学教育重要性的认识日益加深，该项赛事已经演变成为目前规模最大和最具影响力的全球性的高等学校之间的盛会。
这项一年一届的赛事从当年的9月开始，先进行各大洲地区性的预选赛，从近2 000所大学的8 000多个参赛队的预选赛中选拔出100个左右的队于第二年的春季参加全球总决赛。比赛强调团队精神与合作协同攻关能力，3个学生组成一个队，共用一台计算机，一起解决10道左右的难题。这些题目涉及Direct（简单题）、Computational Geometry（计算几何）、Number Theory（数论）、Combinatorics（组合数学）、Search Techniques（搜索技术）、Dynamic Programming（动态规划）、Graph Theory（图论）和Other（其他）。可使用的计算机编程语言为：C++、C、Java和Pascal。但final赛只可以使用C或C++。
赛题特点如下：
① 有实际背景，趣味性和实用性较强。
② 考查的知识范围比较全面（基础的与深层次的题目都有）。
③ 层次性较好，10道题中会有不同水平的题。
④ 灵活、新颖。绝大部分没有固定解法，留有广阔的思维空间，有益于培养学生的创造能力。
从历年的赛题看，难度很大，涉及数学、物理、电子学、计算机科学等多种学科，特别是要用到数理逻辑、图论、集合论、组合数学、概率论、计算几何等数学知识和计算机的高效算法。在比赛现场的审题建模、构思算法、编码调试、自我测试、快速纠错的全面能力，对每一个参赛队而言都是巨大的挑战。近年，尽管已是能够进入决赛圈的队，有的也只能解对11道赛题中的两三道。
ACM/ICPC这项国际顶级赛事比的是智力和计算机综合解题能力的高低，赛场是大学生展示水平与才华的大舞台，是著名的高等学府计算机教育成果的直接体现，同时也是IT企业与世界顶尖计算机人才对话的最佳机会。因而吸引了越来越多的高校参赛，使得参赛队伍的水平上升很快，赛题的难度也在不断提高。
中国的大学参加这项赛事已有15年的历史，现在已有100多所学校的几百支队伍参加亚洲区的预选赛，每年都会有10多所学校进军总决赛，成绩是很好的。
ACM/ICPC赛事属于因材施教活动，它是和国际接轨的，学生参加比赛是一个学习、观摩、交流、开阔眼界、考验心理素养和提高竞争能力的过程。特别是在与编程高手过招的时候，可以把知识运用的综合性、灵活性和探索性水平发挥到极致，体验和感受数学思维和算法艺术之美，在实践中提升科学思维能力。
科学思维能力的提高是学生今后成就事业的一个非常重要的因素，我们希望这本书能够对读者有所帮助。
王建德老师与我愉快地合作了20年，在本书的策划和写作中，王建德老师一如既往地花费了许多心血，总结出十分精彩的观点和思路。
清华大学的一些选手曾试用和验证过原稿中的某些算法，邓俊辉博士、徐明星博士、邬晓钧博士和朱全民老师对原稿提出过宝贵意见，在此一并感谢。
2009年本书第一册（共6章，即第1～6章）出版后，得到许多读者的关怀。这里特别要感谢周广声老师，他对本书第一册中的一些用词和某些基本概念的陈述提出了非常中肯的修改意见。第二册共5章，即第7～11章。
限于作者的学识和水平，难免还会有疏漏和不足之处，敬请读者提出宝贵意见和建议。清华大学计算机系教授，博士生导师
原国际信息学奥林匹克中国队总教练
第7章 利用树状结构解题的策略1
7.1 解决树的最大—最小划分问题的一般方法1
7.2 利用最小生成树及其扩展形式解题8
7.2.1 利用最小生成树解题10
7.2.2 最小k度限制生成树的思想和应用15
7.2.3 次小生成树的思想和应用18
7.3 利用线段树解决区间计算问题20
7.3.1 线段树的基本概念20
7.3.2 线段树的基本操作21
7.3.3 应用线段树解题23
7.4 利用伸展树优化动态集合的操作27
7.4.1 伸展树的基本操作27
7.4.2 伸展树的效率分析30
7.4.3 应用伸展树解题32
7.5 利用左偏树实现优先队列的合并33
7.5.1 左偏树的定义和性质33
7.5.2 左偏树的操作35
7.5.3 应用左偏树解题41
7.6 利用“跳跃表”替代树结构43
7.6.1 跳跃表的概况43
7.6.2 跳跃表的基本操作44
7.6.3 跳跃表的效率分析47
7.6.4 应用跳跃表解题49
小结53
第8章 利用图形（网状）结构解题的策略54
8.1 利用网络流算法解题54
8.1.1 网络与流的概念54
8.1.2 最大流算法的核心——增广路径57
8.1.3 通过求最大流计算最小割切61
8.1.4 求容量有上下界的最大流问题65
8.1.5 网络流的应用70
8.2 利用图的匹配算法解题76
8.2.1 匹配的基本概念76
8.2.2 计算二分图匹配的方法77
8.2.3 利用一一对应的匹配性质转化问题84
8.2.4 优化匹配算法87
8.3 利用“分层图思想”解题94
8.3.1 利用“分层图思想”构建图论模型94
8.3.2 利用“分层图思想”优化算法96
8.4 利用平面图性质解题102
8.4.1 平面图的概念102
8.4.2 平面图的应用实例103
8.5 正确选择图论模型，优化图的运算106
8.5.1 正确选择图论模型106
8.5.2 在充分挖掘和利用图论模型性质的基础上优化算法111
小结116
第9章 数据关系上的构造策略118
9.1 选择数据逻辑结构的基本原则118
9.1.1 充分利用“可直接使用”的信息119
9.1.2 不记录“无用”信息122
9.2 选择数据存储结构的基本方法125
9.2.1 合理采用顺序存储结构126
9.2.2 必要时采用链式存储结构126
9.3 科学组合多种数据结构128
小结130
第10章 数据统计上的二分策略131
10.1 利用线段树统计数据131
10.2 一种解决动态统计的静态方法135
10.2.1 讨论一维序列的求和问题136
10.2.2 将一维序列的求和问题推广至二维137
10.3 在静态二叉排序树上统计数据138
10.3.1 建立静态二叉排序树138
10.3.2 在静态二叉排序树上进行统计139
10.3.3 静态二叉排序树的应用140
10.4 在虚二叉树上统计数据143
小结147
第11章 动态规划上的优化策略148
11.1 减少状态总数的基本策略149
11.1.1 改进状态表示149
11.1.2 选择适当的规划方向152
11.2 减少每个状态决策数的基本策略153
11.2.1 利用最优决策的单调性154
11.2.2 优化决策量161
11.2.3 合理组织状态163
11.2.4 细化状态转移164
11.3 减少状态转移时间的基本策略166
11.3.1 减少决策时间166
11.3.2 减少计算递推式的时间168
小结170
第12章 计算几何上的应对策略172
12.1 应对纯粹计算题的策略探讨172
12.1.1 利用二重二叉树计算长方体的体积并173
12.1.2 利用多维线段树和矩形切割思想解决平面统计或空间统计问题179
12.1.3 利用极大化思想解决最大子矩形问题188
12.1.4 利用半平面交的算法计算凸多边形197
12.2 应对存在性问题的策略探讨200
12.2.1 直接通过几何计算求解200
12.2.2 转换几何模型求解202
12.3 应对最佳值问题的策略探讨204
12.3.1 采用高效的几何模型204
12.3.2 采用极限法205
12.3.3 采用逼近最佳解的近似算法211
小结212无