《程序设计解题策略》素材

本书内容涵盖计算机程序设计中常用的算法策略，包括利用树形结构的解题策略，利用图形（网状）结构的解题策略，数据关系上的构造策略，数据统计上的二分策略，动态规划上的优化策略，计算几何上的应对策略。本书适合作为高校计算机及相关专业数据结构及算法课程的实践教材和教学辅助材料。

封面图

目录

• 前言
• 第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.2Link-Cut Tree的定义82
• 1.5.3Link-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.1SG-组合游戏问题的特殊性质485
• 7.4.2“翻硬币”游戏487
• 7.4.3多图游戏491
• 7.5使用数学工具surreal number应对不平等的组合游戏498
• 7.5.1数学工具surreal number498
• 7.5.2surreal number在组合游戏上的应用500
• 本章小结503