首页 > 代码库 > Day4：T3搜索 T4数学题排列组合
Day4：T3搜索 T4数学题排列组合
T3：搜索
很出名的题吧，费解的开关
同T2一样也是一题很考思考的
附上题解再解释吧：
对于每个状态，算法只需要枚举第一行改变哪些灯的状态，只要第一行的状态固定了，接下来的状态改变方法都是唯一的：每一行需要改变状态的位置都在上一行中不亮的灯的正下面，因为只有这样才能使上一行的灯全亮。我们枚举第一行的状态改变方法（共2^5种），对于每种方法都依次改变下面几行的状态使上面一行灯全亮。到最后一行我们需要判断是否最后一行也恰好全亮，并更新最小步数。
首先需要找到第一行的状态，怎么写？枚举深搜啊
找到了其中一种第一行的状态之后呢？按照题解所说的，改变上一行中不亮的灯的正下面...怎么写？模拟啊不用说了吧
为什么是这样改变？因为需要把状态全部推到最后一行，判断是否可行
之后就是根据思路模拟模拟dfs一下即可了：
var a,g:array[0..6,0..6] of longint; n,i,j,ans:longint; k:char;procedure huan(x,y:longint);//对(x,y)进行操作begin a[x,y]:=1-a[x,y];end;procedure work(x:longint);//开始在第一排的状态已经确定的前提下进行其他行的操作var i,j,k:longint;begin g:=a;//temp数组 k:=x;//初始值表示已经操作过了几次 当然这个k不总是0 for i:=1 to 4 do for j:=1 to 5 do if a[i,j]=0 then begin huan(i,j);huan(i+1,j);huan(i+2,j);huan(i+1,j-1);huan(i+1,j+1);//将这个点下面一格的灯操作一下 inc(k); end; for i:=1 to 5 do if a[5,i]=0 then break//如果还有灯是关着的那么就结束. else if i=5 then if k<ans then ans:=k;//如果全部都是开着的那么就更新答案 a:=g;end;procedure cq(x,y:longint);begin if x=6 then work(y)//如果有六个灯了那么就开始找 一开始的初始步骤数为y else begin cq(x+1,y);//找下一个灯 huan(1,x);huan(1,x-1);huan(2,x);huan(1,x+1);//操作一个灯 cq(x+1,y+1);//找下一个灯 huan(1,x);huan(1,x-1);huan(2,x);huan(1,x+1);//回溯~ end;end;begin readln(n); for n:=n downto 1 do//n可以这样用 begin ans:=7;//用于更新答案(如果可以) for i:=1 to 5 do begin for j:=1 to 5 do begin read(k); a[i,j]:=ord(k)-48; end; readln; end;//读入数据 cq(1,0);//cq(x,y)表示找第一排的x个灯有y个被操作过的情况(当然是没有重复的) if ans<7 then writeln(ans) else writeln(-1); readln; end;end.
T4：排列组合
数学题（感觉自己数论方面略弱...需要多练多总结才行）
准备睡觉了...晚安
Day4：T3搜索 T4数学题排列组合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。