编译通过...

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

├ 测试数据 02：答案正确... 2166ms

├ 测试数据 03：答案正确... 2416ms

├ 测试数据 04：答案正确... 2494ms

├ 测试数据 05：答案正确... 2306ms

├ 测试数据 06：答案正确... 2384ms

├ 测试数据 07：答案正确... 2447ms

├ 测试数据 08：答案正确... 2041ms

├ 测试数据 09：答案正确... 2509ms

├ 测试数据 10：答案正确... 1900ms

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

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

http://hi.baidu.com/%CB%D5%CC%DAsauterne

编译通过...

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

├ 测试数据 02：答案正确... 2416ms

├ 测试数据 03：答案正确... 2572ms

├ 测试数据 04：答案正确... 2822ms

├ 测试数据 05：答案正确... 2572ms

├ 测试数据 06：答案正确... 2900ms

├ 测试数据 07：答案正确... 3244ms

├ 测试数据 08：答案正确... 3181ms

├ 测试数据 09：答案正确... 2744ms

├ 测试数据 10：答案正确... 2353ms

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

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

我弱。。康托和逆康托都上了 还是这么慢。。。。

..直接读入之后开始正向搜索也能过。。只要写的好。。

编译通过...

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

├ 测试数据 02：答案正确... 3462ms

├ 测试数据 03：答案正确... 3462ms

├ 测试数据 04：答案正确... 3509ms

├ 测试数据 05：答案正确... 3509ms

├ 测试数据 06：答案正确... 3509ms

├ 测试数据 07：答案正确... 3509ms

├ 测试数据 08：答案正确... 3462ms

├ 测试数据 09：答案正确... 3462ms

├ 测试数据 10：答案正确... 3478ms

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

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

我爱VIJOS强大的评测机!!!!!!

369KB的打表程序

秒杀

编译通过...

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

├ 测试数据 02：答案正确... 1572ms

├ 测试数据 03：答案正确... 1541ms

├ 测试数据 04：答案正确... 1572ms

├ 测试数据 05：答案正确... 1525ms

├ 测试数据 06：答案正确... 1556ms

├ 测试数据 07：答案正确... 1525ms

├ 测试数据 08：答案正确... 1525ms

├ 测试数据 09：答案正确... 1588ms

├ 测试数据 10：答案正确... 1572ms

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

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

虽然时间很丑，但是代码很简单。我没写康托展开，而是先预处理出9！，然后二分查找状态。预处理出所有的可能情况的步数，然后读入状态，直接输出。

bfs……

将目标放入队列搜……

hash用康托展开

编译通过...

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

├ 测试数据 02：答案正确... 1962ms

├ 测试数据 03：答案正确... 1962ms

├ 测试数据 04：答案正确... 1962ms

├ 测试数据 05：答案正确... 1978ms

├ 测试数据 06：答案正确... 1978ms

├ 测试数据 07：答案正确... 1978ms

├ 测试数据 08：答案正确... 1978ms

├ 测试数据 09：答案正确... 1978ms

├ 测试数据 10：答案正确... 1962ms

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

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

主要就是不能从输入数据向下DFS，而要从结果状态反向DFS，枚举所有情况。

用mod的哈希，也就1600ms,算了

编译通过...

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

├ 测试数据 02：答案正确... 2181ms

├ 测试数据 03：答案正确... 2212ms

├ 测试数据 04：答案正确... 2291ms

├ 测试数据 05：答案正确... 2166ms

├ 测试数据 06：答案正确... 2384ms

├ 测试数据 07：答案正确... 2619ms

├ 测试数据 08：答案正确... 2712ms

├ 测试数据 09：答案正确... 2197ms

├ 测试数据 10：答案正确... 1947ms

bfs+康托hash

编译通过...

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

├ 测试数据 02：答案正确... 1603ms

├ 测试数据 03：答案正确... 1588ms

├ 测试数据 04：答案正确... 1588ms

├ 测试数据 05：答案正确... 1603ms

├ 测试数据 06：答案正确... 1572ms

├ 测试数据 07：答案正确... 1588ms

├ 测试数据 08：答案正确... 1603ms

├ 测试数据 09：答案正确... 1619ms

├ 测试数据 10：答案正确... 1603ms

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

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

秒杀！

貌似有人说打表，我打了个，太大了，就不放上去了............

交的是个bfs的程序

ans:array[1..8]of longint=(285303,227590,77576,135289,205759,293805,157120,69074);

写个这个，直接用康托展开的值判解，貌似比较方便，省了逆康托了。这个用康托就能算出来了。

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

时间长主要是没有写反向的预处理，而是直接50次的正搜索。双向搜索貌似性价比很低，只省了一半时间，不合算。

有效耗时：18048ms

过程套用比较多，所以比较慢

突然发现刚刚想出来的hash函数原来还有个名字，叫康托哈希函数

程序运行速度:每个点都在1.6s~1.8s之间,总运行速度越为17s.

大概做法:先用反向的广度搜索预处理出所有情况+康托哈希函数.

细节:

1.内存的使用.

2.目标状态的设置要细心.(我就在这里WA了N次)

编译通过...├ 测试数据 01：答案正确... 2306ms├ 测试数据 02：答案正确... 2306ms├ 测试数据 03：答案正确... 2462ms├ 测试数据 04：答案正确... 2572ms├ 测试数据 05：答案正确... 2369ms├ 测试数据 06：答案正确... 2572ms├ 测试数据 07：答案正确... 2884ms├ 测试数据 08：答案正确... 3088ms├ 测试数据 09：答案正确... 2353ms├ 测试数据 10：答案正确... 2150ms反搜 是个垃圾!!!!!!!!!!!!!! 好耍哦~~~~~~普通 BFS 就行了 , 不过要用到 康托 来判重, 有点类似 hash ...........9 的全排列有 三十多万 , 利用 康托 判断出 当前搜索到的 序列 是这 三十多万个排列方式中的第几个, 以此来判重......

康托展开:

{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个 123 132 213 231 312 321代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。他们间的对应关系可由康托展开来找到。 如我想知道321是{1,2,3}中第几个大的数可以这样考虑 第一位是3，当第一位的数小于3时，那排列数小于321 如 123 213 小于3的数有1，2 所以有2*2!个 再看小于第二位2的 小于2的数只有一个就是1 所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个所以321是第6个大的数。 2*2!+1*1!是康托展开 再举个例子 1324是{1,2,3,4}排列数中第几个大的数 第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1，2但1已经在第一位了所以只有一个数2 1*2! 第三位是2小于2的数是1，但1在第一位所以有0个数 0*1! 所以比1324小的排列有0*3!+1*2!+0*1!=2个 1324是第三个大数。 此段来自 "NOCOW"

鄙人的程序:

type maptype=array[1..9] of integer; soutype=record w:longint; map:maptype; end;const aim:array[1..8,1..9]of integer=((2,7,6,9,5,1,4,3,8), (2,9,4,7,5,3,6,1,8), (4,3,8,9,5,1,2,7,6), (4,9,2,3,5,7,8,1,6), (6,1,8,7,5,3,2,9,4), (6,7,2,1,5,9,8,3,4), (8,1,6,3,5,7,4,9,2), (8,3,4,1,5,9,6,7,2)); d1:array[1..12] of integer=( 1,2,4,5,7,8,1,2,3,4,5,6 ); d2:array[1..12] of integer=( 2,3,5,6,8,9,4,5,6,7,8,9 ); jie:array[1..8] of longint=( 1,2,6,24,120,720,5040,40320 );var a:maptype; sou:array[1..1000000] of soutype; vis:array[1..400000] of boolean; ai:array[1..8] of longint; function getVIS( st:longint ):longint; var i,j,kk:longint; vv:array[1..9] of boolean; begin fillchar( vv , sizeof(vv) , false ); getVIS:=0; for i:=1 to 8 do begin kk:=0; for j:=1 to sou[st].map[ i ]-1 do if (not vv[j]) then inc( kk ); vv[ sou[st].map[i] ]:=true; getVIS:=getVIS + kk * jie[ 9-i ]; end; getVIS:=getVIS + 1; end; function check( tt:longint ):boolean; var i:integer; begin check:=false; for i:=1 to 8 do if (tt=ai[i]) then exit( true ); end; procedure work; var i,j,k,start,tail,dt,y,t:longint; begin for i:=1 to 9 do sou[ 1 ].map[i]:=a[i]; t:=getVIS( 1 ); if check( t ) then begin writeln( 0 ); exit; end; vis[ t ]:=true; start:=0; tail:=1; repeat inc( start ); for k:=1 to 12 do begin dt:=tail+1; sou[ dt ].w:= sou[start].w+1; sou[ dt ].map:= sou[start].map; y:=sou[ dt ].map[ d1[k] ]; sou[ dt ].map[ d1[k] ]:= sou[ dt ].map[ d2[k] ]; sou[ dt ].map[ d2[k] ]:=y; t:=getVIS( dt ); if not vis[ t ] then begin tail:=dt; vis[ t ]:=true; if check( t ) then begin writeln( sou[tail].w ); exit; end; end; end; until start>=tail; end; procedure start; var k,i,t:longint; begin for k:=1 to 8 do begin for i:=1 to 9 do sou[k].map[i]:=aim[k,i]; t:= getVIS( k ); ai[ k ]:= t; end; for k:=1 to 3 do begin for i:=1 to 9 do read( a[i] ); readln; work; fillchar( vis,sizeof(vis), false ); end; end;begin start;end.

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

康托+反搜 是个拉积

反搜 好傻哦

真的是

type

daty=array[1..9] of integer;

tay=record

map:array[1..9] of integer;

step:longint;

end;

const

aim:array[1..8,1..9]of integer=((2,7,6,9,5,1,4,3,8),

(2,9,4,7,5,3,6,1,8),

(4,3,8,9,5,1,2,7,6),

(4,9,2,3,5,7,8,1,6),

(6,1,8,7,5,3,2,9,4),

(6,7,2,1,5,9,8,3,4),

(8,1,6,3,5,7,4,9,2),

(8,3,4,1,5,9,6,7,2));

u:array[1..12] of integer=(1,2,3,4,5,6,7,8,1,2,4,5);

v:array[1..12] of integer=(2,3,6,5,6,9,8,9,4,5,7,8);

var

t:array[1..1000000] of tay;

p:array[1..9] of longint;

vis:array[1..370000] of boolean;

goal:array[1..8] of longint;

a:daty;

function hash(x:daty):longint;

var i,j,k:integer;

s:array[1..9] of boolean;

begin

fillchar(s,sizeof(s),false);

hash:=0;

for i:=9 downto 1 do

begin

k:=0;

for j:=1 to x[9-i+1]-1 do

if not s[j] then inc(k);

s[x[9-i+1]]:=true;

inc(hash,k*p);

end;

end;

function find(x:longint):boolean;

var i,j:longint;

begin

for i:=1 to 8 do

if x=goal[i] then exit(true);

exit(false);

end;

procedure work;

var i,j,k,head,tail:longint;

begin

head:=0;tail:=1;

t[1].map:=a;

k:=hash(t[1].map);

vis[k]:=true;

if find(k) then

begin

writeln(0);

exit;

end;

repeat

inc(head);

for i:=1 to 12 do

begin

inc(tail);

t[tail].map:=t[head].map;

k:=t[tail].map[u[i]];

t[tail].map[u[i]]:=t[tail].map[v[i]];

t[tail].map[v[i]]:=k;

k:=hash(t[tail].map);

t[tail].step:=t[head].step+1;

if vis[k] then dec(tail)

else vis[k]:=true;

if find(k) then

begin

writeln(t[tail].step);

exit;

end;

end;

until head>tail;

end;

procedure inte;

var i,j:longint;

begin

p[1]:=1;p[0]:=1;

for i:=2 to 9 do p[i]:=p*i;

for i:=1 to 8 do

goal[i]:=hash(aim[i]);

for j:=1 to 50 do

begin

for i:=1 to 9 do read(a[i]);

fillchar(vis,sizeof(vis),false);

work;

end;

end;

begin

inte;

end.

编译通过...

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

├ 测试数据 02：答案正确... 3041ms

├ 测试数据 03：答案正确... 2869ms

├ 测试数据 04：答案正确... 3119ms

├ 测试数据 05：答案正确... 2916ms

├ 测试数据 06：答案正确... 3275ms

├ 测试数据 07：答案正确... 3712ms

├ 测试数据 08：答案正确... 3666ms

├ 测试数据 09：答案正确... 3103ms

├ 测试数据 10：答案正确... 2509ms

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

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

编译通过...

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

├ 测试数据 02：答案正确... 3431ms

├ 测试数据 03：答案正确... 3353ms

├ 测试数据 04：答案正确... 3572ms

├ 测试数据 05：答案正确... 3447ms

├ 测试数据 06：答案正确... 3806ms

├ 测试数据 07：答案正确... 4181ms

├ 测试数据 08：答案正确... 4369ms

├ 测试数据 09：答案正确... 3619ms

├ 测试数据 10：答案正确... 3056ms

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

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

1次A：）海豚给我搞定的……

BFS+康托 也是AC的第100题 纪念下~

Orz楼下打表的……

目标状态就8种

276951438

294753618

438951276

492357816

618753294

672159834

816357492

834159672

由这八个BFS扩展，总共362880种状态，共12种交换方法。康托作HASH。

最大好像是8，没有-1的情况。

哈哈，打个表~~714 KB (732,132 字节)秒杀。

编译通过...

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

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms