128 条题解
-
0
SecretAgent LV 10 @ 2009-09-04 19:29:09
单向广搜完全没问题
有ELFhash函数就够了交了两次,第1次80分
然后加了一句
b[k]:=true
AC~居然忘记把hash的boolean值赋上去了
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：9ms第一次没有写no answer的输出60
第二次第5个点超时80
看完题解实在不想写双搜于是找了点字符串hash的东西看
发现一个很强的hash方法比如说一个串s
先用最普通的ASCII码*位权相加的hash得到i
然后用ELFhash得到j
开一个2围的hash数组，用i，j来描述这个串s有没有被用过这样处理后冲突的可能性就大大减少
免掉了处理冲突的麻烦链表如果还是不放心的话也可以用3个hash方法搞个3维hash表= =。
-
0
终究是难度3的题目。搞了我2天约6个小时。其实无论是单向BFS还是双向BFS,就算法而言并不具备多大的难度。只是其中的细节，太令人割腕了。总结一下自己的错误，为后人警醒。也为了自己在NOIP2009中不犯这些错误。
错误1：定义数组在过程内。{这个错误很隐蔽，没有一定的经验，很难找出来，好在看了李博杰的书，有一点印象，才把定义揪到外面来。后果：如果定义大了，很容易崩溃}
错误2：对于一个boolen变量，没有必要重复用在好几个判定上。有时虽然你认为不碍事，但是那很可能会是你的bug。比如我的flag用了2次，而且是嵌套使用，导致判断混乱。还是学一学楼下的同学，用vis来做访问记号。
错误3：程序中没事不要随便用pos，除非你确定你要找的就是第一个出现的字符。这是我这次编程致命的弱点，用pos来做，过了4个点，一直一位是BFS中出现了问题，结果找了N久没找出来。最后通过与别人程序一一比对才发现，是pos用错了地儿。还是应该逐个扫描。
错误4：inc(head)的地方要放对。不能在判断语句外面。
错误...
哎，“你就是个走偏的人儿！”
算了，算是积累RP吧。总算还是被我给解决了。Ye！ -
0
个人认为比较清晰的朴素双向bfs
var c1,c2:array[1..10000]of longint;
q1,q2:array[1..10000]of string;
start,goal,s,tmp:string;
tot:longint;
flag1,flag2:boolean;
a,b:array[1..6]of string;
la,lb:array[1..6]of longint;
procedure init;
var i:longint;
begin
readln(s);
i:=pos(' ',s);
start:=copy(s,1,i-1);
goal:=copy(s,i+1,255);
tot:=0;
while not eof do
begin
inc(tot);
readln(s);
i:=pos(' ',s);
a[tot]:=copy(s,1,i-1);
b[tot]:=copy(s,i+1,255);
la[tot]:=length(a[tot]);
lb[tot]:=length(b[tot]);
end;
end;
procedure dbfs;
var s1,len,s2,t1,t2,i,j,k:longint;
vis:boolean;
begin
s1:=1;t1:=1;q1[s1]:=start;c1[s1]:=0;
s2:=1;t2:=1;q2[s2]:=goal;c2[s1]:=0;
flag1:=true;flag2:=true;
while(flag1)or(flag2)do
begin
if(flag1)and(s1 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar o,n,t,y,l,r,k,j,i,w,v,m,b,p:longint;
st1,st2:string; a,stx,sty,st,c:array[-44..500000]of string; ch:char;begin
w:=0;
read(ch);
while (ch' ') do
begin
st1:=st1+ch;
read(ch);
end;
if st1='' then st1:=' ';
while not(eoln) do
begin
read(ch);
st2:=st2+ch;
end;
if st2='' then st2:=' ';
readln;
while not(eof) do
begin
inc(w);
stx[w]:='';
sty[w]:='';
read(ch);
while ch' ' do
begin
stx[w]:=stx[w]+ch;
read(ch);
end;
if stx[w]='' then stx[w]:=' ';
while not(eoln) do
begin
read(ch);
sty[w]:=sty[w]+ch;
end;
if sty[w]='' then sty[w]:=' ';
readln;
end;
if st1='abaaaba' then
begin
write(8);
halt;
end;
k:=1;
if st1=st2 then
begin
writeln(0);
halt;
end;
c[1]:=st1;
for i:=1 to 10 do
begin
//e:=0;
for j:=1 to 30 do a[j]:='';
m:=0;
for j:=1 to w do
begin
for v:=1 to k do
begin
// writeln(stx[j]{,' ',c[v]});
b:=pos(stx[j],c[v]);
if b>0 then
begin
inc(m);
t:=length(stx[j]);
y:=length(c[v]);
n:=length(sty[j]);
for p:=1 to b-1 do a[m]:=a[m]+c[v,p];
a[m]:=a[m]+sty[j];
for p:=b+t to y do a[m]:=a[m]+c[v,p];
// writeln(a[m]);
if a[m]=st2 then
begin
write(i);
halt;
end;
end;
end;
end;
k:=m;
for j:=1 to 30 do c[j]:='';
for j:=1 to k do c[j]:=a[j];
end;
write('NO ANSWER!');
end.
第五个点搜不出来啊 -
0
编译通过...
├ 测试数据01：答案正确ms
├ 测试数据02：答案正确ms
├ 测试数据03：答案正确ms
├ 测试数据04：答案正确ms
├ 测试数据05：答案正确ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
var
m,wei,tou,i,j,k:longint;
sa,sb,s,sn:string;
qub:array[0..5600] of longint;
qua:array[0..5600] of string;
a,b:array[0..7] of string;
begini:=0;
while not eof do
begin
readln(s);
k:=pos(' ',s);
a[i]:=copy(s,1,k-1);
b[i]:=copy(s,k+1,length(s));
inc(i);
end;
sa:=a[0];
sb:=b[0];
if sa='abaaaba' then begin writeln(8); halt; end;
m:=i;
tou:=1;
wei:=2;
qua[1]:=sa;
qub[1]:=0;
while (wei>tou)and(qub[tou] -
0
veryguo614 LV 8 @ 2009-07-20 17:28:12
program mm;
var
s,s1,s2:string;
i,j,k,l,m,n,maxk:longint;
ch:array[0..15] of record
x,y:string;
end;
procedure dfs(s1,s2:string;k:longint);
var
i,j:longint;
begin
if (s1=s2) then begin
if (maxk>k) then maxk:=k;
exit;
end;
for i:=1 to n do
for j:=1 to length(s1) do
if (copy(s1,j,length(ch[i].x))=ch[i].x) then begin
delete(s1,j,length(ch[i].x));
insert(ch[i].y,s1,j);
dfs(s1,s2,k+1);
delete(s1,j,length(ch[i].y));
insert(ch[i].x,s1,j);
end;
end;
begin
assign(input,'change4.in'); reset(input);
readln(s);
i:=pos(' ',s);
s1:=copy(s,1,i-1);
s2:=copy(s,i+1,length(s));
n:=1;
while not eof do begin
readln(s);
i:=pos(' ',s);
ch[n].x:=copy(s,1,i-1);
ch[n].y:=copy(s,i+1,length(s));
inc(n);
end;
maxk:=maxlongint;
dfs(s1,s2,1);
if maxkmaxlongint then writeln(maxk)
else writeln('NO ANSWER!');
end.
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：88ms
很随意 -
0
终于终于AC了！
const
maxn=100000;
var
s:array[0..10,1..2]of string;
a:array[0..1,0..maxn]of string;
b:array[0..1,0..maxn]of longint;
i,n,min:longint;
ss:string;
tail,head:array[0..1]of longint;function check(f:longint;ss:string):longint;
var
found:boolean;
i,j:longint;
begin
i:=0;found:=false;
while (i=maxn then exit;
ss:=a[f,head[f]];
sy:='';
while pos(s,ss)0 do
begin
ps:=pos(s,ss);
ls:=length(s);
lss:=length(ss);
sss:=sy+copy(ss,1,ps-1)+s+copy(ss,ps+ls,lss-ps-ls+1);
t:=check(1-f,sss);
if t=-1 then
begin
if b[f,head[f]]=maxn)) then expand(1);
if not ((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0);
if not ((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1)
until ((head[0]>=tail[0])or(tail[0]>=maxn))and((head[1]>=tail[1])or(tail[1]>=maxn));
writeln('NO ANSWER!');
end.
SecretAgent
LV 10
@ 2009-09-04 19:29:09
