2022年2022年极力推荐搜索基础 .pdf

《2022年2022年极力推荐搜索基础 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年极力推荐搜索基础 .pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、搜索基础 2006/01/23版 By XT 搜 索 基 础浙江省镇海中学 xt 目录1. 穷举法例题 1 光光的困惑（故事题）例题 2 砝码称重（ NOIP T96-4）例题 3 逻辑判断（ TOJ1130 ）例题 4 数字和问题（宁波 2005小学组）例题 5 等差数列（ ZJOI2004）例题 6 敲七、敲七版本 2（TOJ1006/1044）例题 7 猫老大数（ TOJ1081 ，猫老大与彩虹的竞赛）例题 8 勇闯黄金十二宫金牛宫（ TOJ1001 ，黄金十二宫）例题 9 石子合并（ TOJ1017 ）例题 10 反正切函数的运用（ NOI2001）例题 11 广告印刷（ TOJ 一周

2、年比赛）例题 12 仓库扩张（ USACO Contest DEC05）例题 13 行星队列（ USACO Contest DEC05）2. 深度优先搜索例题 1 四色图问题（宁波 2005高中组）例题 2 外星生命（ TOJ1062 ）例题 3 数的划分、放苹果（ NOIP T2001-2、POJ1664 ）例题 4 跳棋的挑战（ USACO Training 1.1.4-1）例题 5 骑士的游历 1、2（NOIP T97-3&经典问题）例题 6 黑白棋（ ZJOI03 ）例题 7 卫星照片（ USACO Contest NOV05）例题 8 房间问题（ IOI94 ）例题 9 谷仓安全保护

3、（ USACO Contest NOV05）例题 10 水碗（ USACO Contest JAN06）3. 广度优先搜索例题 1 救援行动（ TOJ1051 By AngelForYou）例题 2 瑰丽华尔兹（ NOI2005）例题 3 倒水问题（经典问题）例题 4 麻将游戏（ SGOI ）例题 5 拯救大兵瑞恩（ CTSC99 ）例题 6 补丁 VS 错误（CTSC99 ）例题 7 穿越封锁线（ OIBH20051113抗日英雄传）例题 8 最后的战犯（ OIBH20051113抗日英雄传）例题 9 Ni骑士（ USACO Contest DEC05）4. 双向广度优先搜索例题 1 九数码

4、问题（ ZJOI2005）例题 2 字串变换（ NOIP T2002-2）5. 迭代加深 DFS 例题 1 跳房子（ USACO Contest NOV05）第 1 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 例题 2 埃及分数（ OIBH ）6. 随机化法例题 1 线型网络（ OIBH ）例题 2 勇气的挑战（ TOJ1073 ）例题 3 虫食算（ NOIP

5、T2004-4）7. 总结第 2 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 1.穷举法 例题 1 光光的困惑 光光的妈妈给光光一篮鸡蛋，让光光拿去给外婆。光光很高兴地接过鸡蛋，向外婆家走去。途中，光光想：这一篮鸡蛋有多少个呢？于是，光光就开始一个个地拿出鸡蛋，数了起来：一个、两个一不小心，蛋全倒翻摔碎了。光光大哭起来例题中，光光数鸡蛋的方法是穷举法，他依次取出

6、鸡蛋然后数，也就是遍历了所有的情况。这样的方法，在其他的题目中，此种方法也是适用的。这是一种最基础的搜索，它的本身不需要用到高深的知识，却是搜索算法的核心。搜索算法的核心就是遍历。而穷举具备了这一点。所以，在搜索找不出很好的方法时，穷举是我们的唯一法宝。下面，我们讲一道经典习题的穷举算法。这是一种经典的穷举。 例题 2 砝码称重（NOIP T96-4 ） 设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重=1000 ） ，输出用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。最容易想到的方法就是枚举出有几个1g ，几个 2g，几个 3g 几个 20g ，然后统计

7、有几种不同的重量。 用数组 w1w6表示重量，q1q6表示选择方案。算法描述如下（Pascal 语言） ：for q1:=0 to a1 do for q2:=0 to a2 do for q3:=0 to a3 do for q4:=0 to a4 do for q5:=0 to a5 do for q6:=0 to a6 do begin sum:=0; for i:=1 to 6 do sum:=sum+qi*wi; end;利用 6 个 for 循环可以算出总重量sum ，剩下的工作就是要判断sum 是否已经出现过即判重。要实现这点很简单，注意到条件：其总重=1000，可以开一个 0.

8、1000的 boolean数组 H，设初值为 false, 然后 Hsum:=true，最后统计在 H1.1000中有几个 true 即可。总结：此枚举算法着实弱智，但事实上此算法可以通过所有的测试数据，在比赛中使用可以省时省力。 因此我们要改变印象中枚举算法是低效的观念，在没有方法时，枚举往往是突破口。 （By 光光）另注：此题的动态规划（ Dynamic Programming）算法此处不予讨论。 例题 3 逻辑判断（TOJ1130 ） 小卡卡从 Pascal 神庙附近的居民那里还了解到，远古时候的 Pascal 圣地居住着三种居民： 永远说真话的神， 永远说假话的恶魔和在白天说假话，在夜

9、里说真话的 Pascal 人。小卡卡想，是否能根据远古居民的话来判断他们都是那种类第 3 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 型的居民。 有五个居民 A，B，C ，D ，E。他们说的话只有3 种： 1.I am not divine/evil/human. 2.X is not divine/evil/human. 3.It is day/night.居

10、民们说话的总数不超过50。 你的任务就是通过居民们说的话来判断他们的种类以及现在是白天还是黑夜。 这道题目是一道经典的穷举题。在这道题目中， 我们首先可以计算出， 我们需要穷举的东西人们的属性和白天或黑夜。显而易见，五个人的属性与白天黑夜至多需要穷举3*3*3*3*3*2=486， 因为人数可能不到5 个。而我们又不能想出更好的方法。于是我们就采用了穷举，作为这道题的正确算法。在穷举上，我们有一个经典的“加一算法”来遍历。具体方法是这样的：我们设五个人的属性分别有0/1/2三种情况，则我们可以用“三进制”计算得到 243 种情况，具体方法我们列几个：具体方法说明五人状态开始0 0 0 0 0

11、末位加一0 0 0 0 1 末位加一0 0 0 0 2 进位0 0 0 1 0 末位加一0 0 0 1 1 末位加一0 0 0 1 2 进位0 0 0 2 0 末位加一0 0 0 2 1 末位加一0 0 0 2 2 进位再进位0 0 1 0 0 依照这样的方法，我们可以穷举每个人的状态，并且判断是否与供词符合。参考程序留给读者自己完成。 例题 4 数字和问题（宁波2005 小学组） 已知 n 个整数 x1,x2, ,xn，以及一个整数k(kn)。从 n 个整数中任选 k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：

12、 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34 现在，要求你计算出和为素数的共有多少种。 本题限定了数据规模， 故可以很快判断出本题适用于穷举法。穷举法的常见思路有加一算法，本题即可以穷举出k个进行相加，判断是否为素数。素数n判断的一种方法是：由2 穷举至n ，如果没有 n的约数，则可以判断出 n是素数，反之不能。利用穷举法，我们可以有一种直接的思路： 枚举x1xn是否要取，第 4 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

13、4 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 如果达到共 k个，则进行求和，并且判断是否为素数，统计。此种方法在数据规模较大的时候不是很好用，也就是判断次数在n大时增长迅速，属于指数级渐进时间复杂度，时间耗费大。时间复杂度O（2n） 。 例题 5 等差数列（ZJOI2004 ）给定 n(1=n=100) 个数, 从中找出尽可能多的数使得他们能够组成一个等差数列. 求最长的等差数列的长度. 我们首先必须对这个数列进行排序，排序我们采用QuickSort。然后我们就能够很快想到一系列的方法：枚举头部、第二个与尾部。但是我们为什么要枚举三个呢

14、？头部当然不用说，第二个是为了与第一个作差，得出公差。然后就可以递推地去枚举到最后。这样我们就能够得出一个O(n3) 的方法，而在 n=100的时候保证不会超时。 例题 6 敲七、敲七版本2（TOJ1006/1044 ） 1.输出 7 和 7的倍数，还有包含7 的数字例如（17，27，37.70 ，71，72，73. ） ，给出一个整数N ， （N 不大于 30000 ） ，输出从小到大排列的不大于N的与 7 有关的数字，每行一个。 2. 给定正整数 N ，求数列An的前N项。数列An满足如下条件： 1.该数列包含自然数集中所有能被7 整除的数 2.该数列包含自然数集中所有个位上含7 的数，如

15、 17,27,177 3.该数列不包含自然数集中其他的数 4.该数列中的数有小到大有序排列 5.该数列中任意两项互不相同 给出一个正整数 N （N=100,000 ）， 输出数列An的前N项，每项占单独一行。1. 这道题按照题意，我们可以求得最简单的方法：从1 枚举到 N，对每一个数字进行判断。 当然这是对这个数据来说最好的方法，其实还有一种方法是预处理，用一些方法记录下来（方法很多） 。至于判断是否含有7，我想到的是一位一位看，而 Maigo 大牛有个方法，就是转成字符串用POS，这是不是个好方法呢？2. 理清题意，发现这是个简单题。读入N 后，我们从 1 开始依次枚举，对每个数字进行 2

16、次运算，如果运算成功，就可以输出并记录个数，直到最后。这个题目还有一种对于大数据的高效方法合并有序链表。我们可以建立2 个链表，然后生成1.N中符合条件的数字。因为这两个链表是有序的，因此用两个指针（静态、动态皆可）去合并。这样是最优效果。 例题 7 猫老大数（TOJ1081 ，猫老大与彩虹的竞赛） 猫老大很喜欢研究数字，特别是喜欢质数。一天，猫老大发现有一些数字可以表示成两个质数相乘的形式。比如， 102 5. 2，5 都是质数，所以 10 是一个“ 猫老大数 ” 。所以猫老大决定考考彩虹，他告诉彩虹一个数 n ，判断 n 是不是“ 猫老大数 ” ？（1=n=231-1） 第 5 页 共 2

17、5 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 由于题目中含有条件1=n=231-1= maxlongint（LONG_MAX ） ，所以我们可以先计算出1 到312 - 1的所有质数，共有4792 个。求质数的方法在例题 4 讲过。于是我们把这些质数存在数组中，完成了第一步的预处理工作。有这样一个定理：如果一个数是合数，那么它一定会有一个小于等于这个数的开方的不是1 的因数

18、。根据这个理和题意，则如果这个数是合数，我们只须要枚举 2 到n 就可以找到一个质数。然后根据唯一分解定理， 我们可以得出猫老大数必定只能质数分拆为两个质数。所以我们只须判断被一个质数除下后是不是质数即可。由于两个质数是成反比例的（ n 一定） ，根据函数曲线，得出一种好的方法先从小到大找到一个较小的，然后继续判断，直到找到第二个，判断剩下的是不是1。 例题 8 勇闯黄金十二宫 金牛宫（TOJ1001 ，黄金十二宫） 现在给出一个数字n，如果n可以表示成2 个合数相乘的形式，则n被称作“ 牛数” ，否则n被称作 “ 弱数” 。比如 164 4，4 为合数，所以 16是一个 “ 牛数” 。阿尔迪

19、巴告诉星矢很多数 字，叫星 矢判断这 些数字是“ 牛数 ” 还是 “ 弱数 ” 。 （1=n=231-1） 其实这道题目与上道题目相反， 有很大的相通之处。 首先，预处理做法相同。其次，如果能够表示为两个合数的乘积，必定能够表示成为4 个或以上的质数的乘积。我们用预处理的质数表求出质数的个数，然后判断是否大于等于4 个就可以了。具体做法参看上题。 例题 9 石子合并（TOJ1017 ） 你有一堆石头质量分别为W1,W2,W3.WN.(W100000)现在需要你将石头合并为两堆，使两堆质量的差为最小。规定1=N=20 ，需输出合并后两堆的质量差的最小值。 这种题目有个直白的方法加一算法。由于 1

20、=N=20，我们就可以直接把这 N 堆用穷举的方法分成两堆，每一次都需要计算，然后求出最小值。最多每组数据需要计算1048576种情况。具体实现起来非常简单， 我也就不再这里多说了。我的程序的运行时间大约是13xxms ，光光的大约是15xxms ，一般来说用这种方法枚举不会超时。 例题 10 反正切函数的运用（NOI2001 ）反正切函数可展开成无穷级数，有如下公式 =+-=01212)1()arctan(nnnnxx ( 其中01x ) 公式(1) 使用反正切函数计算是一种常用的方法。例如，最简单的计算的方法： 第 6 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - -

21、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT ?+-+-+-=1119171513114) 1arctan(4公式(2) 然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式： )tan()tan(1)tan()tan()tan(-+=+公式(3) 通过简单的变换得到： )1arctan()arctan()arctan(pqqpqp-+=+公式(4) 利用这个公式，令31,21=qp，则11=-+pqqp，有 ( )1arc

22、tan312113121arctan31arctan21arctan=?-+=?+?使用21和31的反正切来计算，速度就快多了。 )1arctan(我们将公式(4) 写成如下形式 )1arctan()1arctan()1arctan(cba+=其中、b和均为正整数。 ac我们的问题是：对于每一个给定的（a600001a） ，求b的值。我们保证对于任意的 a 都存在整数解。如果有多个解，要求你给出b+c最小的解。 c首先我们对题目中给出的式子进行转化：11arctanarctanarctanab? ?=+? ? ?1c，111arctanarctanarctan111bcbcabcbc?+?+?

23、=?-?-?，11bcabc+=， -交叉相乘得，化简得(1bca bc-=+)1bcabac-= ，等号左右两边同时加上得， 合 并 同 类 项 得2a21bcabacaa-+= +2()()21bacaa-= +， 移 项 得第 7 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 21acba+=+-a。 由于、c次序无关紧要，所以我们不妨设bbc ， 则有21

24、ababa+-，21ababa+-。由题意，显然得出ab，()221baa- +，21baa-+，得到21ba+a，取值范围为b21,1aaa?+?，枚举 b 即可。 例题 11 广告印刷（TOJ 一周年比赛） 最近，afy 决定给 TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的 N个建筑。afy 决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2HN ，且0Hi=1,000,000,000， 并且我们假设每个建筑物的宽度均为1。 N = 1,000,000，要求输出广告牌的最大面积。 方法不难想到： 如果要使涂刷的

25、总面积是最大的，那么就必然有那么一个建筑物被刷满。那么哪一个建筑物能够被刷满才能够使总体涂刷的面积是最大的呢？沿袭上面的思路， 我们穷举每一个建筑物， 设它能够被刷满。 于是我们可以用两个循环来枚举它的左方与右方各自能够延伸到哪里（也就是求出覆盖到哪里） ，然后这时的面积就可以用这个建筑物的高度* 被覆盖建筑物的总个数，求每次求出来的面积中的最大值。此题的路径压缩可以采取类似并查集的方法，实现起来也很简单。 由于具体的实现与搜索关系不大，所以这里也就一笔带过了。 例题 12 仓库扩张（USACO Contest DEC05） 在 FJ 的农场里有 N （1=N=25000）个长方形仓库，这些仓

26、库的四条边都分别与 x 轴、y轴平行，且四角坐标均为正数，范围为0.1000000。这些仓库都不互相重叠，但是可能有一些点或者一段边是它们共有的。 一次，FJ 得到了更多的奶牛去挤奶， 因此他想扩张自己的仓库。 一个仓库有能够扩张的条件是它不与别的仓库存在任何一个公共角或者任意一段公共边。请你计算有多少个仓库可以扩张。 这道题目枚举的方法有些特殊，需要一些枚举技巧。首先在读入时，我们的处理方法是“拆边”，按横、纵两种拆。拆开以后，我们应该把所有的横边排序，所有的纵边也排序。横边排序规则： 1. 按行排序。 2. 行相等时按这一行的头坐标（线段左边端点第 8 页 共 25 页名师资料总结 - -

27、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 纵坐标）排序。3. 如果再相等就按线段右边端点纵坐标排序。这样就能够保证边的有序性，为下面做好铺垫。竖边类同。然后就是把所有的横边、纵边进行重叠处理。我们可以把它们分开处理。如果重叠（或临接），则两个仓库都不能扩张。经过上述处理，我们可以发现我们需要比较的边数已经大大减少。因此我们可以加上一些细节处理来加快速度。 例题 13 行星队列（USACO Con

28、test DEC05） 平面上给出 N （1=N=770 ）个点（坐标均为1.15000 之间的整数），要求求出有多少组三个点在一条直线上。 这道题拿到后，首先我们会用枚举的方法，写出一个O(N3)的程序。这可能可以过，但固然不是很好，在这里讲一下O(N2log2N)的方法。首先当然是读入操作。读入完毕后，我们这里用斜率来优化。所谓斜率，即为直线的倾斜角 的正切值。因为两点确定一条直线，故我们可以求出每两个点的直线的斜率。我们先用预处理，把斜率求出保存。当然，如求斜率时遇到除数为 0，则需另外处理（那就是与坐标轴平行的情况）。然后把每一个点出发到所有点的直线按斜率排序。排序完毕，我们只需要开i

29、、j二重循环去找这第三个点。因为两点确定一条直线，且每一点出发的直线都已经按斜率排序，故我们只需要用O(log2N) 的时间进行每一次查找。综合时间复杂度为 O(N2)*(log2N)=O(N2log2N) 。2.深度优先搜索深度优先搜索（ Depth First Search） ，是一种常见的搜索方法。我们在一般的搜索解题中， 往往要找的是一棵答案树。 比如某道题目中， 我们有这样一棵答案树（文中是二叉的） ，我们要找到一条一条路径，使其能够到达节点 8。我们可以深度优先地去遍历。 比如先序遍历， 根据它的递归定义， 访问顺序为根-1-3-6-7-8，能很快地搜索出这样的一条路径。根123

30、456 78下面我们来介绍一下回溯法。 回溯法是一类适用广泛而形象的深度优先搜索算法。所谓回溯，就是“碰壁返回” 。通俗的说，也就是你按照一定的顺序去产生一条路径， 然后如果遇到了死路， 就折回一部分然后试探下一条路径。每一次第 9 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 生成的路径都需要经过判断是否到达最终目标。还是以上一棵树为例，我们首先一路通畅，根-1

31、-3-6，然后是死路。不符合，然后折回，到3，然后试探右边 7，然后左边死路，右边8 即为所求。这样，我们就得出了一类问题的通用解法深度优先搜索。这种方法由于答案树的递归定义，一般用递归来解决。 例题 1 四色图问题（宁波2005 高中组） 在绘制区域地图时，要求以国家为单位着色，所有相邻国家着不同颜色。试编写一程序实现如下功能：使用至多四种不同颜色对地图进行涂色 (每块涂一种颜色)，要求相邻区域的颜色互不相同，输出所有可能的涂色方案总数。国家数小于等于 10。 本题可用深度优先搜索来解决。首先，我们读入的是一个 邻接矩阵 。由于国家数小于等于10 ，所以我们最多要搜索 410=1048576

32、次，保证了不会超时，所以我们在接下来的搜索过程中，可以用回溯的方法枚举，进行相邻节点是否同色的判断即可。搜索的时候，如果当前点与相邻点的颜色相同则回溯， 否则继续深入搜索，如果找出一种方案，则记录并回溯。流程是这样的：1. 当前节点为 1 ；2. 当前节点的颜色代号加1；3. 如果当前节点不是1 则与相邻节点判断是否相同4.是：回溯5.不是：如果当前节点为n 6.是：记录并回溯；7.不是：搜索下一层；8. 直到回溯到第 0 个国家为止 例题 2 外星生命（TOJ1062 ） 地球上的科学家收到了来自外星的信号： 000023*000011=002093，科学家猜想这是某个外星人的年龄。但有人指

33、出，这些外星人好像不怎么聪明，因为23*11=253 ，而非2093 。但是科学家们发现，如果把000011 改成 00091 的话算式就成立了。他们认为这是接收信号的时候出了差错的缘故。 现在给你这样一个算式，问最少改动几个数字就能使得算式成立？（格式是?*?=?，忽略进位） 我们可以按位搜索，按照DFS 的顺序，求出一种方案。然后本着动态规划中的最优原理，以这个答案为基础，把新的分支搜索进行下一位的搜索。在这里我们引出 剪枝的概念。在本题中，我们在第n 步就已经比现有结果更差（需要更多的改进），这是我们就可以不用搜下去了，我们就退出本轮搜索，这个称为剪枝，我们剪的是答案树的枝。在搜索中，剪

34、枝一般都是很重要的， 如果没有剪枝， 我们就要搜索很多的节点，做很多的无用功以浪费时间，而剪枝避免了非常多的。不必要的搜索，大大提高了搜索的速度。 所以，剪枝在搜索中的地位是非常高的。如果学好了基础的第 10 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 搜索方法，再去掌握一定的剪枝，就能够用好搜索了。 例题 3 数的划分、放苹果（NOIP T2001-2 、P

35、OJ1664 ） 数的划分：将整数 n 分成 k 份，且每份不能为空， 任意两种分法不能相同(不考虑顺序)，例如：n=7，k=3，下面三种分法被认为是相同的：1，1，5；1，5，1；5，1，1。问有多少种不同的分法。 放苹果：把 M个同样的苹果放在N个同样的盘子里， 允许有的盘子空着不放，问共有多少种不同的分法？（用K 表示）5，1，1和 1，5，1 是同一种分法。1=M,N=10 数的划分： 很清楚，这是一道整数分解的问题。这种分解，较为直接的思路是递归。我们在本题可以采用深度优先搜索的方法。我们定义一个过程，使其反复递归穷举第1 份、第 2 份第 k份，然后寻找出可行的路径，时间复杂度O(

36、nk) 。这种方法思路十分便捷，但也许会超时。我们有两个很好的剪枝：剪枝 1 如果剩余的够不上最小的则剪去。这是显而易见的常理， 但是可以加快速度。 剪枝 2 枚举到剩余 1 个盘子时判断是否可行。也是加快速度的方法，使在题目所描述的n 和 k 的范围之中完全可行。重复的只算一种，我们怎么样处理有关重复的呢？我们可以引入一个参数min ，作为至少每一个要达到min ，顺序由小而大，逐层递归。综上所述，我们可以轻易写出一个优化过的递归搜索程序。放苹果： 我们只需要改变上题的一个小条件，把第一个盘子的最小搜索值设为 0。则就是从 0 搜索起，这个题目也迎刃而解了，毕竟几乎一样的题目 例题 4 跳棋

37、的挑战（USACO Training 1.1.4-1 ） 检查一个如下的 nn的跳棋棋盘，有 n 个棋子被放置在棋盘上，使得每行，每列，每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。 下面的 66的布局可以用序列2 4 6 1 3 5来描述，第 i 个数字表示在第i行的相应位置有一个棋子： 1234561 2 3 4 5 6 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请遍一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。 解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。 （6=n=13 ）这是一道在 USACO

38、中经典的题 Checker Challenge。在这题中，搜索的优化和一些特性的运用显得十分重要。第 11 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 分析这道题，我们首先看来就是一个经典的N 皇后问题。还有的是这道题先定了算法，只能采用回溯算法。N 皇后有它的构造方法，但是不适用。所以我们来看如何就此问题运用最一般的方法求解。我们对每一个限定条件进行分析。由

39、于每一行都不能有两个跳棋， 而跳棋有N 个，所以每一行必有一个跳棋。 由于它是要求每一行中跳棋的列，所以我们只需搜索每一个行就可以了。 根据分析， 横轴我们已经不需要考虑， 纵轴一共有 N条，型轴 2N-1 条，型轴也有 2N-1 条。然后我们可以递归求解。 如果符合条件， 就可以把这个棋子放上去， 三条轴都须记上；当回溯的时候，就必须把它撤除，然后求得总数。但是这种方法对于N=13时有致命弱点慢！经过测试，大约需要2 秒多才能出解。这个在时间上是承受不了的。这道题有个特性是值得我们利用的，那就是对称性。也就是说，需要搜N，我们只需搜 N 的一半。比如 13 ，我们只需搜到 6，然后根据对称性

40、把搜得的结果乘以2，然后再加上搜到的7 的结果。这样就轻松剪掉大约一半。然后我们就有了解题的步骤：先搜到三个解不记状态重新搜输出。这道题还有一个特性， 那就是旋转。 通过旋转还可以剪掉四分之一，但是似乎很麻烦，所以笔者没有去试验过。关于此题的其他方法， 详见其他书籍 （比如 启发式修补法 算法艺术与信息学竞赛 P195 ） 。 例题 5 骑士的游历 1、2 设有一个 n*m的棋盘，如下图，在棋盘上任一点有一个中国象棋马， 马走的规则为：1.马走日字 2. 马只能向右走 即如下图所示: 任务 1:当 N,M 输入之后, 找出一条从左下角到右上角的路径。（NOIP T97-3）任务 2:如果是 n

41、*n 的棋盘，取消马只能向右走的条件，找出一条路径使马能够不重复地遍历每一个点。 （ 竞赛例题解析）1. 题目也就是说， 马能够朝着四个方向前进。 而题目要求的是一条路径， 所以这道题是经典的深度优先的回溯算法。我们把四个方向用数组记录下来，然后就可以开始先用第一种方向生成一条路径，然后回溯，直到有一次点停留在目标顶点为止，输出路径。本题需要注意的是越界的判断与处理。2. 现在马摆脱了束缚， 可以朝着八个方向走了。 我们可以上小题所用的方法来处理这个问题。 在这个问题中， 我们所要研究的不仅仅是到达一个点，而是遍历棋盘。但是用哈希表判断是否到过的记录很麻烦，所以我们只要记录步数就可以了，直到走

42、过步为止。我们回溯之前，要先建立一张空棋盘，然后判断21n -第 12 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 要达到的是否是已经到过的， 如果是则回溯， 反之记录下来。 最后输出这张棋盘就可以了。 例题 7 卫星照片（USACO Contest NOV05） FJ 给他的农场买了 W*H 像素的卫星照片，希望找出最大的“连续的”（互相连接的）牧场。任何一

43、对像素， 一个像素如果能横向的或纵向的与属于这个牧场的另一个像素相连，这样的牧场称作是连续的。 每一张照片都数字化的抽象了，牧场区显示为“ *”，非牧场区显示为“. ”。下面是一个 10*5 的卫星照片样例： .*.* .*.* .*.*. .*.* .*.* 这张照片显示了大小分别为4、16、6 个像素的连续牧场区。 帮助 FJ 在他的每张卫星照片中找到最大的连续牧场。 在这里，我们介绍一种方法，称为FloodFill 。FloodFill是一种简单的染色法，通常译为种子填充法，一般用来求连续区域的面积等。我们在这里先介绍一下这种方法。FloodFill可以有 2 种方法实现。1. DFS。

44、使用普通 DFS 架构。先从一个点出发，向相连的方向（一般是四周）探寻，如果四周有相连的点，则继续递归探查下一个点的四周方向。不过这个需要避免的是搜索的重复，避免陷入死循环。2. BFS。使用普通 BFS 架构（下面会讲）。从一个点出发，向相连的方向扩展节点。这种方法有效避免了搜索的重复，且BFS 适用范围较广（比如限制步数等） ，是可以推荐的。但是BFS 编程比 DFS 略繁。在这道题中，我们采用DFS 来实现 FloodFill 。我们所需要做的一点细节处理是，每一个牧场区搜索到之后，就可以擦去，以避免搜索重复和死循环。 例题 8 房间问题（IOI94） 图示出了一张建筑平面图，编程计算

45、1、该建筑中有多少个房间； 2、最大的房间有多大； 3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。 该建筑分成*个方块（m 50，n50） ，每个方块可有04 堵墙（0 表示无墙） 。 这道题也是典型的FloodFill 。这里的 FloodFill也是可以用 DFS/BFS 做的。为了避免重复计算，我们可以用一个二维数组记录是否探查过这个地方，分成的是第几个房间。第 13 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 25 页 - -

46、 - - - - - - - 搜索基础 2006/01/23版 By XT 我们在 FloodFill中就可以完美解决第1、2 问，接下来就是第 3 个问题了。我们可以枚举每一条边， 来试验是否拆除的面积比原先记录的大（两边面积之和） 。这里我们只需要用到穷举。我们在这里能够采用FloodFill作为架构。试想，如果把FloodFill推广到无向图、有向图呢？有兴趣的读者可以自行研究，此处不再赘述。 例题 9 谷仓安全保护（USACO Contest NOV05） FJ 给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一个有效的密码。一个有效的密码由L（3 = L = 15 ）个小

47、写字母（来自传统的拉丁字母集a.z）组成，至少有一个元音（a, e, i, o, u），至少两个辅音（除去元音以外的音节） ，并且有按字母表顺序出现的字母(例如，abc 是有效的，而bac 不是) 。 给定一个长度 L 和 C个小写字母，写一个程序，打印出所有的长度为L、能由这些字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。 这道题可以用比较基础的DFS 回溯解决。我们可以用一个字符串来当作答案数组（一个比较巧妙的方法），然后层层递归产生新的答案。当深度到达L 时，判断是否满足元、辅音的要求，再输出。然后回溯（ PASCAL 中每一次回溯要去掉“尾巴” ，C/C+ 由于语言优势不

48、必去除） ，以避免重复运算浪费时间。这道题具体的搜索方法与前面我们所讲的一些题目别无二样，可见搜索算法的通用性很强。由于这道题比较简单，在此也不详细说明了。 例题 10 水碗（USACO Contest JAN06） 有 20 个碗，正反状态用0、1 表示（正=0，反=1），给出一组碗的状况，要求用最少的操作次数使碗全部朝正面。一次操作就是以一个碗为中心， 翻转它的左边、右边以及它自己。 （如果一个碗的左（右）边没有则不需要翻转这个碗的左（右）边） 这道题拿到，需要一些敏锐的观察力。我们可以进行一些位处理。首先，我们可以把 20 个碗的 0、1 值从二进制转化为一个长整数。可以发现，这个长整数

49、的范围在 0.1048575之间，因此共 220种状态。这为我们下文的搜索做好了铺垫。我们转换完毕， 然后我们考虑怎样从一个状态值翻动以产生新的状态值。我们考虑多种位操作。其中异或（Pascal 中是 xor ，C/C+中是 ）操作无疑是最好的。我们可以举个例子来说明怎么样翻转。就以样例数据作为例子。我们把原状态转化为二进制。0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3484 然后，我们假设要以左起第三个为中心翻转。则做异或运算：0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3484 0 1 1 1 0 0 0 0 0 0

50、 0 0 0 0 0 0 0 0 0 0 14 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3474 是不是很神奇呢？我们可以把每一个点为中心翻转的异或操作的数保存起来。产生规则：第 14 页 共 25 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 25 页 - - - - - - - - - 搜索基础 2006/01/23版 By XT 3（i=1 ）7（i=2 ）Maski= Maski-1*2（3=i 乙； （6）乙- 甲。