全国青少年信息学奥林匹克联赛章节习题（三）.doc

搜索 7.1 最多因子数 源程序名 可执行文件名 输入文件名 输出文件名 divisors.???（pas, c, cpp） divisors.exe divisors.in divisors.out 【问题描述】 数学家们喜欢各种类型的有奇怪特性的数。例如，他们认为 945 是一个有趣的数，因 为它是第一个所有约数之和大于本身的奇数。 为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内 约数个数最多的那个数。不幸的是，这个数和给定的范围的都比较大，用简单的方法寻找可 能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。 【输入】 只有一行，给出扫描的范围，由下界 L 和上界 U 确定。满足 2≤L≤U≤1000000000。 【输出】 对于给定的范围，输出该范围内约数个数 D 最多的数 P。若有多个，则输出最小 的那个。请输出“Between L and U，P has a maximum of D divisors．”，其中 L，U，P 和 D 的含义同前面所述。 【样例】 divisors.in divisors.out 1000 2000 Between 1000 and 2000, 1680 has a maximum of 40 divisors. 【知识准备】 深度优先搜索的基本实现方法及剪枝的基本概念。 【算法分析】 本题的要求是，求出一个给定区间内的含因子数最多的整数。 首先，有必要明确一下如何求一个数的因子数。若一个数 N 满足 N=P1N1·P2N2·P3N3·…·PmNm，其中 P1, P2, …, Pm 是 N 的 m 个质因子。则 N 的约数 个数为(N1+1)·(N2+1)·(N3+1)·…·(Nm+1)。这一公式可以通过乘法原理来证明。 有了求因子数的公式后，最容易想到的算法就是，枚举区间内的每个整数，统计它们的 约数个数。这个算法很容易实现，但是时间复杂度却相当高。因为区间中整数的范围是 1～ 1000000000，整个枚举一遍并计算因子数的代价约为 109×(109)0.5=1013.5。这个规模是无 法忍受的。所以，我们需要尽量优化时间。 分析一下枚举的过程就会发现，如果我们分别枚举两个数 n 和 p·n（p 为一相对较大 的质数），那么我们将重复计算两次 n 的因子数。其实，如果枚举顺序得当的话，完全可以 在 n 的基础上去计算 p·n，而如果能在 n 的基础上计算 p·n，就相当于计算 p·n 的因子 数只用了 O(1)的时间。这是一个比较形象的例子，类似的（可能相对更复杂一些）重复计 算在枚举过程中应该是普遍存在的。这就是枚举效率低的根本所在。为了解决这一重复，我 们可以选取另一种搜索顺序——枚举质因子。这样的搜索顺序可以避免前面所说了类似 n 和 p·n 的重复计算。 定义 number 为当前搜索到的数。初始时，令 number=1，然后从最小的质数 2 开始枚 举，枚举因子中包含 0 个 2、1 个 2、2 个 2、…、k 个 2 的情况……直至 number·2k 大于 区间的上限(max)。对于每个“2k 的情况”，令 number:=number*2k，在这个基础上，再枚 举因子 3 的情况。然后在 3 的基础上枚举因子 5 的情况，然后是 7 的情况……整个过程是 一个深度搜索的过程，搜索的过程中，利用前面提到的求因子数的公式可以算出当前的 number 的因子数供下一层枚举继承。当 number 大于等于区间下限(min)时，我们就找到 了一个区间内的数(枚举的过程已保证 number 不超过上界)。 所有枚举得到的区间内的数中， 因子数的最大值就是我们要求的目标。 这样的枚举完全去除了重复计算，但是这还是不够的，因为光 1～1000000000 内的数 每枚举一遍就有 109 个单位的操作。所以，我们还需要找到一些剪枝的方法，进一步优化时 间。 我们看到，如果当前搜索状态为(from, number, total)，其中，from 是指当前枚举到的 质因子（按从小到大枚举），total 是指 number 中包含的因子数。那么剩下的因子数最多为 q=logfrommax/number，这些因子组成的因子个数最大为 2q。因此，当前所能取到的（理想 情况）最大约数个数就是 total·2q。如果这个数仍然无法超过当前最优解，则这一分支不 可能产生最优解，可以剪去。 此外，如果[(min-1)/number]=[max/number]，则表示以当前状态搜索下去，结果肯定 不在区间内了，就无法产生合法解，也可剪去。不过，这一剪枝作用不是很大，因为即使不 剪，再搜索一层也就退出了。 以上两个剪枝，前一个是最优化剪枝，后一个是合法性剪枝。相比较而言，前一个剪枝 的作用要大得多。 下面我们用平摊分析的方法来讨论一下搜索的复杂度。 由于枚举的过程中没有重复计算， 每枚举一个质因子，都可以得到一个不同的 number(number≤max)，所以可以将每一个单 位的枚举质因子的代价与一个不超过 max 的 number 对应，并且还可在两者之间建立双射。 不同的 number 最多只有 max 个，所以枚举的总代价不超过 O(max)，max≤109。 加上了剪枝以后，计算总代价就远远小于 O(max)了。从运行效果来看，即便是最大数 据，也可以很快出解。 从本题的解决过程中可以看到，最关键的有两步： （1）采用合理的搜索顺序，避免重复计算； （2）利用最优化剪枝和合法性剪枝，剪去一些不可能产生最优解或合法解的分支。 这两种优化的方法在搜索中的地位是极其重要的，当然可能在本题中的重要性体现得格 外突出。 7.2 黑白棋游戏 源程序名 可执行文件名 输入文件名 输出文件名 game.???（pas, c, cpp） game.exe game.in game.out 【问题描述】 黑白棋游戏的棋盘由 4×4 方格阵列构成。棋盘的每一方格中放有 1 枚棋子，共有 8 枚 白棋子和 8 枚黑棋子。这 16 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 1 条公共边的 2 个方格称为相邻方格。一个方格最多可有 4 个相邻方格。在玩黑白棋游戏时， 每一步可将任何 2 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态， 编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。 【输入】 输入文件共有 8 行。前四行是初始游戏状态，后四行是目标游戏状态。每行 4 个数分 别表示该行放置的棋子颜色。“0”表示白棋；“1”表示黑棋。 【输出】 输出文件的第一行是着棋步数 n。接下来 n 行，每行 4 个数分别表示该步交换棋子的两 个相邻方格的位置。例如，abcd 表示将棋盘上(a，b)处的棋子与(c，d)处的棋子换位。 【样例】 game.in game.out 1111 4 0000 1222 1110 1424 0010 3242 1010 4344 0101 1010 0101 【知识准备】 （1）宽度优先搜索的基本概念； （2）位操作相关知识。 【算法分析】 本题是一道典型的宽度优先搜索题。宽度优先搜索的方法本身应该是很显然的：根据题 目的描述，对于任意一个棋盘状态，可以通过交换相邻两个格子中的棋子得到新的状态（一 次最多得到 24 个新状态）。所以，我们可以从题目给出的起始状态开始不停的扩展，直至 扩展出目标状态。最后，只需输出扩展的路径即可。 上述算法已经可以完全解决本题了。但是，我们现在要继续往细节里讨论本题，讨论本 题的实现。 宽度优先搜索的核心是状态的扩展，状态的扩展是通过状态转换实现的。普通的状态转 换的方法就是按照题目的定义模拟实现。这里，我们要讨论的是高效简洁的状态转换的方法。 首先是状态的表示。题目中的棋盘是由 16 个格子组成的(4×4)，如下图。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a1 a1 a1 a1 a1 0 a1 1 a1 3 4 5 6 a7 a8 a9 2 这 16 个格子，每个格子里非 0 即 1，所以可以将棋盘写成一个长度为 16 的 01 串。 a1 a2 a3 a4 a5 a6 a1 a1 a1 a1 a1 a1 a1 0 1 2 3 4 5 6 这个 0l 串可以用一个 16bit 的整数来表示。也就是说，我们可以用一个 0～65535 的整 数来表示一个状态。 下面最关键的就是状态的转换了。根据题目的定义，每次操作可以交换棋盘上相邻两个 格子中的棋子。显然，如果相邻两个格子中的棋子相同，交换是没有意义的，所以我们只需 要考虑相邻格子中棋子颜色不同的情况。相邻有两种情况，左右相邻和上下相邻。如图，a1 和 a2 为左右相邻，而 a8 和 a12 为上下相邻。我们讨论状态转换的时候，将对这两种“相 邻”分别处理。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a1 a1 a1 a1 a1 0 a1 1 a1 3 4 5 6 图 7-2 2 首先来看左右相邻的情况，以 a15 和 a16 为例。它们交换以后，得到的棋盘状态为： a1 a2 a3 a4 a5 a6 a7 a8 a9 a1 a1 a1 a1 a1 0 a1 1 a1 3 4 6 5 图 7-3 2 但是，从另一个角度来考虑问题，a15＝??a16，所以经过转换后，就相当于将 a15 和 a16 取反。从位操作的角度来看，设原状态为 s，那么 a15 和 a16 交换后得到的新状态 s15 为： s15=s xor 3 同样的，还可以推出 a14 和 a15 交换后得到的新状态 s14 为： s14=s xor 6=s xor (3*21) 当然，还有以下很多状态公式： s13=s xor 12=s xor(3*22) s11=s xor 48=s xor(3*24) s10=s xor 96=s xor(3*25) 这里有两个需要注意之点： （1）交换的两个棋子的颜色必须不同，否则公式不成立； （2）根据状态转换的定义 s4、s8、s12、s16 对应的公式不成立，因为它们右边没有相 邻的棋子。 最后，我们总结一下左右相邻情况下的状态转换公式（棋子颜色必须不同） sk=s xor(3*215-k)，其中 k≠4, 8, 12, 16 与“左右相邻”对应的是“上下相邻”。 “上下相邻”情况的分析与“左右相邻”类似， 这里就不详细展开了，只列出转换的公式（同样，棋子颜色也必须不同） sk=s xor(17*212-k)，其中 k≤12 有了上面两个状态转换的公式，我们只需将起始状态和目标状态转换成 16bit 的整数， 利用公式从起始状态扩展至目标状态即可。整个过程的时间复杂度是 O(24*216)。 从另一个角度考虑问题。本题给出了起始状态和目标状态，那么我们完全可以从这两个 状态开始，分别扩展——也就是用双向宽度优先搜索的方法来解决本题。一般来说，双向搜 索扩展出的状态总数要比单向少很多，时间和空间复杂度都会有所降低。 7.3 纵横填字游戏 源程序名 可执行文件名 输入文件名 输出文件名 puzzle.???（pas, c, cpp） puzzle.exe puzzle.in puzzle.out 【问题描述】 这个题目要求你编写一个程序来解决一个纵横填字游戏。 这个游戏比我们在报纸上见到的通常的填字游戏要简单。游戏仅给出单词的起始位 置，方面(横向或纵向)以及单词的长度。只要单词的长度正好，游戏中能填入任何一个来自 词典的单词。 在游戏中单词相交处的字母必须相同，当然，任何单词只准使用一次。 思考一下以下这个游戏。 例如，假定从上到下有 5 行，用 0 到 4 来表示，从左到右有 5 列，用 0 到 4 来表示。 我们用(X, Y)来表示填字游戏中第 X 列和第 Y 行的字母。 在这个游戏中，我们需填入 5 个单词：在(0, 0)的右边填入一个 4 个字母的单词，在 (0, 0)的下方填入一个 4 个字母的单词，在(2, 0)的下方填入一个 4 个字母的单词，在(0, 2)的右边填入一个 3 个字母的单词，最后在(2, 3)的右边填入一个 3 个字母的单词。字典上 所有的单词都能使用但最多只能使用一次。例如，以下是一个可能的解决方案。 （0, 0）右边，LATE （0, 0）下面，LIED （2, 0）下面，TELL （2, 3）右边，LOW 【输入】 输入文件的第一行是作为字典使用的—个文本文件名，你可以假定这个文件存在，是可 读的并且包含最多不超过 100000 个单词，并且按词典顺序存储，每行一个单词。字典中所 有的单词所含的字母可以是大写或小写(在这个问题中字母的大小写是无关紧要的)。你可以 假设字典中所有单词的长度不超过 20 个字符。输入文件的下一行包含一个整数 n(n≤15)， 表示要填的单词的数量。接下来的 n 行中每行给出关于一个单词的提示，在每个提示中分 别给出单词的首字母在填字游戏中的列和行的位置，后面根据单词的方向是横向还是纵向， 相应跟字符 A 或字符 D，最后一个数表示该单词的长度，以上数据之间均用空格隔开。 你能作以下的进一步的假设。 （1）填字游戏的尺寸不超过 10×10。 （2）游戏盘中放得下所有的单词。 （3）用给定的词典是能够破解出该游戏的。 【输出】 输出文件应该包含 n 行，输出游戏中可填入的所有单词。单词应该每行出现一个，并 且按输入文件中提示的顺序输出。每个单词中所有的字母必须是大写的。所有的单词必须来 自给定的词典文件(忽略大小写)。任何单词只能使用一次。对于给定输入文件可能有大量的 正确解决方案，你只须输出其中的任意一个解决方案。 【样例】 puzzle.in puzzle.out words.txt LATE 5 LIED 00A4 TELL 00D4 EEL 20D4 LOW 02A3 23A3 【知识准备】 （1）深度优先搜索的基本实现方法； （2）Hash 表的基本理论及其实现方法（主要是“吊桶处理冲突法”） 。 【算法分析】 本题是一个规模巨大的搜索问题，其规模主要体现在词典（单词表）中的单词数（最多 可达到 100000），这意味着每在一个空位中填一个单词就可能有 100000 种选择。 搜索题一般来说都会有很强的剪枝性，但是本题没有，除了一些合法性的剪枝外，基本 上找不到任何可行的剪枝，哪怕是效果很弱的剪枝也没有。 先来看看最简单而且能够非常自然想到的搜索方法：一个一个空位枚举，对于题目给出 的每个空位在单词表中枚举一个暂时符合要求的单词填进去。这个算法最坏情况的时间复杂 度是 O(100000n)的(n≤20)。当然，10000020 的阶一般是达不到的，但是要达到 1000002 应该不是很难办到的，而 1000002 已经足以让程序超时了。 让我们分析一下上面算法的瓶颈。 对于 O(100000n)的算法来说，降一点指数其实效果不是非常明显的，因为起码要把 n 降到 1.x 才能不超时，而且降指数也不是那么容易办到的。然而，如果能把 100000 这个底 数降低到很小，比方说一个小常数，效果应该就很好了。由于 n 不大，只有 20，如果底数 很小的话（设为 c），算法的时间复杂度就是 O(cn)，再加上一些可行性的剪枝，程序的效 率应该是很高的。 现在的问题就是，如何来降这个 100000 的底数了。前面提到的最简单的搜索方法，每 枚举一个单词都要扫描一遍单词表，这是极大的浪费，因为单词表中绝大多数的单词都是非 法的（根据一般英语词典的情况来说)。实际上，我们扫描一遍单词表的目的是找出所有当 前合法的单词，而实现这一目的并非只能用扫描一遍单词表这种方法。 我们知道有一个概率常数级的查找方法——Hash 法。 当然，Hash 一般是用来查找单一元素的，而我们要查找的是所有的合法单词（每个合 法单词都是不同的），也就是查找多个元素。在这点上，Hash 是不适合作本题的查找数据 结构的。不过，稍微利用一下 Hash 的特殊性质，这个问题就解决了。Hash 需要设计 Hash 函数，而 Hash 函数是有不可避免的冲突的，如果被查找元素发生冲突，则可能找到多个目 标元素，必须在多个目标元素中找出真正要查找的元素。我们正好可以抓住“冲突”这一点， 利用这个“冲突”，设计一个比较特殊的 Hash 函数，让所有的合法单词的 Hash 函数值相 同，即让所有合法单词“冲突” 。这样，要找合法单词，只要计算一下任一合法单词对应的 Hash 函数值，然后在 Hash 表中把该值对应的所有冲突单词找出来即可。 现在我们就来设计这个 Hash 函数。其实这个函数说来也简单：首先确定一个搜索的顺 序（即先搜索哪个空位，后搜索哪个空位），然后就可以确定搜索每个空位时该空位中被确 定的字母的位置。 如图 7-4，共有两个空位可填单词，(0, 1)~(2, 1)和(1, 0)~(1, 2)。假设先填 (0, 1)～(2, 1)，这时没有任何位置的字母被确定，所有长度为 3 的单词都是合法的单词。但是，填完第 一个单词以后，对于空位(1, 0)～(1, 2)来说，就有一个位置的字母已经被确定下来了，它就 是(1, 1)位置上的字母。 图 7-4 Si …… 1 Si j …… Sin 图 7-5 如图 7-5，设一个长度为 L 的单词的第 i1、i2、…in 位上已经被确定下来，那么一种可 以选择的 Hash 函数是 f (S)  (Si * pi  Si * pi    Sin * pin ) modHASHLEN 1 1 2 2 这里，p 可以是任取的一个数（一般来说，p 取质数效果比较好） ，HASHLEN 是 Hash 表的长度（一般也是取质数效果较佳） 。 设计完了 Hash 函数以后，一切的做法就一目了然了：首先确定一个搜索的顺序，根据 每一步空位上确定的字母的位置，对每个单词按特定的 Hash 函数计算其 Hash 函数值，并 将其放入 Hash 表（建议用“吊桶法”处理冲突），这是一个初始化的过程。然后，按前面 定的顺序进行搜索（这个顺序最好是每次都选能确定字母数最多空位），根据确定的字母计 算出合法单词对应的 Hash 函数值，并从 Hash 表中取出所有合法单词（当然，也可能会取 出少量的非法单词，可以稍加判断将其去除） ，进行枚举。 算法的总体思想是利用 Hash 表来快速的查找合法单词，以达到可行性剪枝的目的。 最后，我们来简单分析一下算法的复杂性。由于使用了 Hash 表，复杂度是概率的，很 难估算。需要指出的是，待选的单词表是一个词典，词典一般是正态分布的，所以除了搜索 的第一层以外，以后的合法单词肯定都是很少的，再加上合法性剪枝的成分，实际上程序的 效率应该是很高的。但是，这个算法毕竟还是指数级的，虽然使用了 Hash 表基本上把所有 的无用功都去掉了（当然，还会有一些非法单词产生冲突，不过，当 Hash 表长度达到单词 数的两倍以上后，这样的冲突概率一般都很小，基本可以忽略）。指数级的算法肯定不是一 个完美的算法，所以如果数据非常强的话，这个算法也是有可能超时的，只是这样的数据很 难出，至少现在还没能找出这样的数据来。 7.4 魔术数字游戏 magic.???（pas, c, cpp） magic.exe magic.in magic.out 源程序名 可执行文件名 输入文件名 输出文件名 【问题描述】 填数字方格的游戏有很多种变化，如下图所示的 4×4 方格中，我们要选择从数字 1 到 16 来填满这十六个格子(Aij，其中 i＝1..4，j＝1..4)。为了让游戏更有挑战性，我们要 求下列六项中的每一项所指定的四个格子，其数字累加的和必须为 34： 四个角落上的数字，即 A11+A14+A41+A44＝34。 每个角落上的 2×2 方格中的数字，例如左上角：A11+A12+A21+A22＝34。 最中间的 2×2 方格中的数字，即 A22+A23+A32+A33=34。 每条水平线上四个格子中的数字，即 Ai1+Ai2+Ai3+Ai4＝34，其中 i＝1..4。 每条垂直线上四个格子中的数字，即 A1j+A2j+A3j+A4j＝34，其中 j＝1..4。 两条对角线上四个格子中的数字，例如左上角到右下角：A11+A22+A33+A44＝34。 右上角到左下角：A14+A23+A32+A41＝34 A11 A12 A13 A14 A21 A22 A23 A24 A31 A32 A33 A34 A41 A42 A43 A44 【输入】 输入文件会指定把数字 1 先固定在某一格内。输入的文件只有一行包含两个正数据 I 和 J，表示第 1 行和第 J 列的格子放数字 1。剩下的十五个格子，请按照前述六项条件用数 字 2 到 16 来填满。 【输出】 把全部的正确解答用每 4 行一组写到输出文件，每行四个数，相邻两数之间用一个空 格隔开。两组答案之间，要以一个空白行相间，并且依序排好。排序的方式，是先从第一行 的数字开始比较，每一行数字，由最左边的数字开始比，数字较小的解答必须先输出到文件 中。 【样例】 magic.in magic.out 11 1 4 13 16 14 15 2 3 8 5 12 9 11 10 7 6 1 4 13 16 14 15 2 3 12 9 8 5 7 6 11 10 【问题分析】 设方格中的 16 个数为 16 个未知数。根据题目给出的约束，可以列出 16 个方程。 四个角落上的数字： A11+A14+A41+A44=34 每个角落上的 2*2 方格中的数字： A11+A12+A21+A22=34 A13+A14+A23+A24=34 A31+A32+A41+A42=34 A33+A34+A43+A44=34 最中间的 2*2 方格中的数字： A22+A23+A32+A33=34 每条水平线上四个格子中的数字： Ai1+Ai2+Ai3+Ai4=34，其中 i=1..4。 每条垂直线上四个格子中的数字： A1j+A2j+A3j+A4j=34，其中 j=1..4。 两条对角线上四个格子中的数字： A11+A22+A33+A44=34 A14+A23+A32+A41=34 当然，这 16 个方程是有线性相关的，所以这个方程组是不定方程。解方程时，可能会 出现自由未知量。不过，未知数的取值范围较小（1~16） ，所以可以通过枚举自由未知量的 方法来求得所有解。 7.5 魔板 源程序名 可执行文件名 输入文件名 输出文件名 panel.???（pas, c, cpp） panel.exe panel.in panel.out 【问题描述】 有这样一种魔板：它是一个长方形的面板，被划分成 n 行 m 列的 n*m 个方格。每个方 格内有一个小灯泡，灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态 改变为另一个状态。操作的方式有两种： （1）任选一行，改变该行中所有灯泡的状态，即亮的变暗、暗的变亮； （2）任选两列，交换其位置。 当然并不是任意的两种状态都可以通过若干操作来实现互相转化的。 你的任务就是根据给定两个魔板状态，判断两个状态能否互相转化。 【输入】 文件中包含多组数据。第一行一个整数 k，表示有 k 组数据。 每组数据的第一行两个整数 n 和 m。(0