usaco4.1.4 Cryptcowgraphy 最后的总结,最终没有看题解,自己想出来四个剪枝,刚开始四个剪枝加上一直无法ac,正在抓狂的时候发现有个地方写错了,导致许多新的枝条,改一下,ac了,这一题也没想象中的那么难,加油。 后记:看了题解后搜索顺序改了一下,直接导致剪枝四没有用上,发现慢的出奇,15s左右才能出解,看来剪枝四效率很高呢。 一看就是搜索,写一下裸的过了5个点 {ID:zhengha3 PROG:cryptcow LANG:PASCAL}program aa;const z='Begin the Escape execution at the Break of Dawn';var s:string; i,j:longint;function check(s:string):boolean; begin if s=z then exit(true) else exit(false); end;procedure dfs(s:string;dep:longint);var i,j,k,l:longint; s1,s2,s3,s4:string; begin if check(s) then begin writeln(1,' ',dep);close(output);halt;end; l:=length(s); for i:=1 to l do if s[i]='C' then for j:=i+1 to l do if s[j]='O' then for k:=j+1 to l do if s[k]='W' then begin s1:=copy(s,1,i-1); s2:=copy(s,i+1,j-i-1); s3:=copy(s,j+1,k-j-1); s4:=copy(s,k+1,l); s1:=s1+s3;s1:=s1+s2;s1:=s1+s4; dfs(s1,dep+1); end; end;begin assign(input,'cryptcow.in');reset(input); assign(output,'cryptcow.out');rewrite(output); read(s); dfs(s,0); writeln(0,' ',0); close(output);end. 留位想剪枝 剪枝一,第一个特殊字符必须是C,最后一个特殊字符必须是W 剪枝二,hash数组判重,不重复处理 加上这两个剪枝第六个点大概8秒出解,继续想 这好像是个大剪枝,剪枝三,每两个特殊字符之间的字符串必须和目标字符串有交集,即pos(s1,z)<>0; 加上这个剪枝后又快了大概3秒钟,5s出解,看来还有更为强大的剪枝,继续想..烦.. 剪枝四,这个应该归到剪枝三上,因为我是这样循环的 for i:=1 to l do if s[i]='C' then for j:=i+1 to l do if s[j]='O' then for k:=j+1 to l do if s[k]='W' then 所以我发现如果在上一个k没有通过剪枝三话那么剩下的也通不过,直接break; 第6个点耗时2.2s,还是超时,再相出一个剪枝估计就可以ac了,继续,恶心.. 突然发现有一点写错了,感觉剪枝四要分情况,等下再写,用前三个剪枝,过到第八个点,剪枝四应该是可以用的,感觉要以o为界限,让我再仔细想一下 加上剪枝四了,第六个点确实变快了,第八个点根本没用上剪枝四。 认真检查一下,发现有一个地方写脑残了,导致了很多大枝条,改了一下,ac了,成就感颇高,这四个剪枝全是自己想的,yes.. {ID:zhengha3 PROG:cryptcow LANG:PASCAL}program aa;const z='Begin the Escape execution at the Break of Dawn'; seed=31;var s:string; i,j:longint; hash:array[0..1200007] of boolean; a:array[1..29] of longint;function bkdhash(s:string):longint;var i:longint; begin bkdhash:=0; for i:=1 to length(s) do bkdhash:=(bkdhash*seed+ord(s[i]))and $FFFFFFF; end;function check(s:string):boolean; begin if s=z then exit(true) else exit(false); end;function cut1(s:string):boolean;var i:longint; begin for i:=1 to length(s) do if (s[i]='C') or (s[i]='W') or (s[i]='O') then if s[i]<>'C' then exit(false) else break; for i:=length(s) downto 1 do if (s[i]='C') or (s[i]='W') or (s[i]='O') then if s[i]<>'W' then exit(false) else break; exit(true); end;function cut2(s:string):longint;var s1:string; sum:longint; begin a[1]:=0;sum:=1; for i:=1 to length(s) do if (s[i]='C') or (s[i]='O') or (s[i]='W') then begin inc(sum);a[sum]:=i;end; inc(sum);a[sum]:=length(s)+1; for i:=1 to sum-1 do begin s1:=copy(s,a[i]+1,a[i+1]-a[i]-1); if (pos(s1,z)=0) and (s1<>'') then exit(a[i+1]); end; exit(-1); end;procedure dfs(s:string;dep:longint);var i,j,k,l,con:longint; s1,s2,s3,s4,s5:string; pd:boolean; begin if check(s) then begin writeln(1,' ',dep);close(output);halt;end; l:=length(s); for i:=1 to l do if s[i]='C' then begin s1:=copy(s,1,i-1); if cut2(s1)<>-1 then break; for j:=i to l do if s[j]='O' then begin s1:=copy(s,i,j-i-1); if cut2(s1)<>-1 then break; for k:=j+1 to l do if s[k]='W' then begin s1:=copy(s,1,i-1); s2:=copy(s,i+1,j-i-1); s3:=copy(s,j+1,k-j-1); s4:=copy(s,k+1,l); s1:=s1+s3;s1:=s1+s2;s1:=s1+s4; con:=bkdhash(s1) mod 1200007; if cut1(s1)=false then continue; if cut2(s1)<>-1 then break; if hash[con]=false then begin dfs(s1,dep+1);hash[con]:=true;end else continue; end; end; end; end;begin assign(input,'cryptcow.in');reset(input); assign(output,'cryptcow.out');rewrite(output); read(s); if cut1(s)=false then begin writeln(0,' ',0);halt;close(output);end; dfs(s,0); writeln(0,' ',0); close(output);end.