120 条题解
-
0
wytk2008 LV 7 @ 2009-11-03 22:05:46
单向BFS+8^8布尔数组-->AC
双向BFS+2*8^8布尔数组-->内存溢出
双向BFS+康托展开hash-->0ms AC
拓展一个：康托展开
X=a[1]*n!+a[2]*(n-1)!+...+a[n]*1!(从左往右编号1..n)
其中a[i]表示从i..1中比num[i]小的数字的个数。
Function ct(p:arr):longint;
Var
i,j,t,ans:longint;
Begin
for i:=1 to 8 do
begin
t:=0;
for j:=2 to 9 do
if p[j] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms汗，连双搜都不用...
ELFHASH WA 了N次，最后终于暴力用
直接个hash[0..9,0..9(八个)]然后再来个滚动数组=AC...
VOJ的数据真水 -
0
program bashumananti;
const
xx:array[1..4]of shortint=(0,-1,0,1);
yy:array[1..4]of shortint=(-1,0,1,0);type
arr=array[1..3,1..3]of byte;
jl=record
qipan:arr;
fa:longint;
end;var
str:string[10];
i,j,k,m,n,kkk:longint;
cllose1,cllose2,oppen1,oppen2:longint;
x1,x2:array[1..1000000]of jl;
f1,f2:array[1..1000000]of longint;procedure init;
begin
m:=0; kkk:=0;
cllose1:=1; oppen1:=1;
cllose2:=1; oppen2:=1;
f1[cllose1]:=0; f2[cllose2]:=0;
x1[1].fa:=0; x2[2].fa:=0;
read(str);
for i:=1 to 3 do
x1[cllose1].qipan[1,i]:=ord(str[i])-ord('0');
for i:=4 to 6 do
x1[cllose1].qipan[2,i-3]:=ord(str[i])-ord('0');
for i:=7 to 9 do
x1[cllose1].qipan[3,i-6]:=ord(str[i])-ord('0');
x2[cllose2].qipan[1,1]:=1; x2[cllose2].qipan[1,2]:=2; x2[cllose2].qipan[1,3]:=3;
x2[cllose2].qipan[2,1]:=8; x2[cllose2].qipan[2,2]:=0; x2[cllose2].qipan[2,3]:=4;
x2[cllose2].qipan[3,1]:=7; x2[cllose2].qipan[3,2]:=6; x2[cllose2].qipan[3,3]:=5;
end;function same1(chkarr:arr):boolean;
var
i,j,k,kk:integer;
begin
for k:=1 to cllose1-1 do
begin
kk:=0;
for i:=1 to 3 do
for j:=1 to 3 do
if x1[k].qipan=chkarr then inc(kk) else break;
if kk=9 then exit(true);
end;
exit(false);
end;function same2(chkarr:arr):boolean;
var
i,j,k,kk:integer;
begin
for k:=1 to cllose2-1 do
begin
kk:=0;
for i:=1 to 3 do
for j:=1 to 3 do
if x2[k].qipan=chkarr then inc(kk) else break;
if kk=9 then exit(true);
end;
exit(false);
end;procedure isok1;
var
i,j,k,w:longint;
begin
for k:=1 to oppen2 do
begin
w:=0;
for i:=1 to 3 do
for j:=1 to 3 do
if x1[oppen1].qipan=x2[k].qipan then inc(w) else break;
if w=9 then
begin
write(f1[oppen1]+f2[k]);
halt;
end;
end;
end;procedure isok2;
var
i,j,k,w:longint;
begin
for k:=1 to oppen1 do
begin
w:=0;
for i:=1 to 3 do
for j:=1 to 3 do
if x2[oppen2].qipan=x1[k].qipan then inc(w) else break;
if w=9 then
begin
write(f2[oppen2]+f1[k]);
halt;
end;
end;
end;procedure search;
var
i,j,k:longint;
i1,j1:shortint;
buffer:arr;
begin
inc(kkk);
if odd(kkk) then
begin
for i:=1 to 3 do
for j:=1 to 3 do
if x1[cllose1].qipan=0 then
begin
for k:=1 to 4 do
begin
i1:=i+xx[k];
j1:=j+yy[k];
if (i1>0)and(i10)and(j10)and(i10)and(j1oppen1) or (cllose2>oppen2);
writeln('No answer!');
end. -
0
program shuangxiang;
const maxn=50000;
var zzz,i1,j1,r,r1,head,head1,tail,tail1,i,j,n,m,k,s,t:longint;
a,a1:array[1..maxn]of string;
lu,lu1,x,y,x1,y1:array[1..maxn]of integer;
b,b1:array[1..500000]of boolean;
start,final,w:string;
jh:char;jc:array[1..9]of longint;function hash(ww:string):longint;
var i,j:longint;
begin
s:=0;for i:=1 to 9 do begin t:=0;for j:=i+1 to 9 do if ww[i]>ww[j] then inc(t);s:=s+t*jc[10-i];end;
hash:=s;
end;procedure print(bj:longint);
var o:longint;
begin
if bj=1 then begin for o:=1 to tail1 do begin if a1[o]=a[tail] then begin write(lu[tail]+lu1[o]);exit;end;end;end;
if bj=2 then begin for o:=1 to tail do begin if a[o]=a1[tail1] then begin write(lu1[tail1]+lu[o]);exit;end;end;end;
end;function check(uu,bj:longint):boolean;
begin
if (bj=1)and(b1[uu]=false) then exit(true);
if (bj=2)and(b[uu]=false) then exit(true);
exit(false);
end;procedure change(wz,k:longint;var w:string;var p1,q1:longint);
var tt:longint;
begin
if (k=1)and(p1>1) then begin p1:=p1-1;tt:=(p1-1)*3+q1;jh:=w[tt];w[tt]:=w[wz];w[wz]:=jh;end;
if (k=2)and(p11) then begin q1:=q1-1;tt:=(p1-1)*3+q1;jh:=w[tt];w[tt]:=w[wz];w[wz]:=jh;end;
if (k=4)and(q1=head) do dec(p);
while (lu1[y]=lu1[q])and(q>=head1)do dec(q);
if z-p>=y-q then exit(false) else exit(true);
end;procedure search;
var p,q,wz,q1,p1:longint;
begin
inc(head);
wz:=pos('0',a[head]);
p:=(wz-1) div 3+1;q:=wz mod 3;if q=0 then q:=3;
for i:=1 to 4 do begin
w:=a[head];
p1:=p;q1:=q;
change(wz,i,w,p1,q1);
zzz:=hash(w);
if ((q1q)or(p1p))and(b[zzz])then begin
b[zzz]:=false;
inc(tail);
a[tail]:=w;
lu[tail]:=lu[head]+1;
if check(zzz,1) then begin print(1);halt;end;
end;
end;
end;procedure search1;
var p,q,wz,q1,p1:longint;
begin
inc(head1);
wz:=pos('0',a1[head1]);
p:=(wz-1) div 3+1;;q:=wz mod 3;if q=0 then q:=3;
for i:=1 to 4 do begin
w:=a1[head1];
p1:=p;q1:=q;
change(wz,i,w,p1,q1);
zzz:=hash(w);
if ((q1q)or(p1p))and(b1[zzz])then begin
b1[zzz]:=false;
inc(tail1);
a1[tail1]:=w;
lu1[tail1]:=lu1[head1]+1;
if check(zzz,2) then begin print(2);halt;end;
end;
end;
end;begin
readln(start);final:='123804765';
jc[1]:=1;jc[2]:=1;
for i:=3 to 9 do jc[i]:=jc*(i-1);
if start=final then write(0) else begin
fillchar(b,sizeof(b),true);
fillchar(b1,sizeof(b1),true);
tail:=1;tail1:=1;head:=0;head:=0;
a[1]:=start;a1[1]:=final;
b[hash(a[1])]:=false;b1[hash(a1[1])]:=false;
repeat
if pd(tail,tail1) then search else search1;
until (head>=tail)or(head1>=tail1)or(tail+tail1>600000);
write('NO answer!');
end;
end.HASH+双向宽搜。。。。。一看我就知道绝对沙茶 用了两个模版还不带TYPE的
-
0
song19931218 LV 9 @ 2009-10-11 17:58:38
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|写这一题写了两个小时。。。。。已经快崩溃了。。。看了swj的程序，一开始我的程序的hash表建立的太猥琐了，用了拉链法，查找很慢，时间空间都会暴掉。。。。后来采用了
sigma(k!*a[k])的hash表进行判重，总算过了。。。。
不过很奇怪，因为我开始用了sigma((k-1)!*a[k])判重，竟然连样例都过不了。。。是因为判重的时候出错，但是为什么sigma(k!*a[k])就一定能保证不会冲突？？？？请大牛点拨，orz!!! -
0
oliverthree LV 10 @ 2009-10-10 09:53:00
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms康托展开判重+bfs。。。 不过代码写的有点丑
-
0
const
target='123804765';
stage:array[1..8] of longint=(1,2,6,24,120,720,5040,40320);
type
node=record
s:string[9];
step:integer;
end;
var
used:array[0..362879] of boolean;
a:array[1..1000000] of node;
cld,open,i,j,k,l:longint;
now,s1:string[9];
procedure print;
begin
writeln(a[open].step);
halt;
end;
procedure check;
var
i,j:longint;
begin
j:=0;
for i:=1 to 8 do
j:=j+(ord(a[open].s[i])-48)*stage[i];
if used[j] then dec(open)
else used[j]:=true;
end;
begin
readln(a[1].s);
a[1].step:=0;
cld:=0;open:=1;
repeat
inc(cld);
now:=a[cld].s;
l:=pos('0',now);
if l>3 then begin
inc(open);
a[open].step:=a[cld].step+1;
s1:=now;
s1[l]:=s1[l-3];s1[l-3]:='0';
a[open].s:=s1;
check;
if s1=target then print;
end;
if l0 then begin
inc(open);
a[open].step:=a[cld].step+1;
s1:=now;
s1[l]:=s1[l+1];s1[l+1]:='0';
a[open].s:=s1;
check;
if s1=target then print;
end;
until cld>open;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msA*算法不懂。
hash+朴素的BFS 0S -
0
program p1360;
const
s='123804765';
a:array[1..4] of integer=(1,-1,3,-3);
var q:array[1..100000] of string[9];
bo:array['0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8'] of boolean;
b:array[1..100000] of integer;
i,j,l,f,t,k,n,m:longint;
ch:char;
bb:array[1..4] of boolean;
ww:boolean;
ss,sss:string[9];
begin
fillchar(bo,sizeof(bo),1);
f:=1;
b[1]:=0;
l:=1;
readln(q[f]);
t:=pos('0',q[f]);
while f0) and( t+a[i] -
0
SecretAgent LV 10 @ 2009-09-25 14:12:40
广搜
耗时有点多。。编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 9ms
├ 测试数据 05：答案正确... 103ms
├ 测试数据 06：答案正确... 119ms
├ 测试数据 07：答案正确... 119ms
├ 测试数据 08：答案正确... 119ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：469ms -
0
li573924451 LV 7 @ 2009-09-19 20:33:44
program eightqueens;
var
x:array[1..8] of integer;
a,b,c:array[-7..16] of boolean;
i:integer;
procedure print;
var k:integer;
begin
for k:=1 to 8 do write(x[k]:4);
writeln;
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to 8 do if a[j] and b and c
then begin
x[i]:=j;
a[j]:=false;
b:=false;
c:=false;
if i -
0
记录号 Flag 得分 记录信息 环境 评测机 程序提交时间
R1770573 Accepted 100 From gsrq－
P1360 FPC Edogawa Conan 2010-4-5 12:43:41From yours
八数码问题编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msconst
goal='123804765';
d:array[1..9,0..4] of longint=((2,2,4,0,0), //1
(3,3,1,5,0), //2
(2,2,6,0,0), //3
(3,5,1,7,0), //4
(4,6,4,2,8), //5
(3,5,3,9,0), //6
(2,8,4,0,0), //7
(3,9,7,5,0), //8
(2,8,6,0,0));//9
var
q:array[1..362880] of record
s:string;
depth:longint;
end;
ahash:array[1..362880] of boolean;
i,k,head,tail,step:longint;
x,s:string;
function hash(s:string):boolean;
var
i,j,ans,tem:longint;
begin
ans:=0;
for i:=1 to 8 do
begin
tem:=0;
for j:=i+1 to 9 do
if s[j]
wytk2008
LV 7
@ 2009-11-03 22:05:46
