noi导刊枚举与搜索

《noi导刊枚举与搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、枚举与搜索讲稿长沙市雅礼中学朱全民有关搜索的NOIP试题神经网络(2003)---宽搜侦探推理(2003)---枚举与优化传染病控制(2003)---深搜与优化虫食算(2004)---深搜与优化火柴棒等式(2008)---简单枚举双栈排序(2008)---二分图的搜索靶形数独(2009)---深搜与优化简单枚举法所谓枚举，即对可能的解集合一一列举。解题思路为：首先确定可能的解集合抽象出解包含的参数，确定每个参数的数据范围对解的每个参数的数据范围采用循环语句一一枚举对每次枚举，根据题意给定的条件判定是否解，是否是最优解。火柴棒等式给你n根火柴棍，你可以拼出多少个形如“A+B=

2、C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）3.n根火柴棍必须全部用上分析0~9的数字所用的火柴数：6,2,5,5,4,5,6,3,7,6对于N<=24，去掉+，=，实际上数字只有20根火柴。首先考虑解集合，因为最多为20根火柴组成数字：不可能为10个1；不可能8个1，1个4；不可能为7个1，2个7或1个0；…..C不会超过1000枚举答案设F(I)表示数为I时的火柴棍数FORA=0TO1

3、000DOIFF(A)

4、推荐的算法分为两步：1．预处理每个人的每一句话，并把它们分类处理；2．枚举罪犯和当前星期几，找出所有可能发生的情况。下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述可以发现语句可分为三类：分析1．指明i是否是罪犯的语句；2．指明今天是星期d的语句；3．没有意义的语句(不符合格式要求)。我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就

5、必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。1．没说任何一句有意义的话；2．只说真话；3．只说假话；4．既说真话也说假话。分析需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。最后，如果对于罪犯i存在一个d使得当前情况是可能的，我们就说i就是可能的罪犯。[时间效率]O(MP

6、Day

7、)（其中Day={Sunday，M

8、onday,Tuesday,Wednesday,Thursday,Friday,Saturday}）优化我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期d的总人数，于是改进后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有的话

9、，再用O(

10、Day

11、)的时间枚举星期几。这样，改进后算法的复杂度就是O(m(p+

12、Day

13、))。那么我们可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体