基础算法策略枚举

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,基础算法策略,枚举策略,枚举策略的基本思想,枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。,枚举,策略,解题思路为：,首先确定可能的解集合；,抽象出解包含的参数，确定每个参数的数据范围；,对解的每个参数的数据范围采用循环语句一一枚举；,对每次枚举，根据题意给定的条件判定是否解，是否是最优解。,设某个问题的解所涉及的参数（状态参数）有n个，分别表示为a,1，,a,2，,a,n，,其中a,i1,状态元素a,i,的最小值；a,ik,状态元素a,i,的最大值(1in)，即a,11,a,1,a,1k,，a,21,a,2,a,2k,， a,i1,a,i,a,ik,，a,n1,a,n,a,nk,for a,1,a,11,to a,1k,do,fo a,2,a,21,to a,2k,do ,for a,i,a,i1,to a,ik,do ,for a,n,a,n1,to a,nk,do,if 状态(a,1,，a,i,，a,n,)满足检验条件,then 输出问题的解；,枚举策略,枚举法常用于解决,“,是否存在,”,或,“,有多少种可能,”,等类型的问题。例如，求解不定方程的问题就可以采用列举法。,枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。,枚举,策略,的优化,枚举算法的时间复杂度：,状态总数*单个状态的耗时,主要优化方法：, 减少状态总数, 降低单个状态的考察代价,优化过程从以下几个方面考虑：, 枚举对象的选取, 枚举方法的确定, 采用局部枚举或引进其他算法,枚举算法的应用,若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：,（13）10=（1101）2， 13为B类数；,（10）10=（1010）2 10为B类数；,（24）10=（11000）2 24为A类数；,程序要求：求出11000之中（包括1与1000），全部A、B两类数的个数。,例题1：二进制数的分类,【分析】,此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。,具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为11000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。,例题2：01统计,将问题的数据规模扩充到求1到m（m S1 + 2,可以取S0 = 4 S1 = 0；S0 = 3 S1 = 1.这一类数中的A类数个数：(4 4) + (3 4),数字形式为(10xxxxx),2,设5个填数位置填0的个数为S0，填1的个数为S1，则S0 + S1 = 5;,若为A类数，则S0 + 1 S1 + 1,可以取S0 = 5 S1 = 0；S0 = 4 S1 = 1；S0 = 3 S1 = 2.这一类数中的A类数个数： (,5,5,) + (,4,5,) + (,3,5,),数字形式为,(0xxxxxx)2,这一类数字的分析与前几类略有不同，因为前几类二进制数的位数都是,7,，而这一类数还需对位数进行讨论：,（,1,）,1,位数，即,(1)2,，不是,A,类数,（,2,）,2,位数，即,(1x)2,，,(10)2,和,(11)2,都不是,A,类数,（,3,）,3,位数，即,(1xx)2,，,A,类数个数为,(,2,2,) =1,（,4,）,4,位数，即,(1xxx)2,，,A,类数个数为,(,3,3,) =1,（,5,）,5,位数，即,(1xxxx)2,，,A,类数个数为,(,4,4,)+ (,3,4,)=5,（,6,）,6,位数，即,(1xxxxx)2,，,A,类数个数为,(,5,5,) + (,4,5,) =6,最后的答案是,1 + 5 + 16 + (1 + 1 + 5 + 6) = 35,对于一般情况：,设m的二进制数为a,1,a,2,a,n,(其中a,1,为最高位)，设a,1,a,2,a,k,中0的个数为S0(k)，1的个数为S1(k)，设b,1,b,2,b,n,为1m的一个数，此时可分为：,第一大类，当b1=1时，可根据前缀的不同来分类统计；,第二大类，当b1=0时，可根据二进制数位数的不同来分类统计。,1,1,x,x,x,x,1 2 i n,最高位,最低位,左数第i位,设左数第i位为1，后n-i位（画X的位）中有j个0，记前k位（从左数）中0的个数为S0(k)，1的个数为S1(k)，（可预先求出），则前缀为(10XX)2的A类数共有,0,个A类数，,其中S0(i-1)+1+jS1(i-1)+n-i-j,第一大类：,j个0,要对从第2n位上的每一个1进行上述统计，即第一类的最终结果应为：,第一大类：,条件：,当第i位为1，且S0(i 1) + 1 + j S1(i 1) + n - i j,第二大类：,0,0,1,x,x,x,x,1 2 i n,最高位,最低位,左数第i位,如果左数第i位为1，即为n-i+1位的二进制数，其中的A类数共有：,个，其中j为后n-i位中0的个数，且满足后n-i+1位中0的个数多于1的个数。,第二大类：,故第二大类总的A类数个数为：,以上两大类统计的均是小于m的A类数，如果m本身是A类数，那么ans3 = 1，否则ans3 = 0。,问题的解即为ans1 + ans2 + ans3。,根据二进制数的前缀来分类是合理的，既没有重复也没有遗漏。当,m,的二进制数长度为,n,时，最多有,2n,种类型，即,种，比直接穷举,m,个数有了很大进步。,总结：,枚举对象的确定,在一个8*8的棋盘上，有一个国王和若干个骑士。其中，国王走一字步，骑士走马步。玩家必须选择一个骑士跟国王一起行动，其他的骑士则自己单独走到集中点。骑士和国王一起走的时候，只算一个人走的步数。求一个点，使所有的骑士和国王相聚在这个点上的所走的步数最少。,例题3：圆桌骑士（IOI98，usaco3.3）,此题可从3个方面考虑：分治、枚举、数学方法。,由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举对象有：,分析,1、最后的汇聚点。,2、国王与背他的骑士的汇聚点。,3、背国王的骑士。,国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。 这样我们估算一下时间为O（8*8*8*8*63）=O（36*104），完全可以承受。,另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。,分析,图中红色格子为假设的集结点，绿色格子为假设的某骑士跟王接头地点，蓝色的Q为前去背王的人，增量为黑色路线步数的和减去蓝色虚线的步数。,算法流程：,disx1，y1，x2，y2-（x1，y1）（x2，y2）之间的距离。,For I：=1 to 8 do枚举汇合点,For j：=1 to 8 do begin,All ：=所有骑士到这一点的和；,Best:=min(best,all+国王到汇聚点的步数),For x：=1 to 8 do 枚举武士国王的相会点,For y：=1 to 8 do begin,For kk：=1 to k do 枚举与国王结合的武士,If disknightkk.x,knightkk.y,x,ymin then begin,Min:= disknightkk.x,knightkk.y,x,y;,Mink:=k;,End;,End；,Now:= all-mink武士走到汇合点的距离+ mink武士走到汇聚点的距离+ 国王走到汇聚点的距离+从汇聚点到汇合点的距离；,Best：=min（best，now）,End；,局部枚举,某城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。,例题4：新年好,佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？,e,a,b,c,d,1,分析,算法框架：,（1）用5次最短路，计算出6个点两两之间的距离,（2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。,其它实例：火柴棒等式（,NOIP2008）,给你n(,n=0）,3. n根火柴棍必须全部用上,分析,09的数字所用的火柴数：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时的火柴棍数,FOR A=0 TO 1000 DO,IF F(A)best then bestsum；,这个算法枚举状态为O（n,9,）,从减少重复计算入手,记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。,考察过程改为 ：,for xx1 to x2 do 计算长方体的体积,for y,y1 to y2 do sumsum+mapx，y，z2；,if sumbest then bestsum； 调整最优解,由于利用了计算出的结果，整个算法的时间复杂度降为O（n,8,）。,3、提取恰当的信息,上述考察实际上求出z轴坐标为z,2,的平面中矩形（,x,1,，y,1,，x,2,，y,2,）的数和。我们将这个数和记为value(a),value(A)=value(ABCD)+value(B)-value(BC)-value(BD),这就启发我们用另一种方法表示立方体的信息：设recx，y，z表示z轴坐标为z的水平面中矩形（1,，1，x，y,）的数和。,z轴坐标为z的水平面中,左上角为（x,1,，y,1,）、右下角为（x,2,，y,2,）的矩阵的数和为,recx,2,，y,2,，z+ recx,1,，,y,1,，z-recx,2,，,y,1,，z-recx,1,，y,2,，z,Rec数组可以在输入数据的同时计算。,这样，考察过程就可以改为,sumsum+recx,2,，y,2,，z,2,+recx,1,，,y,1,，z,2,-recx,2,，,y,1,，z,2,-recx,1,，y,2,，z,2,；,if sumbest then best,sum；,时间复杂度降为O（n,6,）。,如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设,total(z)以z轴坐标为z的平面为下底面的长方体的最大数和,Total(z)=,0,Max(0,total(z-1)+recx2,y2,z+recx1-1,y1-1,z),-recx2,y1-1,z-recx1-1,y2,z),z=0,z0,3,-2,-2,4,6,a,b-a,b,算法框架,for x11 to n do 枚举所有可能的子平面,for x21 to n do,for y11 to n do,for y21 to n do,begin,total0；以（x1,y1）为左上角、（x2,y2）为右下上角）,for z1 to n do 枚举长方体b下底面的z轴坐标,begin,totalmax total，0 + recx2，y2，z + recx1-1，y1-1，z,- recx2，y1-1，z - recx1-1，y2，z；,计算以z为下底面的长方体b的最大数和,if total best then besttotal； 调整最优解,end；,end；,这一改进使得考察的状态整数降为n,5,