题解 - Vijos

0

prince_hao LV 10 @ 2010-04-08 22:26:07

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

亲爱滴DLX~~

0

huyunzhou LV 8 @ 2009-11-09 12:24:50

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀！！！

这个题目就是要狂剪枝，

不仅要找当前可填的数最少的格子去填，

还要开个三维的boolean型的hash把当前的所有点可以填的数记录下来，

将这个三维数组作为一个搜索的状态参量进行搜索

把程序贴出来给大家参考一下吧，我没用三维的hash，其实这个大的两维的hash等同于我说的那个三维的hash，目的都是一样的

这个程序写的比较丑，不过还是可以秒杀的，不是太容易理解，要仔细想想

type arr1=array[1..70,1..9] of boolean;

arr2=array[1..70] of integer;

var n:integer;

x,y,l:arr2;

h:arr1;

a:array[1..9,1..9] of integer;

h1,h2:array[1..9,1..9] of boolean;

h3:array[0..2,0..2,1..9] of boolean;

h4:array[1..70] of boolean;

procedure ready;

var st:string;

i,j,p,q:integer;

begin

fillchar(h1,sizeof(h1),true);fillchar(h2,sizeof(h2),true); fillchar(h3,sizeof(h3),true);

for i:=1 to 9 do

begin

readln(st);

for j:=1 to 9 do if st[j]='0' then

begin

inc(n); x[n]:=i; y[n]:=j;

end else

begin

p:=ord(st[j])-48; a:=p;

h1:=false; h2[j,p]:=false;

h3[(i-1)div 3,(j-1) div 3,p]:=false;

end;

end;

for i:=1 to n do

begin

for j:=1 to 9 do if h1[x[i],j] and h2[y[i],j] and h3[(x[i]-1)div 3,(y[i]-1)div 3,j] then

begin

inc(l[i]); h:=true;

end;

end;

end;

procedure put;

var i,j:integer;

begin

for i:=1 to 9 do

begin

for j:=1 to 9 do write(a);

writeln;

end;

halt;

end;

procedure f(k:integer;h:arr1;l:arr2);

var i,j,q,sh,min:integer;

o:boolean;

hz:arr1; lz:arr2;

begin

if k>n then put

else

begin

min:=9;

for i:=1 to n do if not h4[i] then if l[i]

0

chiccs LV 9 @ 2009-11-08 17:36:49

用已经填充的数字个数作为搜索的状态变量.每次只填可填数字最少的格子,其它格子全部舍弃(也就是交给下一次搜索解决).若某格子可填数字为0则说明出错了,这时退回上一层

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

Matt LV 10 @ 2009-10-02 11:16:00

离奇的判断优化...

总之我也不知道为什么

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

向往拥有DLX的生活...

0

chengrui LV 10 @ 2009-10-28 21:38:01

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

弱弱的剪枝.......

不会用dance link 可怜......

Orz秒杀的神牛

50个

0

hxlong LV 10 @ 2009-09-05 18:18:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

贪心搜索 orz秒杀的大牛

0

ljq LV 10 @ 2009-09-05 14:05:41

把P1345的程序改了改，交上去，结果只有30分……囧……

0

fp_s1 LV 9 @ 2009-09-03 23:11:34

???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????p??????????????????????????????????????????????????????????????????????????

怎么剪支？怎么优化？？？？？？？？？？？？？？？？？？急！！！！！！！！

0