NOI导刊枚举与搜索.ppt

枚举与搜索讲稿 长沙市雅礼中学 朱全民,有关搜索的NOIP试题,神经网络(2003)-宽搜 侦探推理(2003)-枚举与优化 传染病控制(2003)-深搜与优化 虫食算(2004)-深搜与优化 火柴棒等式(2008)-简单枚举 双栈排序 (2008)-二分图的搜索 靶形数独(2009)-深搜与优化,简单枚举法,所谓枚举，即对可能的解集合一一列举。 解题思路为： 首先确定可能的解集合 抽象出解包含的参数，确定每个参数的数据范围 对解的每个参数的数据范围采用循环语句一一枚举 对每次枚举，根据题意给定的条件判定是否解，是否是最优解。,火柴棒等式,给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：,注意： 1. 加号与等号各自需要两根火柴棍 2. 如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C=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)N-4 THEN FOR B=1000-A DO IF F(A)+F(B)+F(A+B)=N-4 THEN 输出；,侦探推理,证词中出现的其他话，都不列入逻辑推理的内容。 明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真话。 现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！ 要求： 判断谁是罪犯？,分析,这道题的关键点是“如何能够快速正确实现出来” ，事实上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行“字符串处理”这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。 推荐的算法分为两步： 1预处理每个人的每一句话，并把它们分类处理； 2枚举罪犯和当前星期几，找出所有可能发生的情况。 下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述可以发现语句可分为三类：,分析,1指明i是否是罪犯的语句； 2指明今天是星期d的语句； 3没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。 对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。 1没说任何一句有意义的话； 2只说真话； 3只说假话； 4既说真话也说假话。,分析,需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。 最后，如果对于罪犯i存在一个d使得当前情况是可能的，我们就说i就是可能的罪犯。 时间效率 O(MP|Day|) （其中Day=Sunday，Monday, Tuesday, Wednesday, Thursday, Friday, Saturday）,优化,我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期d的总人数，于是改进后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有的话，再用O(|Day|)的时间枚举星期几。这样，改进后算法的复杂度就是O(m(p+|Day|)。 那么我们可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。,现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。 输入： n(1n20)；n个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值，-999单位立方体的整数值999 输出：长方体的数和,立方体问题,“简单”枚举过程,1、枚举所有可能的平面 for x11 to n do for x21 to n do for y11 to n do for y21 to n do for z11 to n do for z21 to n do 考察状态（x1，y1，z1，x2，y2，z2）； 2、考察状态（x1，y1，z1，x2，y2，z2）过程如下 sum0； for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do for zz1 to z2 do sumsum+mapx，y，z； 调整最优解 if sumbest then bestsum； 这个算法枚举状态为O（n9）,从减少重复计算入手,记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。 考察过程改为 ： for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do sumsum+mapx，y，z2； if sumbest then bestsum； 调整最优解 由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。,3、提取恰当的信息 上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)-value(BD) 这就启发我们用另一种方法表示立方体的信息：设recx，y，z表示z轴坐标为z的水平面中矩形（1，1，x，y）的数和。 z轴坐标为z的水平面中左上角为（x1，y1）、右下角为（x2，y2）的矩阵的数和为recx2，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，z,Rec数组可以在输入数据的同时计算 fillchar(rec，size(rec)，0)；rec数组初始化 for z1 to n do 逐层输入信息 for x1 to n do 逐行输入z平面的信息 for y1 to n do 逐列输入z平面上x行的信息 begin read(mapx，y，z)； 输入z平面上（x,y）中的数 if (x=1)and(y=1) 计算z平面上以（1，1）为左上角、（x,y）为右下角的矩形的数和 then rec1，1，zmap1，1，z else if y=1 then recx，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z； end；for 这样，考察过程就可以改为 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y2，z2； if sumbest then bestsum； 时间复杂度降为O（n6）。,如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设 total(z)以z轴坐标为z的平面为下底面的长方体的最大数和,算法框架,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 - recx-1-1，y2，z； 计算以z为下底面的长方体b的最大数和 if total best then besttotal； 调整最优解 end； end； 这一改进使得考察的状态整数降为n5,深度优先搜索,深度优先搜索算法是搜索中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先的顺序扩展所有可能情况，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法也称为“回溯法”。 深度搜索是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。,深度搜索算法的几个重要因素,(1) 状态: 作为递归的值参。 (2) 边界条件: 作为递归的结束条件，通常以深度结束。 (3) 递归范围: 作为for循环的初值和终值。 (4) 约束条件: 满足解的条件。 (5) 最优性要求：满足最优解的条件。,深度搜索的基本框架,procedure dfs(当前状态)； begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果；exit；回溯 end； for i算符最小值 to 算符最大值 do begin 算符i作用于当前状态，扩展出一个子状态； 标记子状态路径； if (子状态满足约束条件) and (子状态满足最优性要求)then dfs(子状态)； 恢复子状态路径； 回溯 end； end；,N皇后问题,在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。,基本思想,由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探； 按行放置皇后，每一行放一皇后； 对每一行所放置的皇后按列进行试探； 若某个位置能放，则放，否则试放下一个位置 若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。 若n个皇后都放好了，则得到了一个解。,算法基本框架,Procedure Try(i:integer)； 搜索第i行皇后的位置 var j:integer; begin if i=n+1 then 输出方案； for j:=1 to n do if 皇后能放在第i行第j列的位置 then begin 放置第i个皇后； 对放置皇后的位置进行标记； Try（i+1） 对放置皇后的位置释放标记； end; end;,边界条件设置,怎样判断某列放置了皇后 a: array 1MaxN of Boolean; 竖线被控制标记 怎样判断某对角线上放置了皇后 b: array 2MaxN * 2 of Boolean; 左上到右下斜线被控制标记 c: array 1-MaxN MaxN-1 of Boolean; 左下到右上斜线被控制标记,程序,Procedure Try( i: integer)； var j:integer; begin if i=n+1 then print； for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j; aj:=false; bi+j:=false; ci-j:=false; Try (i+1) aj:=true; bi+j:= true; ci-j:= true; end; end;,给出一个矩阵及一些国都名： o k d u b l i n dublin a l p g o c e v tokyo r a s m u s m b london o s l o n d o n rome y i b l g l r c bonn k r z u r i c h paris o a i b x m u z oslo t p q g l a m v lima 要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。,寻找国都名,搜索的方向,算法思想,将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。 在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了 Const Fx : Array18,12 Of Shortint 定义八个方向 =(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1);,Procedure Work(T,X,Y:Integer); 搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标 Var I : Integer; Begin If T=Length(S)+1 Then begin 搜索完，打印输出 Out; exit end; For I:=1 To 8 Do 八个方向进行搜索 Begin X:=X+FxI,1; Y:=Y+FxI,2; 坐标变化 If (AX,Y=ST)And(BX,Y) Then Begin W:=W+Chr(I+48); 记录路径 BX,Y:=False; 设置已经搜索 Work(T+1,X,Y); 继续搜索下一个 Delete(W,Length(W),1);恢复原路径 BX,Y:=True; 恢复标志 End; X:=X-FxI,1; Y:=Y-FxI,2; 返回后，坐标恢复 End; End;,构造字串,生成长度为n的字串，其字符从26个英文字母的前p(p26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时 a b c b a满足条件 a b c b c不满足条件 输入：n，p 输出：所有满足条件的字串,分析,状态：待扩展的字母序号i。 由于该变量的存储量太大，因此我们将s设为全局变量； 边界条件：产生了一个满足条件的字串，即 i=n+1； 搜索范围：从a开始的后p个字符； 约束条件：当前字串没有相邻子串相等的情况,procedure solve (i: integer)； var j, k: integer； t : longint ; begin if i=n+1 then 若产生了一个满足条件的字串，则输出 begin writeln (s)； inc( t )；exit 回溯 end； for k1 to p do 搜索每一个可填字母 begin ss+chr(64 + k )；j1；检查当前字串是否符合条件 while (jcopy(s,length(s)-2*j+1,j) 可以改用hash值来直接比对 do inc (j)； if ji div 2 then solve(i+1)； 若当前字串符合条件，则递归扩展下一个字母 delete( s, length (s), 1 ) 恢复填前的字串 end; end;,记忆化搜索,1. 递归前对尚待搜索的信息进行预处理 如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。 2.记忆化搜索 如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。,序关系计数,用关系和=将3个数a、b和c依次排列有13种不同的关系： abc， ab=c， acb， a=bc， a=b=c， a=cb， bac， ba=c， bca， b=ca， cab， ca=b， cba。 输入n 输出n个数依序排列时有多少种关系。,1 、枚举所有序关系表达式 由于类似于a=b和b=a的序关系表达式是等价的，为此，规定等号前面的大写字母在ASCII表中的序号，必须比等号后面的字母序号小。 状态（Step，First，Can）：其中Step表示当前确定第Step个关系符号；First表示当前大写字母中最小字母的序号；Can是一个集合，集合中的元素是还可以使用的大写字母序号 边界条件（step=n）：即确定了最后关系符号 搜索范围（Firstin）：枚举当前大写字母的序号 约束条件（i in Can）：序号为i的大写字母可以使用,procedure Count(Step，First，Can)； 从当前状态出发，递归计算序关系表达式数 begin if Step=n then begin 若确定了最后一个关系符号，则输出统计结果 for iFirst to n do if i in Can then Inc(Total)； Exit 回溯 end；then for iFirst to n do 枚举当前的大写字母 if i in Can then begin 序号为i的大写字母可以使用 Count(Step+1，i+1，Can-i)； 添等于号 Count(Step+1，1，Can-i) 添小于号 Endthen end； Count 该算法的时间复杂度是W(n!),2、粗略利用信息 若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。 设i个数共有Fi种不同的序关系，那么，由上面的讨论可知，在算法1中，调用一次Count(Step+1，1，Can-i)之后，Total的增量应该是Fn-Step。这个值可以在第一次调用Count(Step+1，1，Can-i)时求出。而一旦知道了Fn-Step的值，就可以用TotalTotal+Fn-Step 代替调用Count(Step+1，1，Can-i),procedure Count(Step，First，Can)； Step，First，Can的含义同算法1 begin if Step=n then begin 若确定了最后一个关系符号，则输出统计结果 for iFirst to n do if i in Can then Inc(Total)；Exit 回溯 end；then for iFirst to n do 枚举当前的大写字母 if i in Can 序号为i的大写字母可以使用 then begin Count(Step+1，i+1，Can-i)；添等于号 if Fn-Step=-1 then begin 第一次调用 Fn-Step Total；Count(Step+1，1，Can-i)； 添小于号 Fn-Step Total-Fn-Step Fn-Step=Total的增量 end then else TotalTotal+Fn-Step Fn-Step已经求出 endthen end；count 该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2n)。,3、充分利用信息 在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则可得到下面两条信息： 第一条信息：前k个大写字母都是用等号连接的。前半部分将产生的序关系数，就是n个物体中取k个的组合数 第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。 这样，我们可以得到Fn 的递推关系式： 采用上述公式计算Fn的算法记为算法3，它的时间复杂度是W(n2)。,var Total ：Comp；答案 F ：array0maxn of Comp；Fi为i个数的序关系表达式个数 i，j ：Integer； x ：Comp； begin FillChar(F，Sizeof(F)，0)；F初始化 F0 1； for i1 to n do begin递推F数组 Fi 0；x1； for j1 to i do begin 计算Fi xx*(i-j+1)/j；Fi Fi+x*Fi-j Endfor end；for writeln(Fn)； 输出结果 end；main,传染病控制,传染病的传播具有如下性质： 第一:它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会得病。 第二:这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。 第三:在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。 你的程序要针对给定的树，找出合适的切断顺序 。,贪心,我们首先来通过对样例数据和其它的一些比较简单的数据进行一些观察，很容易得到一种贪心的算法，对这种算法可做如下的描述： 1我们用Sum(i)表示以i为根节点的子树上的节点总数。那么我们每次砍掉当前层中还未砍掉的节点里面使得Sum(i)取到最大值的那个节点； 2重复第1步直到当前层中的节点为空。,一个反例,随机化搜索,1我们通过随机函数来选择即将被砍掉的节点，可以通过设置权值来使得算法更大可能地去选择“看起来最优”的决策； 2重复第1步直到当前层中的节点为空； 3对前两步执行多次并选取所得到的最优结果。 这个算法被设计出来以后，就很难在构造出能使这个算法失败的数据了，因此在考场上能够设计出来这个算法就已经很令人满意了，而事实也恰恰如此（这个算法可以通过所有的测试数据）。,虫食算,所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。 BADC + CBDA DCCC 给出一个N进制的虫食算式，相同的字母代表相同的数字，不同的字母代表不同的数字。 要求求出满足这个算式的唯一一组解，也就是字母和数字的一一对应关系.,解决方案1,要求一一对应的关系，就可以枚举这些一一对应的关系，找出符合的一项。这样，关系总数有O(N!)个，最坏情况下必须枚举所有的关系，并且加以判断，复杂度高达O(N*N!) ！,优化,大体上，从算式最后一位开始模拟运算情况，当可递推时递推，不可递推则枚举。 对于一竖列，先处理两个加数，当遇到的字母的值不确定时，则枚举当前位（注意与前面的情况判重）；否则不作为处理和，当遇到的字母的值不确定时,可从加数部分确定的值来确定（注意与前面的情况判重和进位）；否则看加数部分确定的值是否能得到和部分（注意进位）。引出矛盾就回溯。 例如它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况；A 则可以由D,E的值递推而来。对于倒数2位, (E+C+最后一位进位) mod N=A ；E的值可以用前面的结果；枚举C；判断A是否为(D+C+最后一位进位) mod N 虽然复杂度还是O(N!)，但这种方法限制很多（相当于剪枝）。,解决方案3,两个M位数相加，可以按位相加，设第i位的进位xi=1,表示有进位，为xi表示没有进位。,BADC + CBDA DCCC,枚举每位是否进位，复杂度是O(2n), (因为首位不可能进位，无须枚举)。然后，用高斯消元法来解方程，复杂度是O(n3) 。总复杂度是O(2n*n3) 。,优化,在解决方案3的基础上，我们可以对进位的枚举剪枝。观察这个竖列：A+B=C，若无进位则有AC且B=C. 若能推导出A=A （A,B为任何不相等字母），则当前的枚举不可行。可用递归枚举，从后向前枚举，处理一个竖列时则用上述2个不等式，看是否矛盾。数据结构用邻接矩阵。（规定A）。 若加进不等式A=B ，要加入所有x(x=A) =y(B=y)，枚举x,y，用O(n2)的时间。再判断是否有x=y.,靶形数独,输入9*9的数，其中一些是空格，要求完成 靶形数独，使得得到分数最大。,搜索剪枝,首先是搜索顺序的控制. 我们总是选择当前选择余地最小的格子进行搜索. 如果有两个格子的选择范围一样大, 那么优先搜索尽量靠里的格子. 这样可以使得搜索树的上端枝条尽量少, 显著地减少了搜索树的节点数. 优先搜索靠里的格子是为了尽快得到一个得分较高的解, 提高最优性剪枝的效率 最优性剪枝: 设当前还没有填入的数字总和为sum, 当前的得分为cur, 最优得分为best, 如果sum*10+cur=best, 那么已经没有继续搜索的必要了, 剪枝. 使用位运算来进行集合操作: 计算选择范围大小, 判断数字k能否放入(i, j). 可以显著减小算法的常数.,宽度优先搜索,宽度优先搜索算法也是搜索中的一种控制策略，它不像深度优先搜索那样一直往前搜索，直到找到答案位置。 宽度优先搜索是对每一步都扩展出所有可能的状态，逐层往下搜索。 对于一般图而言，它从某个未被访问的顶点v出发,依次访问v的各个未曾访问过的邻接点,直到所有已被访问的邻接点都被访问到. 要实现宽度优先，必须借助对列存放扩展的节点。,宽度优先搜索算法框架,procedure bfs(v); Init_queue(q); Visite(v); vistedv:=true; Insert_queue(q,v)； While not empty(q) do 取出队首元素 v For 对所有v扩展出来的元素w if not visitedw then visite(w);visitedw:=true; Insert_queue(q,w) delete_queue(q,v); ,街道赛跑,下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号0，1，N(此图中N=9)，点之间可以用含箭头的线相连。标号为0的点是起点；标号为N的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头(向外的)继续向前跑。,一个完整路线具有如下特点： 1路线中每一点都可从出发点到达； 2路线中每一点都可到达终点； 3终点处没有向外的箭头。 运动员要到达终点，但不要求路线(图)中的每一点都经过。但是路线(图)中的某些点是必经之点。上图的例子中，必经之点是：0，3，6，9。 任务A: 题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。 任务B: 假定赛跑必须在相邻的2天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第1天从点0出发，结束于“分裂点”。第2天从“分裂点”出发，结束于点N。 题目给出一个完整路线（图）C，请编程输出所有可能的“分裂点”（任务B）。“分裂点”S一定不是起点或终点。C可被S分成两个完整的子路线：这两个子路线没有公共的箭头线，并且S是这两个子路线的唯一公共点。在上的例子中，仅点3是“分裂点”。,输入数据： 输入数据描述一个完整路线（最多50个点，最多100个箭头），共n1行。前面n行描述箭头的终点，其中第i行中的每一个数字表示从点i（1in）出发的每一个箭头的终点，以2作为该行的结束。最后一行（第n+1行）中有一个数字1，表示输入结束。 输出数据： 输出两行数据，第1行表示必经点（子任务A）首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第2行表示“分裂点”：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务B）。,分析,必经点: 是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点N。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点0跑至终点N。 分裂点: 某点是必经点； 在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点； 完整路线中去除这个必经点后的所有点，分成两个互为独立的集合: 可从出发点0到达。这些点组成子路径1； 无法从出发点0到达。这些点组成子路径2； 两个集合中的点之间，无任何箭头相连；,思路,从点0开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜索的结果，将路线上的所有点(除当前判别点外)分为两个集合： 宽度优先搜索中访问到的点，即从出发点0可达的点集合，设这些点到达标志； 宽度优先搜索中未访问过的点，即不可从出发点0到达的点集合。这些点设未到达标志； 若终点N在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。,输入完整路线的相邻矩阵data1; For i1 to n-1 do /顺序设点1、点2，点N1为当前判别点 begin datadata1; /删除顶点i，构建新图的相邻矩阵data； for j1 to n do begin datai,j0; dataj,i0 end; BFS(0)； /宽度优先搜索出发点0可达的点集 if visitedn= -1 /若出发点0不可达终点n，则顶点i为必经点 then begin 输出顶点i为必经点； foundtrue； /初始时假设顶点i为分裂点 For k0 to n-1 do /搜索出发点0可达的点集合 For p0 to n do /搜索出发点0不可达的点集合 if (visitedk-1) if found then 输出顶点i为分裂点； end；then end；for,Amazing Robots: IOI2003,已知条件： 迷宫 i（i=1,2） （每个不会大于20*20） 守卫 Gi（0=Gi=10） （守卫循环移动进行执勤） （守卫巡逻的方格数（24） 求： 两个机器人都离开迷宫所用的最少指令数目 和离开制指令序列（10000 步以内）。,每一步可以发出的命令可以是N, E, S, W中的一种，有4种选择。 对每一步具体发出哪个命令，直接搜索。 假设最后结果是T。（也就是最少出宫时间） 时间复杂度是O(4T),这种方法时间复杂度太高，绝对不可行!,5*4和4*4的迷宫 第一个机器人的位置是(2,2) 第二个机器人的位置是(3,2) 当前时间是0。 状态(2,2),(3,2),0),状态表示： （第一个机器人位置，第二个机器认位置，时间）,E,(2,2),(3,2),0),(2,3),(3,3),1),时间已知，则所有Guard的位置可知。 Guard、Robot的位置均已知，所以状态可以转移,0时刻,1时刻,2时刻,3时刻,0时刻和2时刻是一样的 1时刻和3时刻是一样的。 稍加分析：此Guard循环以2为周期循环。,状态转移，需要的信息是：Robot位置，Guard位置。 Position of Robot1, 2是的作用就是记录Robot位置。 Time的作用就是为了计算Guard的位置,状态：(position of Robot1, position of Robot2, Time) Time=10000，这是状态数过多的罪魁祸首！,题目说：Guard巡逻经过的格子数只可能是2, 3, 4。 也就是说机器人巡逻周期只能是2, 4, 6。 2, 4, 6=12，所以第0时刻、12时刻、24时刻Guard的状态完全相同。 12可以看作Guard的周期。Time只要记录当前是第几个周期。因为周期确定了，Guard的位置也完全确定了！,0=Time=11,状态数(n*n)*(n*n)*12=12n4。 用BFS算法，标志数组判重。 时间复杂度O(12n4)。,n=20 完全可以承受 -,