题解 - Vijos

0

11022908 LV 9 @ 2009-07-24 20:26:24

while h

0

飓风音速 LV 10 @ 2009-07-22 20:58:01

BFS+判重。判重我借助了字符串

0

zsy90943 LV 10 @ 2009-07-21 14:02:29

SPFA、

看来要多做做位压的题了、

K为目标状态、0没病、1有病(PS:怎么那么别扭额- -)

zheng[i]

if L=0,-1 Inc(zheng[i])

fu[i]

if L=-1 Inc(fu[i]) fu[i] shl 1

吃了I药后的状态、(k or fu[i]) and zheng[i]

随便写写、、大牛勿喷、、

0

wyc4662 LV 10 @ 2009-07-15 10:58:50

var n,m,g,h,l,k,i:integer;

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

f:array[0..1024,1..11] of boolean;

f2:Array[0..1024] of integer;

ch:boolean;

function check:boolean;

var i,j:integer;

begin

for i:=1 to k-1 do

for j:=1 to n do

if ff[k,j] then break else

if j=n then begin check:=false; exit; end;

check:=true;

end;

function check2:boolean;

var i:integer;

begin

i:=1;

while f[k-1,i]=true do i:=i+1;

if i=n+1 then check2:=true else check2:=false;

end;

begin

read(n,m);

for g:=1 to m do

for h:=1 to n do

read(a[g,h]);

k:=1;

while lk do begin

for g:=1 to m do begin

f[k]:=f[l];

for h:=1 to n do

if a[g,h]=1 then f[k,h]:=true else

if a[g,h]=-1 then f[k,h]:=false;

if check then begin

f2[k]:=f2[l]+1;

k:=k+1;

if check2 then begin write(f2[k-1]); exit; end;

end else for h:=1 to n do f[k,h]:=false;

end;

l:=l+1;

end;

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

end.

第三和第四个点卡了N久，原来死循环了……

0

mike_nzk LV 10 @ 2009-06-23 16:37:38

P1019弱化版

把1019的程序拿来改了改，1次AC

0

我不是小shy LV 8 @ 2009-06-08 22:53:47

这个题不是状态压缩Dp么...?

0

gwm0415 LV 4 @ 2009-05-15 16:46:45

var i,j,kkk,yyy,n,m:integer;

boo:boolean;

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

b,bb:array[0..1024] of boolean;

c,d,dd:array[1..11]of integer;

procedure fdq(k:integer);

var i,j,s:integer;

begin

if k>n then begin

s:=0;

for i:=1 to n do

inc(s,c[i]*d[i]);

dd:=d;

if bb then begin

for j:=1 to n do

if a[yyy,j]=1 then dd[j]:=0 else

if a[yyy,j]=-1 then dd[j]:=1;

s:=0;

for i:=1 to n do

inc(s,c[i]*dd[i]);

if not b then begin

b:=true;

boo:=false;

end;

end;

end else begin

d[k]:=0;

fdq(k+1);

d[k]:=1;

fdq(k+1);

end;

end;

begin

readln(n);

readln(m);

for i:=1 to m do begin

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

readln;

end;

fillchar(b,sizeof(b),false);

c[1]:=1;

for i:=2 to n do c[i]:=c*2;

b[c[n]*2-1]:=true;

for kkk:=1 to 10000 do begin

boo:=true;

bb:=b;

for yyy:=1 to m do

fdq(1);

if b[0] then begin

writeln(kkk);

halt;

end;

if boo then begin

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

halt;

end;

end;

end.

0

怪盗~基德 LV 10 @ 2009-05-13 14:59:19

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第n次提交了，细节啊呜~~~~~~~~~~~~~~~~

hash+递归

var i,j,kkk,yyy,n,m:integer;

boo:boolean;

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

b,bb:array[0..1024] of boolean;

c,d,dd:array[1..11]of integer;

procedure fdq(k:integer);

var i,j,s:integer;

begin

if k>n then begin

s:=0;

for i:=1 to n do

inc(s,c[i]*d[i]);

dd:=d;

if bb then begin

for j:=1 to n do

if a[yyy,j]=1 then dd[j]:=0 else

if a[yyy,j]=-1 then dd[j]:=1;

s:=0;

for i:=1 to n do

inc(s,c[i]*dd[i]);

if not b then begin

b:=true;

boo:=false;

end;

end;

end else begin

d[k]:=0;

fdq(k+1);

d[k]:=1;

fdq(k+1);

end;

end;

begin

readln(n);

readln(m);

for i:=1 to m do begin

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

readln;

end;

fillchar(b,sizeof(b),false);

c[1]:=1;

for i:=2 to n do c[i]:=c*2;

b[c[n]*2-1]:=true;

for kkk:=1 to 10000 do begin

boo:=true;

bb:=b;

for yyy:=1 to m do

fdq(1);

if b[0] then begin

writeln(kkk);

halt;

end;

if boo then begin

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

halt;

end;

end;

end.

0

lijian3256 LV 10 @ 2009-04-03 13:22:13

printf("The patient will be dead.\n");

写成了printf("The patient will be dead\n");

结果一个劲说我超时。。。害我在那看哪里超时了。。。。

0

chengrui LV 10 @ 2009-03-27 12:32:40

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

bfs+hash

0

blacksnow LV 10 @ 2009-03-14 23:02:38

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

刚开始,i打成j,还有30分.......(有3个答案是2);

第二次,来了个A*算法,90,不知那错...(后来发现没有注意到'the ........')

最后,干脆弄个简单的HASH,秒杀.....

这道题教育我们,难度2的题目,根本不用去想双向动规和A*

0

风之 LV 8 @ 2009-03-14 16:59:00

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

哈哈!

0

李肥888 LV 10 @ 2009-03-11 13:06:08

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC，感觉棒极了。

var

n,m,i,j,i1,j1,q1,q2,tmpint:integer;

tmp:array[1..10]of integer;

list:array[1..30000,1..10]of ^integer;

b:array[1..30000]of ^integer;

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

boo1,boo2:boolean;

begin

readln(n);

readln(m);

for i:=1 to m do

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

for i:=1 to n do begin

new(list[1,i]);

list[1,i]^:=-1;

end;

q1:=1;q2:=1;

new(b[1]);

b[1]^:=0;

while q1m then begin

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

halt;

end;

for i:=1 to m do begin

for j:=1 to n do tmp[j]:=list[q1,j]^;

for J:=1 to n do begin

tmpint:=tmp[j]+a;

if tmpint0 then tmp[j]:=0;

if tmpint=0 then tmp[j]:=0;

end;

boo2:=true;

for i1:=1 to q2 do begin

boo1:=false;

for j1:=1 to n do if list[i1,j1]^tmp[j1] then begin

boo1:=true;

break;

end;

boo2:=boo2 and boo1;

if not boo2 then break;

end;

if boo2 then begin

inc(q2);

for j:=1 to n do begin

new(list[q2,j]);

list[q2,j]^:=tmp[j];

new(b[q2]);

b[q2]^:=b[q1]^+1;

end;

boo1:=true;

for j:=1 to n do if tmp[j]0 then begin

boo1:=false;

break;

end;

if boo1 then begin

writeln(b[q2]^);

halt;

end;

end;

end;

inc(q1);

end;

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

end.

0

cgy4ever LV 10 @ 2009-01-26 22:29:35

位运算 BFS 记忆化

不错的题目.

0

WSC_1992 LV 8 @ 2009-01-17 15:18:30

[red]**第100道纪念**[/red]

标准的宽搜，用了Hash可以秒杀

0

他在那里 LV 7 @ 2008-11-09 12:36:44

BFS判断是否重复时，就从后向前扫描一遍就得了。根本不用HASH表。

题目很适合初学者

0

curimit LV 10 @ 2008-11-04 13:48:18

DP 34行AC

0

白c超超 LV 10 @ 2008-11-02 15:22:21

这是数据的位运算读入

cure[i]:=0;

for j:=1 to n do

if a[j]=1 then cure[i]:=cure[i] shl 1 else cure[i]:=(cure[i]+1) shl 1;

cure[i]:=cure[i] shr 1;

anti[i]:=0;

for j:=1 to n do

if a[j]=-1 then anti[i]:=(anti[i] + 1) shl 1 else anti[i]:=anti[i] shl 1;

anti[i]:=anti[i] shr 1;

然后在进行搜索或者最短路径求解的时候

go:=(q[l] and cure[i]) or anti[i];就可以了

0

liuyuqing LV 3 @ 2008-11-01 19:38:30

典型贪心法

0

zhujf553 LV 10 @ 2008-10-30 18:39:36

spfa+位运算，两次ac，第一次是因为没做无解判断

题解

149 条题解

毒药？解药？

信息

状态

开发

支持

题解

149 条题解

毒药？解药？

信息

状态

开发

支持

还没有账户？

登录