Begin thCe OCcOCeOCxeOCtOCnOCt OCeOCrOCk OW eW aWeaWapWioW BWEsWcuWthWof Dawn
这个数据是有解

pascal 秒过 优化！！！
```pascal
const
aim:string='Begin the Escape execution at the Break of Dawn';
var
s:string;
i,nc,no,nw:longint;
aimn,sn:array[0..127]of longint;
re:array[0..97013]of boolean;

procedure noans;
begin
writeln('0 0');
halt;
end;

procedure outans;
begin
writeln('1 ',nc);
halt;
end;

function change(s:string;c,o,w:integer):string;
begin
change:=copy(s,1,c-1)+copy(s,o+1,w-o-1)+copy(s,c+1,o-c-1)+copy(s,w+1,length(s)-w);
end;

function hash(s:string):qword;
var
i,j:longint;
a:qword;
begin
a:=0;
for i:=1 to length(s) do
begin
a:=a shl 6;
if s[i]=' '
then
j:=0
else
if (s[i]>='A') and (s[i]<='Z')
then
j:=ord(s[i])-ord('A')+1
else
j:=ord(s[i])-ord('a')+27;
a:=(a+j)mod 97011;
end;
exit(a);
end;

procedure search(st:string);
var
p:array[0..31]of longint;
c,o,w,len,i,k:longint;

function connect(a,b,c,d:integer):boolean;
begin
if (a>b) and (c>d) then exit(true);
if pos(copy(st,a,b-a+1)+copy(st,c,d-c+1),aim)=0
then
exit(false)
else
exit(true);
end;

begin
if st=aim then outans;
if re[hash(st)] then exit;
len:=length(st);
if len<=47 then exit;
re[hash(st)]:=true;
k:=0;
for i:=1 to len do
if (st[i]='C')or(st[i]='O') or (st[i]='W')
then
begin
inc(k);
p[k]:=i;
end;
if copy(st,1,p[1]-1)<>copy(aim,1,p[1]-1) then exit;
if copy(st,p[k]+1,len-p[k])<>copy(aim,p[k]+48-len,len-p[k]) then exit;
if (st[p[1]]<>'C')or(st[p[k]]<>'W') then exit;
p[0]:=0;
p[k+1]:=len+1;
for o:=2 to k-1 do
if st[p[o]]='O'
then
for c:=1 to o-1 do
if st[p[c]]='C'
then
if connect(p[c-1]+1,p[c]-1,p[o]+1,p[o+1]-1)
then
for w:=k downto o+1 do
if st[p[w]]='W'
then
if connect(p[w-1]+1,p[w]-1,p[c]+1,p[c+1]-1)
then
if connect(p[o-1]+1,p[o]-1,p[w]+1,p[w+1]-1) then search(change(st,p[c],p[o],p[w]));
end;

begin
readln(s);
if s=aim
then
begin
writeln('1 0');
halt;
end;
for i:=1 to length(s) do inc(sn[ord(s[i])]);
for i:=1 to 47 do inc(aimn[ord(aim[i])]);
for i:=0 to 127 do
if aimn[i]<> sn[i]
then
begin
if chr(i)='C'
then
nc:=nc+sn[i]
else
if chr(i)='O'
then
no:=no+sn[i]
else
if chr(i)='W'
then
nw:=nw+sn[i]
else
noans;
end;
if(nc<>no) or (nc<>nw) then noans;
search(s);
noans;
end.
```

const
goal:string='Begin the Escape execution at the Break of Dawn';
prime:longint=99991;
letter:set of char=['C','O','W'];
var
ch :char;
i,j,ls,quit :longint;
st :string;
stan,che,fp :array[' '..'z']of longint;
h1 :array[0..99990]of boolean;
h2 :array[0..99990]of boolean;

procedure shut;//终止函数，用于退出程序
begin
writeln('0 0');
close(output);
halt;
end;

function stringhash(str:string):longint;//求字符串哈希函数
var
i,sum :dword;
begin
sum:=0;
for i:=1 to length(str) do
sum:=(sum*65599+ord(str[i]))and $ffffffff;
exit(sum mod prime)
end;

function exchange(str:string; a,b,c:longint):string;//字符串变换
var
s1,s2,tmp :string;
begin
tmp:=str;
s1:=copy(tmp,b+1,c-b-1); delete(tmp,b,c-b+1);
s2:=copy(tmp,a+1,b-a-1); insert(s2,tmp,b);
delete(tmp,a,b-a); insert(s1,tmp,a); exit(tmp);
end;

procedure init;
begin
readln(st); ls:=length(st); close(input);
if (ls-47)mod 3<>0 then shut;//小cut1：判断是否有整组“COW”
quit:=(ls-47) div 3;
for i:=1 to 47 do inc(stan[goal[i]]);
for i:=1 to ls do inc(che[st[i]]);
if (che['C']<>che['O'])or(che['O']<>che['W']) then shut;//小cut2：判断C O W 数量是否一致
che['C']:=0; che['O']:=0; che['W']:=0;
for ch:=' ' to 'z' do if che[ch]<>stan[ch] then shut;//小cut3：如果除“COW”外字符数不同，结束
if ls=47 then begin writeln('1 0'); close(output); halt; end;//小cut4：如果本身已是目标，结束
for i:=1 to 47 do
for j:=1 to 47 do
h1[stringhash(copy(goal,i,j-i+1))]:=true;//预处理每一部分出现的的字符串
end;

procedure search(x:longint; s:string);
var
i,j,k,l,r,len :longint;
tmp :string;
cal :array[1..3]of longint;
pos :array[1..3,1..9]of longint;
postmp :array[1..27]of longint;
begin
if (x>quit)and(s=goal) then begin writeln(1,' ',quit); close(output); halt; end;
len:=length(s);
h2[stringhash(s)]:=true;//没有出现过，记录一下
l:=1;
while not(s[l] in letter) do inc(l);
if (s[l]<>'C')or not(h1[stringhash(copy(s,1,l-1))]) then exit;//大cut1：当第一个加入字母不为‘C’或第一子段不正确时，剪枝
r:=len;
while not(s[r] in letter) do dec(r);
if (s[r]<>'W')or not(h1[stringhash(copy(s,r+1,len-r))]) then exit;//同上
fillchar(cal,sizeof(cal),0); fillchar(pos,sizeof(pos),0); fillchar(postmp,sizeof(postmp),0);
j:=0;
for i:=1 to len do
if s[i] in letter then
begin
inc(cal[fp[s[i]]]);
pos[fp[s[i]],cal[fp[s[i]]]]:=i;
inc(j); postmp[j]:=i;
end;
for i:=1 to j-1 do
if not(h1[stringhash(copy(s,postmp[i]+1,postmp[i+1]-postmp[i]-1))]) then exit;//大cut3：如果其中任意一段没出现过，剪枝
for i:=1 to cal[1] do
for j:=1 to cal[1] do
for k:=cal[1] downto 1 do
if (pos[1,j]<pos[2,i])and(pos[2,i]<pos[3,k]) then
begin
tmp:=exchange(s,pos[1,j],pos[2,i],pos[3,k]);
if h2[stringhash(tmp)] then break;//大cut3：如果之前搜索过 ，剪枝
search(x+1,tmp);
end;
end;

procedure main;
begin
fp['C']:=1; fp['O']:=2; fp['W']:=3;//对字母'C'，'O'，'W'添加一个映射，方便处理
search(1,st);
shut;
end;

begin
init;
main;
end.

编译通过...

├ 测试数据 01：答案正确... 900ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：900ms

真不错，第二道字符串hash题！

送上题解：http://www.nocow.cn/index.php/USACO/cryptcow

终于AC100题了...

注意一下,是10行,不是1行输入数据,难怪那么多次格式错误

就是有点慢，4000+ms

BegiCiC C EOoCoCeWOOn at tCreak OtC executWWf OheWWOCOhCOeCO BOnWWscapWDWWawn

我的程序输出是Yes,标程是No?

编译通过...

├ 测试数据 01：答案正确... 2072ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2072ms

编译通过...

├ 测试数据 01：答案正确... 1103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1103ms

USACO 4.1 cryptcow

本沙茶由于搜索时打错一个变量,答案都对,慢8s左右,TLE了n遍。。。

太难！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！？？？？？？？？？？

靠！用了半天字母链表，居然发现夹在里面的C O W也是需要交换的!rp..

var

start,s:string;

hash:array[0..97011] of boolean;

flag:boolean;

procedure print(step:longint);

begin

if not flag then

write('YES');

flag:=true;

end;

procedure print_n;

begin

write('NO');

end;

function checkhash(now:string):boolean;

var

g,h,i:longint;

begin

h:=0;

for i:=1 to length(now) do

　　begin

　　 h:=h shl 4+ord(now[i]);

　　 g:=h and $f0000000;

　　 if g0 then

　　　　h:=h xor (g shr 24);

　　 h:=h and (not g);

　　end;

h:=h mod 97011;

if hash[h] then begin

　　hash[h]:=false;

　　exit(false);

end;

exit(true);

end;

function check(now:string):boolean;

var

i,j:longint;

a:string;

begin

for i:=1 to length(now) do

　　if (now[i]='W') or (now[i]='O') or (now[i]='C') then

　　 begin

　　　　for j:=i+1 to length(now) do

　　　　 if (now[j]='W') or (now[j]='O') or (now[j]='C') then

　　　　　　break;

　　　　a:=copy(now,i+1,j-i-1);

　　　　if a='' then continue;

　　　　for j:=1 to length(a) do

　　　　 if (a[j]='W')or (a[j]='O') or (a[j]='C') then

　　　　　　delete(a,j,1);

　　　　if pos(a,start)=0 then

　　　　 exit(false);

　　 end;

exit(true);

end;

procedure search(now:string;step:longint);

var

i,j,k:longint;

next:string;

begin

if now=start then print(step);

if checkhash(now) then exit;

if not check(now) then exit;

for j:=1 to length(now) do

　　if now[j]='O' then

　　 for i:=j-1 downto 1 do

　　　　if now[i]='C' then

　　　　 for k:=length(now) downto j+1 do

　　　　　　if now[k]='W' then

　　　　　　 begin

　　　　　　　　next:=copy(now,1,i-1)+

　　　　　　　　　　 copy(now,j+1,k-j-1)+

　　　　　　　　　　 copy(now,i+1,j-i-1)+

　　　　　　　　　　 copy(now,k+1,100);

　　　　　　　　search(next,step+1);

　　　　　　 end;

end;

begin

while not eof do begin

fillchar(hash,sizeof(hash),true);

start:='Begin the Escape execution at the Break of Dawn';

readln(s);

search(s,0);

if not flag then

print_n;

flag:=false;

end;

end.

好吧......我承认Cheat掉RP....但是我的程序只有第七个点过不去，

无奈了........USACO上都过不去......

最近有点脑残，找可行解编BFS，然后死命查错...

program cryptcow;

const

aim:string='Begin the Escape execution at the Break of Dawn';

var

s:string;

i,nc,no,nw:integer;

aimn,sn:array[0..127]of integer;

re:array[0..97013]of boolean;

procedure noans;

begin

writeln('0 0');

halt;

end;

procedure outans;

begin

writeln('1 ',nc);

halt;

end;

function change(s:string;c,o,w:integer):string;

begin

change:=copy(s,1,c-1)+copy(s,o+1,w-o-1)+copy(s,c+1,o-c-1)+copy(s,w+1,length(s)-w);

end;

function hash(s:string):qword;

var

i,j:integer;

a:qword;

begin

a:=0;

for i:=1 to length(s)

do begin

a:=a shl 6;

if s[i]=' '

then j:=0

else if (s[i]>='A')and(s[i]b) and(c>d) then exit(true);

if pos(copy(st,a,b-a+1)+copy(st,c,d-c+1),aim)=0

then exit(false) else exit(true);

end;

begin

if st=aim then outans;

if re[hash(st)] then exit;

len:=length(st);

if len

编译通过...

├ 测试数据 01：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：134ms

这样的hash不会撞到么。。我觉得数据如果再强一点的话可能就不能AC了。。

呃、真水啊```再水，也得看懂题目...看不懂啊啊~~~

var

start,s:string;

hash:array[0..97011] of boolean;

flag:boolean;

procedure print(step:longint);

begin

if not flag then

write('YES');

flag:=true;

end;

procedure print_n;

begin

write('NO');

end;

function checkhash(now:string):boolean;

var

g,h,i:longint;

begin

h:=0;

for i:=1 to length(now) do

begin

h:=h shl 4+ord(now[i]);

g:=h and $f0000000;

if g0 then

h:=h xor (g shr 24);

h:=h and (not g);

end;

h:=h mod 97011;

if hash[h] then begin

hash[h]:=false;

exit(false);

end;

exit(true);

end;

function check(now:string):boolean;

var

i,j:longint;

a:string;

begin

for i:=1 to length(now) do

if (now[i]='W') or (now[i]='O') or (now[i]='C') then

begin

for j:=i+1 to length(now) do

if (now[j]='W') or (now[j]='O') or (now[j]='C') then

break;

a:=copy(now,i+1,j-i-1);

if a='' then continue;

for j:=1 to length(a) do

if (a[j]='W')or (a[j]='O') or (a[j]='C') then

delete(a,j,1);

if pos(a,start)=0 then

exit(false);

end;

exit(true);

end;

procedure search(now:string;step:longint);

var

i,j,k:longint;

next:string;

begin

if now=start then print(step);

if checkhash(now) then exit;

if not check(now) then exit;

for j:=1 to length(now) do

if now[j]='O' then

for i:=j-1 downto 1 do

if now[i]='C' then

for k:=length(now) downto j+1 do

if now[k]='W' then

begin

next:=copy(now,1,i-1)+

copy(now,j+1,k-j-1)+

copy(now,i+1,j-i-1)+

copy(now,k+1,100);

search(next,step+1);

end;

end;

begin

while not eof do begin

fillchar(hash,sizeof(hash),true);

start:='Begin the Escape execution at the Break of Dawn';

readln(s);

search(s,0);

if not flag then

print_n;

flag:=false;

end;

end.

这题真恶心。

用时1181ms，不想优化了……就用了ELFhash和一点小优化……代码写丑了……

编译通过...

├ 测试数据 01：答案正确... 775ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：775ms

呵呵，把USACO上过了的代码改了改，时间还可以啊……