B班day1上午枚举与搜索教案朱全明

noip 学习资料

枚举与搜索讲稿长沙市雅礼中学 朱全民

noip 学习资料

有关搜索的NOIP试题 有关搜索的 试题 神经网络 神经网络(2003)---宽搜 宽搜 神经网络 侦探推理 侦探推理(2003)---枚举与优化 侦探推理 枚举与优化 传染病控制 传染病控制(2003)---深搜与优化 传染病控制 深搜与优化 虫食算 虫食算(2004)---深搜与优化 虫食算 深搜与优化 火柴棒等式 火柴棒等式(2008)---简单枚举 火柴棒等式 简单枚举 双栈排序 (2008)---二分图的搜索 双栈排序 二分图的搜索 靶形数独 靶形数独(2009)---深搜与优化 靶形数独 深搜与优化

noip 学习资料

简单枚举法所谓枚举，即对可能的解集合一一列举。 所谓枚举，即对可能的解集合一一列举。 解题思路为： 解题思路为： 首先确定可能的解集合 抽象出解包含的参数，确定每个参数的数 抽象出解包含的参数， 据范围 对解的每个参数的数据范围采用循环语句 一一枚举 对每次枚举，根据题意给定的条件判定是 对每次枚举， 否解，是否是最优解。 否解，是否是最优解。

noip 学习资料

火柴棒等式 给你 根火柴棍，你可以拼出多少个形如“A+B=C”的等式？ 给你n根火柴棍，你可以拼出多少个形如“ 的等式？ 根火柴棍 的等式 等式中的A、 、 是用火柴棍拼出的整数 若该数非零， 是用火柴棍拼出的整数( 等式中的 、B、C是用火柴棍拼出的整数(若该数非零， 则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示 )。用火柴棍拼数字 的拼法如图所示： 则最高位不能是 )。用火柴棍拼数字 的拼法如图所示：

注意： 注意： 1. 加号与等号各自需要两根火柴棍 2. 如果 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、 视为不同的等式( 、 、 , 与 视为不同的等式 C>=0) ) 3. n根火柴棍必须全部用上 根火柴棍必须全部用上

noip 学习资料

分析 1. 2. 3. 4. 5. 0~9的数字所用的火柴数：6,2,5,5,4,5,6,3,7,6 的数字所用的火柴数： 的数字所用的火柴数 对于N<=24,去掉 ，=,实际上数字只有 根火 对于 ，去掉+, ,实际上数字只有20根火 柴。 首先考虑解集合，因为最多为20根火柴组成数字 根火柴组成数字： 首先考虑解集合，因为最多为 根火柴组成数字： 不可能为10个1; 不可能为10个1; 不可能8个 ， 个 ； 不可能 个1,1个4; 不可能为7个 ， 个 或 个 ； 不可能为 个1,2个7或1个0; ….. C不会超过 不会超过1000 不会超过

noip 学习资料

枚举答案 设F(I)表示数为 时的火柴棍数 表示数为I时的火柴棍数 表示数为 FOR A=0 TO 1000 DO IF F(A)<N-4 THEN FOR B=1000-A DO IF F(A)+F(B)+F(A+B)=N-4 THEN 输出； 输出；

noip 学习资料

侦探推理

证词中出现的其他话，都不列入逻辑推理的内容。 证词中出现的其他话，都不列入逻辑推

理的内容。 明明所知道的是，他的同学中有N个人始终说假话， 明明所知道的是，他的同学中有N个人始终说假话，其余的 人始终说真话。 人始终说真话。 现在， 现在 ， 明明需要你帮助他从他同学的话中推断出谁是真正 的凶手，请记住，凶手只有一个！ 的凶手，请记住，凶手只有一个！ 要求： 要求： 判断谁是罪犯？ 判断谁是罪犯？

noip 学习资料

分析 这道题的关键点是“如何能够快速正确实现出来” ,事 这道题的关键点是“如何能够快速正确实现出来” 实上这道题对编码能力的要求要大于对算法本身的要求。 实上这道题对编码能力的要求要大于对算法本身的要求。 由于这道题的数据范围并不是很大，但需要进行“ 由于这道题的数据范围并不是很大，但需要进行“字符串 处理”这种比较麻烦的工作， 处理”这种比较麻烦的工作，因此在比赛时就可以采用效 率低一些的枚举算法来换取编码上的简单。 率低一些的枚举算法来换取编码上的简单。 推荐的算法分为两步： 推荐的算法分为两步：

1.预处理每个人的每一句话，并把它们分类处理； 预处理每个人的每一句话，并把它们分类处理； 2.枚举罪犯和当前星期几，找出所有可能发生的情况。 枚举罪犯和当前星期几，找出所有可能发生的情况。下面我们来逐步细化一下每一步的算法，对于第一步， 下面我们来逐步细化一下每一步的算法，对于第一步，我们 希望的是把一些杂乱的不好处理的“字符串信息” 希望的是把一些杂乱的不好处理的“字符串信息”转化为 相对比较好处理的信息。为此，我们可以通过把“信息” 相对比较好处理的信息。为此，我们可以通过把“信息” 进行分类的方法使得对于每一类信息， 进行分类的方法使得对于每一类信息，更加方便的处理 即我们可以用一个或者几个变量来表示), ),由题目描述 (即我们可以用一个或者几个变量来表示),由题目描述 可以发现语句可分为三类： 可以发现语句可分为三类：

noip 学习资料

分析1.指明i是否是罪犯的语句； 指明i是否是罪犯的语句； 2.指明今天是星期d的语句； 指明今天是星期d的语句； 没有意义的语句(不符合格式要求) 3.没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划 分到第三类中去， 分到第三类中去，这样在处理每个语句的时候就必须要考 虑该语句是否符合格式要求，通过以上的处理， 虑该语句是否符合格式要求，通过以上的处理，我们对于 每一个语句用几个变量就可以表示了。 每一个语句用几个变量就可以表示了。 对于第二步的细化，我们在枚举完

罪犯和当前星期几之后， 对于第二步的细化，我们在枚举完罪犯和当前星期几之后， 就可以比较方便的判断每一句话的真伪了， 就可以比较方便的判断每一句话的真伪了，这样我们再根 据每个人所说的话把人进行分类。 据每个人所说的话把人进行分类。

1.没说任何一句有意义的话； 没说任何一句有意义的话； 2.只说真话； 只说真话； 3.只说假话； 只说假话； 4.既说真话也说假话。 既说真话也说假话。

noip 学习资料

分析 需要注意的是，对于第一类人我们既可以把他当成说真话 需要注意的是， 也可以把他当成说假话的，而如果第四类人存在的话， 的，也可以把他当成说假话的，而如果第四类人存在的话， 那么从他本身就可以推出矛盾了。 那么从他本身就可以推出矛盾了。 最后，如果对于罪犯i存在一个d使得当前情况是可能的， 最后，如果对于罪犯i存在一个d使得当前情况是可能的， 我们就说i就是可能的罪犯。 我们就说i就是可能的罪犯。 时间效率] [时间效率] O(MP|Day|) (其中Day={Sunday,Monday, Tuesday, 其中Day={Sunday, Day={Sunday Saturday}) Wednesday, Thursday, Friday, Saturday})

noip 学习资料

优化 我们可以发现在对罪犯和当前星期几进行“双重枚举”时， 我们可以发现在对罪犯和当前星期几进行“双重枚举” 进行了很多重复的操作，于是我们想到， 进行了很多重复的操作，于是我们想到，能不能不枚举是当 前星期几？这样我们把这类语句与判断罪犯的语句分离， 前星期几？这样我们把这类语句与判断罪犯的语句分离，可 以先由判断罪犯的语句中确定一部分人肯定说真话， 以先由判断罪犯的语句中确定一部分人肯定说真话，一部分 人肯定说假话， 人肯定说假话，剩下的一部分人就要根据他所说的当前星期 几的语句来判断了， 几的语句来判断了，首先我们假设所有人判断星期的语句不 自相矛盾， 自相矛盾，这样每个人将在判断这类问题里面至多有一个答 我们便可以统计判断当前是星期d的总人数， 案，我们便可以统计判断当前是星期d的总人数，于是改进 后的算法对于每一个可能的罪犯，先用O(p) O(p)的时间处理所有 后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有 的话，再用O(|Day|)的时间枚举星期几。这样， O(|Day|)的时间枚举星期几 的话，再用O(|Day|)的时间枚举星期几。这样，改进后算法 的复杂度就是O(m(p+|Day|)) O(m(p+|Day|))。 的复杂度就是O(m(p+|Day|))。 那么我们可不可以再进一步，把算法优化到线性？这里面可 那么我们可不可以再进一步，把算法优化到线性？ 以比较明确地告诉大家，是可以做到的， 以比较明确地告诉大家，是

可以做到的，具体的算法类似于 上面的按照语句的种类分离语句，只是分离得更细， 上面的按照语句的种类分离语句，只是分离得更细，处理得 更复杂，在这里就不做赘述，留给大家思考。 更复杂，在这里就不做赘述，留给大家思考。

noip 学习资料

立方体问题现有一个棱长为n的立方体，可以分成 现有一个棱长为 的立方体，可以分成n3个1*1*1的 的立方体 的 单位立方体。每个单位立方体都有一个整数值。 单位立方体。每个单位立方体都有一个整数值。n3 个单位立方体的数和不会超过longint范围。现在要 范围。 个单位立方体的数和不会超过 范围 求在这个立方体找到一个包含完整单位立方体的长 方体，使得该长方体内所有单位立方体的数和最大。 方体，使得该长方体内所有单位立方体的数和最大。 输入： 的数字矩阵， 输入： n(1≤n≤20);n个n*n的数字矩阵，每个数 ≤ ≤ ; 个 的数字矩阵 字矩阵代表一层， 字矩阵代表一层，每个数字代表一个单位立方体的 整数值， 整数值，-999≤单位立方体的整数值≤999 ≤单位立方体的整数值≤ 输出： 输出：长方体的数和

noip 学习资料

“简单”枚举过程 简单”1、枚举所有可能的平面 、 for x1←1 to n do for x2←1 to n do for y1←1 to n do for y2←1 to n do for z1←1 to n do for z2←1 to n do 考察状态( , , , , , ); 考察状态(x1,y1,z1,x2,y2,z2); 2、考察状态(x1,y1,z1,x2,y2,z2)过程如下 、考察状态( , , , , , ) sum←0; ; for x←x1 to x2 do {计算长方体的体积 计算长方体的体积} 计算长方体的体积 for y←y1 to y2 do for z←z1 to z2 do sum←sum+map[x,y,z]; {调整最优解 调整最优解} , , ; 调整最优解 if sum>best then best←sum; ; 这个算法枚举状态为 (n9) 这个算法枚举状态为O(

noip 学习资料

从减少重复计算入手 记录先前考察的结果。在统计长方体2时，只要将长方体 的统计结果 记录先前考察的结果。在统计长方体 时 只要将长方体1的统计结果 加上长方体3就可以了，而不必按上述算法那样重新进行计算。 加上长方体 就可以了，而不必按上述算法那样重新进行计算。 就可以了

考察过程改为 ： for x←x1 to x2 do {计算长方体的体积 计算长方体的体积} 计算长方体的体积 for y←y1 to y2 do sum←sum+map[x,y,z2]; , , ; if sum>best then best←sum; {调整最优解 调整最优解} ; 调整最优解 由于利用了计算出的结果，整个算法的时间复杂度降为O( 由于利用了计算出的结果，整个算法的时间复杂度降为 (n8)。

noip 学习资料

3、提取恰当的信息上述考察实际上求出z轴坐标为z 的平面中矩形( 上述考察实际上求出z轴坐标为z2的平面中矩形

(x1, y1,x2,y2)的数和。我们将这个数和记为value(a) 的数和。我们将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)value(A)=value(ABCD)+value(B)-value(BC)value(BD)

这就启发我们用另一种方法表示立方体的信息： 这就启发我们用另一种方法表示立方体的信息：设 rec[x, z]表示 轴坐标为z的水平面中矩形( 表示z rec[x,y,z]表示z轴坐标为z的水平面中矩形(1, 1,x,y)的数和。 , , )的数和。

轴坐标为z 的水平面中左上角为 左上角为( z 轴坐标为 z 的水平面中 左上角为 ( x1 , y1 ) 、 右下 角 为 ( x2 , y2 ) 的矩阵 的数 和为 rec[x2 , y2 , z]+ z]z]rec[x1,y1,z]-rec[x2,y1,z]-rec[x1,y2,z]

noip 学习资料

Rec数组可以在输入数据的同时计算 Rec数组可以在输入数据的同时计算 fillchar(rec,size(rec), fillchar(rec,size(rec),0);{rec数组初始化} {rec数组初始化} 数组初始化 for z←1 to n do ← for x←1 to n do ← for y←1 to n do ← begin read(map[x, read(map[x,y,z]); z]); {输入z平面上(x,y)中的数} 输入z平面上(x,y)中的数} {逐层输入信息 逐层输入信息} 逐层输入信息 {逐行输入 平面的信息 逐行输入z平面的信息 逐行输入 平面的信息} {逐列输入 平面上x行的信息 逐列输入z平面上 行的信息} 逐列输入 平面上 行的信息

(x=1)and(y=1 计算z平面上以( 为左上角、 x,y)为右下角的矩形的数和} if (x=1)and(y=1) {计算z平面上以(1,1)为左上角、(x,y)为右下角的矩形的数和} then rec[1,1,z]←map[1,1,z] rec[1 z]←map[1 else if y=1 then rec[x,y,z]←rec[x-1,n,z]+map[x,y,z] y=1 rec[x, z]←rec[xz]+map[x, rec[x, z]←rec[x, z]+map[x, z]; else rec[x,y,z]←rec[x,y-1,z]+map[x,y,z]; end; end;{for}

这样， 这样，考察过程就可以改为 sum←sum+rec[x2,y2,z2]+rec[x1,y1,z2]-rec[x2,y1,z2]-rec[x1,y2,z2]; best←sum; if sum>best then best←sum; 时间复杂度降为O 时间复杂度降为O(n6)。

noip 学习资料

的数和是负数， 如果长方体 a 的数和是负数 ， 则长方体 a 的计算 结果废弃， 结果废弃 ， 考察长方体 b-a 。 因为长方体 b 的数 的数和， 和 = 长方体 b-a 的数和 + 长方体 a 的数和 ， 由于长 方体 a 的数和为负， 长方体 b-a 的数和一定大于 的数和为负 ， 的数和。由此可见， 等于长方体b的数和。由此可见，在累计长方体 数和的时候， 数和的时候 ， 只要由上而下地枚举长方体下底 轴坐标即可。 面的z轴坐标即可。设 total(z)—— 以 z 轴坐标为 z 的平面为下底面的长 方体的最大数和0 total ( z ) = max(0, total ( z 1)) + rec[ x2 , y2 , z ] + rec[ x1 1, y1 1, z ] rec[ x2 , y1 1, z ] rec[ x1 1, y2 , z ] z=0 z>0

noip 学习资料

算法框架for x1←1 to n do {枚举

所有可能的子平面 枚举所有可能的子平面} 枚举所有可能的子平面 for x2←1 to n do for y1←1 to n do for y2←1 to n do begin total←0;{以(x1,y1)为左上角、( ;以 )为左上角、(x2,y2)为右下上角)} )为右下上角) 、( for z←1 to n do {枚举长方体 下底面的z轴坐标 枚举长方体b下底面的 轴坐标} 枚举长方体 下底面的 轴坐标 begin total←max {total,0} + rec[x2,y2,z] + rec[x1-1,y1-1,z] , , , , , - rec[x2,y1-1,z] - rec[x-1-1,y2,z]; , , , , ; {计算以 为下底面的长方体b的最大数和 计算以z为下底面的长方体 的最大数和} 计算以 为下底面的长方体 的最大数和 if total> best then best←total; {调整最优解 ； 调整最优解} 调整最优解 end; ; end; ; 这一改进使得考察的状态整数降为n5 这一改进使得考察的状态整数降为

noip 学习资料

深度优先搜索 深度优先搜索算法是搜索中的一种控制策略，但 深度优先搜索算法是搜索中的一种控制策略， 与枚举法不同的是，它是从初始状态出发， 与枚举法不同的是，它是从初始状态出发，运用 题目给出的条件、规则，按照深度优先 深度优先的顺序扩 题目给出的条件、规则，按照深度优先的顺序扩 展所有可能情况， 展所有可能情况，当所有可能情况都探索过且都 无法到达目标的时候，再回退到上一个出发点， 无法到达目标的时候，再回退到上一个出发点， 继续探索另一个可能情况， 继续探索另一个可能情况，这种不断回头寻找目 标的方法也称为“回溯法” 标的方法也称为“回溯法”。 深度搜索是求解特殊型计数题或较复杂的枚举题 中使用频率最高的一种算法。 中使用频率最高的一种算法。

noip 学习资料

深度搜索算法的几个重要因素 (1) 状态 作为递归的值参。 状态: 作为递归的值参。 (2) 边界条件 作为递归的结束条件，通常以 边界条件: 作为递归的结束条件， 深度结束。 深度结束。 (3) 递归范围 作为 循环的初值和终值。 递归范围: 作为for循环的初值和终值 循环的初值和终值。 (4) 约束条件 满足解的条件。 约束条件: 满足解的条件。 (5) 最优性要求：满足最优解的条件。 最优性要求：满足最优解的条件。

noip 学习资料

深度搜索的基本框架procedure dfs(当前状态 ； 当前状态); 当前状态 begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果；exit;{回溯 记下最优结果； 回溯} ; 回溯 end; ; for i←算符最小值 to 算符最大值 do begin 算符最小值 算符i作用于当前状态，扩展出一个子状态； 算符 作用于当前状态，扩展出一个子状态； 作用于当前状态 标记子状态路径； 标记子状态路径； if (子状态满足约束条件 and (子状

态满足最优性要求 子状态满足约束条件) 子状态满足最优性要求)then 子状态满足约束条件 子状态满足最优性要求 dfs(子状态 ； 子状态); 子状态 恢复子状态路径； 回溯 回溯} 恢复子状态路径； {回溯 end; ; end; ;

本文来源：https://www.bwwdw.com/article/tkf1.html