本书试题涉及知识点的说明

本书中的题目来自2007—2009年广东省青少年信息学奥林匹克竞赛决赛和邀请赛，所有题目都是在ACM/ICPC竞赛中取得优异成绩的历届中山大学ACM/ICPC代表队成员原创的，题型丰富，所覆盖的知识面相当广泛，包括了各种常用的算法设计方法，数据结构设计，以及计算几何、图论、数论、模拟和博弈论等方面的知识。

1. 算法设计方法

（1）递推和递归。几乎所有算法书都将递推和递归列为学习算法设计的第一步。递推就是逐步推导的过程，是从规模较小的问题逐步推导出规模较大问题的一个迭代过程。递推算法主要包含递推初始条件和递推方程两个要素。而递归则是一种降格思维，将问题表示为与原问题相似但规模更小的问题，然后通过函数的自调用来求解问题。递归算法主要包含递归终止条件和递归方程两个要素，递推的算法通常都可以改写成递归。递推在各种数学推导及动态规划中经常被用到。本书中涉及递归算法的题目有2.6节“积木游戏”、4.5节“礼物”、5.7节“方块游戏”等。

（2）搜索、枚举及优化剪枝。在缺乏解决问题的有效模型时，搜索是一种最行之有效的解决问题的基本方法。搜索本身有一个很清晰的基本框架，容易实现；但它本身又很复杂，因为在实现过程中有很大的优化空间，从而可以有效地减少搜索量，避免出现超时的问题。搜索技术主要包括广度优先搜索和深度优先搜索。程序设计类竞赛的搜索问题主要考查选手充分发掘问题隐含的约束条件及设计剪枝优化的能力。另外，由于搜索本质上是对问题解空间的一个遍历，搜索过程中需要避免重复遍历同一个状态，因此，搜索状态如何进行合适的编码和判重往往也是搜索问题的一个重要的考查点。本书中涉及搜索算法的题目有1.4节“秦始皇陵”、2.3节“剑之修炼”、4.2节“夜宵1号”、5.2节“彩球游戏”、5.8节“正方矩阵”、7.2节“Bug”、7.8节“棍子”、8.7节“佩恩的秘密”等。

（3）动态规划（Dynamic Programming，简称DP）。动态规划算法主要用于求解最优化问题。它的特点是能够把求解复杂问题的过程恰当地分成若干个相互联系的阶段，通过组合子问题的解而解决整个问题。动态规划必须符合无后效性及最优化原理两个特点。无后效性是指一个状态的抉择不会影响到代表着更大规模的问题的状态的抉择；而最优性原理则需要一个大问题的最优性必须建立在其子问题的最优性之上。动态规划是竞赛中常见的类型，具有变形多（有线性DP，环形DP，树形DP等），难易跨度大，技巧性强等特点。动态规划算法的设计主要涉及状态表示，状态转移方程，初始状态，问题的解的表示等几个要素。“记忆化搜索”实际上也是动态规划的一种，它是用递归的方式对各个状态进行求解，只是利用数组或者其他方式把所有求解过的状态的答案记录下来，从而避免对同一个状态重复求解。这样的做法的好处是程序写起来简单，而且可以不用求解那些对最终状态没有作用的状态。本书中涉及动态规划算法的题目有1.6节“大航海”、2.7节“夏娜的菠萝包”、4.6节“企鹅”、5.6节“狐狸的谜语”、6.2节“鱼肉炸弹”、7.1节“WXYZ与绿豆饼”、7.5节“猴子”、8.2节“伟大的航路”、8.5节“小新的问题”、9.3节“钱之炼金术师”等。

（4）贪心。贪心算法是使所做的选择看起来都是当前最优的，即“只顾眼前利益”，期望通过所做的局部最优解选择来产生一个全局最优解。其具体策略是并不从整体最优考虑，而是选取某种意义下的局部最优解。当然使用贪心算法时，要使得到的结果也是整体最优的。本书中涉及贪心算法的有2.5节“骰神秘笈”、4.3节“天堂之花”、7.7节“Lie Dice III：雀神秘笈”。

2. 数据结构

算法和数据结构是计算机程序中最基本的两个部分，因此当进行程序设计时，常常会使用到各种数据结构。最基本的数据结构为线性表、树、图等。线性表主要有数组、栈、队列和链表等，而树主要是二叉树相关的结构。由此引伸出来的数据结构有最小堆、AVL树、Splay树、并查集、线段树、哈希表等。它们能够在相对复杂的算法中提高处理速度。本书中与数据结构相关的题有1.8节“轰炸”、3.3节“不公平的比赛”、3.4节“地精计算机”、5.4节“指纹”、6.1节“WING”、8.1节“哆啦A梦的百宝袋”、8.4节“魔神英雄传”、9.4节“牛影传说”。

3. 图论

图论中的知识点相当广泛：最基本的有广度优先遍历、深度优先遍历等，稍复杂的如最短路径问题、拓扑排序、Floyd算法等，更复杂的还有染色问题、匹配问题、网络流问题等。比赛中的图论问题一般有两种：一种可以转化为基本图论问题，然后使用经典算法解决；而另一种需要选手设计算法。本书中涉及到的图论问题有1.2节“讨厌的新系统”、1.3节“纳克萨玛斯”、2.2节“时间与空间之旅”、2.8节“魔之修炼”、4.8节“减肥”、5.3节“酱油推广活动”、6.4节“关键公路”、7.3节“费洛蒙”、7.6节“Debug”、8.3节“课堂笔记”、8.6节“咕噜咕噜魔法阵III”、8.8节“又是Bug”等。

4. 数学题

程序设计类竞赛往往还要求选手具有良好的数学功底。比赛中的数学题主要考查数论、组合数学、概率统计、离散数学等知识。数学问题一般需要通过一定的推导计算，或者从问题中发掘数学规律，从而解决问题。本书与数学相关的问题有1.1 节“谁是天才”、4.4节“张小牛日记”、5.5节“无聊的黑叔”等。

5. 计算几何

计算几何中的知识点也相当多。程序设计类竞赛除了考查基本的几何知识，如两点间最近距离、直线方程、三角形各心、点线面之间的关系、坐标旋转等，通常还会考查凸包相关的一些算法，包括最近点对、卡壳旋转等。另外，扫描线思想的应用也是计算几何的一个考查点。计算几何的题目通常会涉及浮点数运算，选手需要处理好运算中可能产生的浮点误差。本书中与计算几何相关的题目有4.7节“地板砖”、6.3节“验证码”、9.2节“青蛙军曹的地球进攻计划”等。

6. 博弈

博弈题在近几年的程序设计类竞赛中越来越常见，最经典的博弈题是Nim游戏及其变种。解决博弈题需要博弈论的一些基础知识，以及对游戏规则的分析能力和对最优策略的设计能力。本书涉及博弈的题目有1.7节“括号游戏”、3.1节“取石子游戏”等。

7. 模拟及杂题

模拟题也是比赛中常见的一类题目，主要考查选手的编码能力，考虑问题的全面性和细心程度。通常题目的难度不高，但编码量一般比较大。选手需要仔细地阅读题目给出的条件，准确地理解题目的要求，并细心和耐心地将程序准确无误地写好，才可以完成好题目。还有一些使用了不常规的算法或解题方法，我们这里都归类为杂题。本书中本类题目有1.5节“围棋”、2.1节“涂鸦”、2.4节“小岛探险”、3.2节“循环有序序列”、4.1节“万能遥控器”、5.1节“求和号”、7.4节“电梯问题”、9.1节“怪盗基德与牌神秘笈”等。

下表列出本书题目难度及类型。

本书题目难度及类型清单