题解

139 条题解

  • 0
    @ 2009-10-25 10:29:30

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    剪枝写错了,囧啊囧得我牙都掉了~~~~~~~~~冏

    PS:我的头标原本是有牙的

  • 0
    @ 2009-10-25 10:27:21

    orz ,,强大的剪枝

    判断还未枚举到的列,若有一列3个字母都确定了,但有无进位都不满足,说明当前的字母顺序错误,直接EXIT.

  • 0
    @ 2009-10-25 10:36:51

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

    终于秒杀了

    感谢所有写题解的大牛

    —————————begin—————————————————

    从右到左举字符串一和二(字母)的状态 第三个用算的(看符不符合 处理一下)

    再来一个超级强减枝

    因为字母重复所以每一次递归都

    从右到左刷一下看每一列上 加或不加1(进位) 看符不符合

    —————————end.—————————————————

  • 0
    @ 2009-10-25 10:38:30

    真的猛士.要敢于直面不断的UNAC.和直线下降的AC率.

    谢谢大牛的那个强剪枝..90分N久后被点化.

    然后.倒着搜这点很诡异.很没道理- -

  • 0
    @ 2009-10-24 21:23:08
  • 0
    @ 2009-10-09 21:26:28

    巨水!

    按位枚举的裸搜 90分!

    按字母枚举的裸搜 30分!

    第九个点 牛啊

  • 0
    @ 2009-10-06 17:36:21

    我的搜索就是差啊!~

  • 0
    @ 2009-10-02 15:12:19

    我的第一百个AC!!!!!

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    两个半小时+160行=0MS

  • 0
    @ 2009-09-30 21:49:41

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

    郁闷,一直纠结在90分,第九点(原题数据貌似第8点)真是太恐怖了.......

    不断地剪枝,这点在Pascal运行上从20秒+变到5秒...再变到9秒(用了链表居然更慢了,大概范围太小了)....再变到了3秒,彻底无语了(但是貌似这个程序在puppy上可以过,puppy真是高效).....数学课上突然想起了那道卢斯加法表,弱弱的加了几句话,居然秒出.....

    只是搜索再加些白痴的剪枝,虽不比各位大牛,但是完全是独立思考AC的,自认为比那些看了题解后吹嘘自己,吹嘘高斯消元法的人好些

    Ps:最后一次的优化在于先试探性的找出0的位置

  • 0
    @ 2009-09-27 17:51:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    从大到小枚举数字+再加入可行性剪枝+按照字母从右到左从上到下的出现顺序搜+搜出一种方案以后再判断其是否合法+Vivid Puppy=秒杀AC

    第一次交的时候忘记判断搜出来的方案是否合法结果WA掉2个点……

  • 0
    @ 2009-09-16 00:41:05

    进制枚举+高斯消元

    总算勉强AC

    庆祝100题~

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 508ms

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

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

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

  • 0
    @ 2009-09-10 10:00:15

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    哈哈,秒杀了!

    注意要从大到小枚举。

    小剪枝+从大到小枚举(70行)。

  • 0
    @ 2009-09-02 13:40:20

    回溯时枚举数字要从大到小

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 25ms

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

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

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

    从小到大:

    编译通过...

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

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

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

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

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

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

    ├ 测试数据 07:答案正确... 134ms

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

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

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

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

    Unaccepted 有效得分:80 有效耗时:134ms

  • 0
    @ 2009-08-20 19:02:59

    瀑布汗。。。完全没剪枝。。。正向搜没过。。反向0秒。。什么世道啊。。。为什么这道题反向那么快啊。。是不是数据出出来就是吭正向搜的啊。。。还是题目特性啊。。。

  • 0
    @ 2009-08-18 19:05:03

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 150ms

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

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

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

    program alpha_;

    type

    ntype=array[1..26]of longint;

    ftype=array[0..25]of boolean;

    ctype=array['A'..'Z']of longint;

    var

    a,b,c:ntype;

    f:ftype;

    m:ctype;

    n,i,j,k:longint;

    sa,sb,sc:string;

    procedure init;

    begin

    readln(n);

    readln(sa);

    readln(sb);

    readln(sc);

    fillchar(m,sizeof(m),byte(-1));

    fillchar(a,sizeof(a),byte(-1));

    fillchar(b,sizeof(b),byte(-1));

    fillchar(c,sizeof(c),byte(-1));

    fillchar(f,sizeof(f),1);

    end;

    procedure cover(ch:char;k:longint);

    var i:longint;

    begin

    for i:=1 to n do

    begin

    if sa[i]=ch then a[i]:=k;

    if sb[i]=ch then b[i]:=k;

    if sc[i]=ch then c[i]:=k;

    end;

    end;

    function check(p:longint):boolean;

    var i:longint;

    begin

    check:=true;

    for i:=1 to p-1 do

    if (a[i]-1)and(b[i]-1)and(c[i]-1)

    then if ((a[i]+b[i]+1)mod n=c[i])or((a[i]+b[i])mod n=c[i])

    then continue

    else exit(false);

    end;

    procedure dfs(left,jin,p:longint);

    var i,j,k,t:longint;

    m1:ctype;

    a1,b1,c1:ntype;

    f1:ftype;

    begin

    if left=0

    then begin

    if p=0

    then

    if jin=0

    then

    begin

    for i:=1 to n-1 do

    write(m[chr(i+64)],' ');

    writeln(m[chr(n+64)]);

    halt;

    end

    else exit

    else

    if (m[sa[p]]+m[sb[p]]+jin)mod n=m[sc[p]]

    then dfs(left,(m[sa[p]]+m[sb[p]]+jin)div n,p-1);

    end

    else

    if (m[sa[p]]-1) and (m[sb[p]]-1)

    then

    if m[sc[p]]-1

    then

    if (m[sa[p]]+m[sb[p]]+jin) mod n=m[sc[p]]

    then dfs(left,(m[sa[p]]+m[sb[p]]+jin)div n,p-1)

    else exit

    else

    begin

    k:=(m[sa[p]]+m[sb[p]]+jin) mod n;

    t:=(m[sa[p]]+m[sb[p]]+jin) div n;

    m1:=m; a1:=a; b1:=b; c1:=c; f1:=f;

    if f[k]

    then begin

    f[k]:=false;

    m[sc[p]]:=k;

    cover(sc[p],k);

    if check(p)

    then dfs(left-1,t,p-1);

    m:=m1; a:=a1; b:=b1; c:=c1; f:=f1;

    end

    else exit;

    end

    else

    if m[sa[p]]=-1

    then begin

    m1:=m; a1:=a; b1:=b; c1:=c; f1:=f;

    for i:=n-1 downto 0 do

    if f[i]

    then begin

    f[i]:=false;

    m[sa[p]]:=i;

    cover(sa[p],i);

    if check(p)

    then dfs(left-1,jin,p);

    m:=m1; a:=a1; b:=b1; c:=c1; f:=f1;

    end;

    end

    else begin

    m1:=m; a1:=a; b1:=b; c1:=c; f1:=f;

    for i:=n-1 downto 0 do

    if f[i]

    then begin

    f[i]:=false;

    m[sb[p]]:=i;

    cover(sb[p],i);

    if check(p)

    then dfs(left-1,jin,p);

    m:=m1; a:=a1; b:=b1; c:=c1; f:=f1;

    end;

    end;

    end;

    begin

    init;

    dfs(n,0,n);

    end.

    考.. 第九个点..

  • 0
    @ 2009-08-11 22:09:14

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    vogec2那个剪枝是指数级的,非常地高效。自我推荐一下:

    http://blog.sina.com.cn/slyzcjf

    这里有我的一些题解,包括该题。

  • 0
    @ 2009-08-06 21:09:39

    .

    .

    .

    ├ 测试数据 09:答案正确... 603ms

    .

    .

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

    第九个点令人汗颜…………………………

    这题剪枝一定要狠~~~~~~~~~~~~~~~~~~~~~~~~

  • 0
    @ 2009-07-29 10:18:05

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var

    time :real;

    st1,st2,st3 :string;

    n,i :integer;

    a :array['A'..'Z']of integer;

    s,vis :array[0..26]of integer;

    function judge(i:integer):boolean;

    var

    k :integer;

    begin

    for k:=i downto 1 do

    if (a[st1[k]]>-1)and(a[st2[k]]>-1)and(a[st3[k]]>-1) then

    if ((a[st1[k]]+a[st2[k]])mod na[st3[k]])and

    ((a[st1[k]]+a[st2[k]]+1)mod na[st3[k]]) then exit(false);

    if (a[st1[k]]>-1)and(a[st2[k]]>-1) then

    if a[st1[k]]+a[st2[k]]>n then exit(false);

    if (a[st1[k]]>-1)and(a[st2[k]]>-1)and(a[st3[k]]>-1) then

    if ((a[st1[k]]+a[st2[k]]+1)mod n=a[st3[k]])

    and(a[st1[k]]+a[st2[k]]+1>n) then exit(false);

    exit(true);

    end;

    procedure dfs(k,jin,leng:integer);

    var

    i,p :integer;

    begin

    if k=0 then

    if jin=0 then

    begin

    for i:=1 to n-1 do

    write(a[chr(ord('A')+i-1)],' ');

    writeln(a[chr(ord('A')+n-1)]);

    halt;

    end else exit;

    if a[st1[k]]=-1 then

    begin

    if (a[st2[k]]=-1)or(a[st3[k]]=-1) then

    for i:=1 to leng do

    begin

    a[st1[k]]:=s[i];

    vis[s[i]]:=leng;

    s[i]:=s[leng];

    vis[s[i]]:=i;

    if judge(k) then dfs(k,jin,leng-1);

    vis[s[i]]:=leng;

    s[i]:=a[st1[k]];

    vis[s[i]]:=i;

    end

    else

    begin

    a[st1[k]]:=a[st3[k]]-a[st2[k]]-jin;

    if a[st1[k]]

  • 0
    @ 2009-07-24 09:15:54

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    老是第9组TLE

    自己又写了个剪枝 本来应该是很有效率 却因为i,j打反了 导致完全没用#24

    。。。。

  • 0
    @ 2009-07-14 18:11:12

    自己胡写总是90.....

    看过voyagec2大牛神解,瞬间改好0MS AC!!!!

    OTZ神牛..

信息

ID
1099
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
4720
已通过
1012
通过率
21%
被复制
22
上传者