149 条题解

  • 0
    @ 2013-02-16 10:13:53
  • 0
    @ 2012-10-31 16:47:41

    感谢发最短路题解的大牛们 真是个好思路!

  • 0
    @ 2012-07-29 08:43:03

    var

    p:array[0..3000]of boolean;

    f:array[0..3000]of longint;

    c,a,b:array[1..200]of longint;

    i,j,n,m,s:longint;

    procedure sou(x:longint);

    var s,i:longint;

    begin

    for i:=1 to m do begin

    s:=x;

    s:=s or a[i];

    s:=s and b[i];

    if (p=false)or(p)and(f[x]+10 then a[i]:=a[i]+s;

    if c[j]>=0 then b[i]:=b[i]+s;

    s:=s*2;

    end;

    end;s:=s-1;

    f[0]:=0;p[0]:=true;

    sou(0);

    if p then begin

    writeln(f);exit;

    end;

    writeln('The patient will be dead.');

    end.

    直接背包嘛,弄成2进制然后背包

  • 0
    @ 2012-07-17 11:53:39

    我用bfs+hash判断药效是否有重复

     测试数据 04:运行时错误...|错误号: 103

    可怜的90分啊~呜呜 TAT 

    只是在第4个点一直是这个错误,,谁能解释这是怎么回事啊

  • 0
    @ 2010-04-13 18:21:17

    type arr=array[1..100]of longint;

    var a:array[1..100,1..10]of longint;

    b:array[1..100]of longint;

    i,min,j,n,m,k:longint;

    procedure change(k:longint;var b:arr);

    var i:longint;

    begin

    for i:=1 to m do

    if a[k,i]=1 then begin

    if b[i]=-1 then b[i]:=1;

    end

    else if a[k,i]=-1 then begin

    if b[i]=1 then b[i]:=-1;

    end;

    end;

    function ss(b:arr):boolean;

    var i:longint;

    begin

    for i:=1 to m do

    if b[i]1 then exit(false);

    exit(true);

    end;

    procedure asd(step,j:longint;b:arr);

    var i:longint;

    c:array[1..100]of longint;

    begin

    if minstep-1 then min:=step-1;

    exit;

    end;

    for i:=1 to n do

    if ij then

    begin

    c:=b;

    change(i,c);

    asd(step+1,i,c);

    end;

    end;

    begin

    readln(m);

    readln(n);

    for i:=1 to n do

    for j:=1 to m do read(a);

    for i:=1 to m do b[i]:=-1;

    min:=maxlongint;

    for k:=1 to 200 do begin

    asd(1,0,b);

    if minmaxlongint then begin

    writeln(min);

    exit;

    end;

    end;

    writeln('The patient will be dead.');

    end.

    怎么剪枝啊!DFS80分啊!!!!

  • 0
    @ 2010-04-03 14:58:25

    楼上正解

  • 0
    @ 2010-03-08 23:48:10

    这道题拿到之后第一反应就是宽搜,但是时间肯定很恶心。既然想到了宽搜,HASH是必须要解决的。这里就用到了北京集训大牛传授的位运算。位运算的公式能有十多条,但是用不上那么多,只有皮毛的 and 和or 就解决问题。但是HASH映射方式解决了之后,会发现这其实是一道图论题。通过药物,A状态能到B状态,则AB边权值为1,最后一个spfa求单元最短路径就ok了。

    先说一下hash。比如一共有三种病,那么状态的二进制表示就是111(就是(1 shl n)-1)。对应的十进制是7,于是就从7downto1,并枚举每一种药,把能连通的都连上。这里要特别注意顺序,必须是downto 否则就会悲剧。(我在这wa了好久)。

    再说一下我怎么处理药的。我分为两个数组,一个治疗一个破坏(= =!)。如果值为1,则读入到治疗数组中。治疗数组的初始值为111,治疗的就变成0;如果值为-1,则读入到破坏数组中。破坏数组的初始值为0,破坏了就变成1。最后将他们转化为十进制,再用状态(7 downto 1)来or破坏and治疗,就得到了此种药对此状态的治疗后状态。注意,必须先破坏后治疗,因为如果本身有了这个病,再得,就没效果了,所以如果你本身有这个病,然后自己治好了,然后又得。。。在这又wa掉了。

    最后是spfa,注意条件,就ok了。

    最后帖程序。

    type

    arr=array[0..11]of integer;

    var

    dist:array[0..1024]of integer;

    p:array[0..1024000]of integer;

    a:array[0..1024,0..1024]of integer;

    cure,damg:array[0..100]of integer;

    s1,s2:arr;

    m,n,nn,i,j,head,tail,now,w:integer;

    procedure SPFA;

    begin

    for i:=0 to nn do dist[i]:=-1; dist[nn]:=0;

    head:=1;tail:=1;p[head]:=nn;

    while head

  • 0
    @ 2009-11-13 16:48:16

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

    DFS,第一次第8个超时了

    加了个预处理就秒了。。。

    program p1026;

    const ft:array[0..11]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048);

    var i,j,k,n,m,l:longint;

    f:array[0..3000]of integer;

    a:array[1..100,1..10]of integer;

    d:array[1..1024,1..100]of integer;

    procedure sort(p:longint);

    var i,j,k:longint;

    begin

    for i:=1 to m do

    begin

    k:=d[p,i];

    if (f[k]=0)or(f[p]+1

  • 0
    @ 2009-11-08 10:25:10

    暴力bfs,秒杀

  • 0
    @ 2009-11-07 23:12:45

    用二进制数的十进制码表示状态,于是共有1024个点,标号0--1023.

    对于每个点x,应用药剂i得到点y则在x,y之间连一条边,权为1。

    之后对于2^n -1,应用单源最短路算法,输出dist[0]

  • 0
    @ 2009-11-04 21:33:28

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-11-02 21:36:05

    编译通过...

    ├ 测试数据 01:运行时错误...|错误号: 128

    ├ 测试数据 02:运行时错误...|错误号: -1073741819

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

    ├ 测试数据 04:运行时错误...|错误号: -1073741819

    ├ 测试数据 05:答案错误...程序输出比正确答案长

    ├ 测试数据 06:答案错误...程序输出比正确答案长

    ├ 测试数据 07:运行时错误...|错误号: -1073741819

    ├ 测试数据 08:运行时错误...|错误号: -1073741819

    ├ 测试数据 09:答案错误...程序输出比正确答案长

    ├ 测试数据 10:答案错误...程序输出比正确答案长

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

    Unaccepted 有效得分:10 有效耗时:0ms

    #include

    using namespace std;

    struct h

    {

    int x[11];

    int num;

    }a[10000];

    int n;

    bool f(int y)

    {

    for(int i=1;i>n>>m;

    a[1].num=0;

    for(i=1;ib[i][j];

    for(i=1;i

  • 0
    @ 2009-11-01 08:50:24

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program ex;

    type arr=array[1..10]of longint;

    var i,j,n,m:longint;

    med:array[1..100]of arr;

    start,now:arr;

    hash:array[0..1024]of boolean;

    function check_hash(x:arr):boolean;

    var i,j,t:longint;

    has:longint;

    begin

    has:=x[1];

    t:=1;

    for i:=2 to m do

    begin

    t:=t*2;

    inc(has,t*x[i]);

    end;

    if not hash[has] then

    begin

    hash[has]:=true;

    exit(false);

    end

    else

    exit(true);

    end;

    procedure init;

    var i,j:longint;

    begin

    fillchar(hash,sizeof(hash),false);

    readln(m);

    readln(n);

    for i:=1 to n do

    begin

    for j:=1 to m do

    begin

    read(med);

    if med=0 then med:=-1

    else if med=-1 then med:=0;

    end;

    readln;

    end;

    for i:=1 to m do

    begin

    start[i]:=0;

    end;

    check_hash(start);

    end;

    function finish(x:arr):boolean;

    var i,j:longint;

    begin

    for i:=1 to m do

    if x[i]1 then exit(false);

    exit(true);

    end;

    procedure bfs;

    var i,j,h,t:longint;

    quecount:array[1..650]of longint;

    questate:array[1..650]of arr;

    begin

    fillchar(quecount,sizeof(quecount),0);

    fillchar(questate,sizeof(questate),0);

    h:=1;t:=1;

    quecount[1]:=0;

    questate[1]:=start;

    while h

  • 0
    @ 2009-10-30 08:07:03

    我做的不是题,是水

  • 0
    @ 2009-10-28 21:42:12

    一晚上啊,我的时间就耗在这上面了!!!不过第一次写位运算的BFS,收获还是很大的。

    调试了两个小时的收获是:shl i是不可以的,要shl i-1,因为i 的初值都是1了。

    因为一共只有10种病,我们就用病来代表状态。用f1[i],f2[i]分别表示能治和能得的病。f1中0表示能治,f2中1表示能得,这样新状态now2:= now and f1[i] or f2[i] and 一般是变成0,or 一般是变成1.

    刚开始now=1111111...,一直变成00000....,最多也就1 shl (n-1)种情况,BFS是不会超的.

    有人听懂没?都没听,好,那我就不说了.

  • 0
    @ 2009-10-24 22:33:50

    如果你的3、4组数据过不了,请看万恶的注释

  • 0
    @ 2009-10-23 21:21:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    位运算。宽搜。hash判重。。。。详情可参见CTSC99 补丁vs错误

  • 0
    @ 2009-10-17 21:09:10

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

    伟大的位运算+搜索~~

  • 0
    @ 2009-10-14 17:39:56

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    宽搜hash。。秒杀

  • 0
    @ 2009-10-11 00:03:53

    和众位神牛的方法不同,我使用了IDS+位运算+hash

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    也许Vijos的数据出的是无心的,但遇到了“有心”偷懒的我,用了一个比较WS的IDS,结果第四个点TLE了。

    N次改变代码退出顺序,又寄希望于Puppy,结果依然TLE。

    后来套来了输出数据,加了一个不大合理的“剪枝”:until ansDeep>=5

    终于第四个不超时了,但第10个点剪过了,输出答案错误。

    又改成until ansDeep>=5 ,结果第10个过了,第4个又超时了。。。

    无奈,考验RP的时候到了

    until ansDeep>=5+random(2);

    交了两次,在Puppy的帮助下,终于AC了。。。。。。

    声明:谁要是拿我的代码去刷这个题结果导致AC率的下降,与本人无关!

    (谁叫你cheat来着。。。。。)

    源代码如下:

    program vijos_1026;

    const

    maxM=100;

    maxH=1023;

    var

    n,m:longint;

    bTrue,bFalse:array[1..maxM] of longint;

    h:array[0..maxH] of boolean;

    procedure init;

    var

    i,j,t:longint;

    begin

    readln(n);

    readln(m);

    for i:=1 to m do begin

    for j:=1 to n do begin

    read(t);

    case t of

    1:bTrue[i]:=bTrue[i] or (1

信息

ID
1026
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3640
已通过
1102
通过率
30%
被复制
17
上传者