/ Vijos / 题库 / Vs Rum /

题解

20 条题解

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-09-05 14:05:41

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

  • 0
    @ 2009-09-03 23:11:34

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

    怎么剪支?怎么优化??????????????????急!!!!!!!!

  • 0
    @ 2009-09-13 15:09:42

    Accepted 有效得分:100 有效耗时:247ms

    盯了半天的DLX,还是不会用链表操作,只能只用他的最优位置搜索了........

  • 0
    @ 2009-08-31 15:04:10

    Dancing Links果然很nb:

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

  • 0
    @ 2009-08-31 13:41:03

    请问下这题如果用深搜要怎么优化剪枝才能不超时,谢谢

  • 0
    @ 2009-08-31 12:14:54

    被封了可以立马解封,神......

  • 0
    @ 2009-08-30 18:52:50

    秒杀

  • 0
    @ 2009-08-26 20:16:35

    这题为什么看不到?

  • 0
    @ 2009-08-23 17:10:50

    飘过

  • 0
    @ 2009-08-23 13:05:43

    我来打酱油。。。

  • 0
    @ 2009-08-22 12:47:35

    .....

  • 0
    @ 2009-08-22 01:10:01

    这叫寂寞……

    别说我刷题解……

  • 0
    @ 2009-08-21 13:56:52

    太水了,这不叫题……

  • 0
    @ 2009-08-21 13:50:02

    很水的~~~

  • 1

信息

ID
1632
难度
8
分类
搜索 点击显示
标签
(无)
递交数
555
已通过
82
通过率
15%
被复制
1
上传者