Vijos1026 毒药?解药?的两种特殊题解

和众位神牛的方法不同,我使用了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<<(j-1));
-1:bFalse[i]:=bFalse[i] or (1<<(j-1));
end;
end;
readln;
end;
end;

procedure IDS;
var
ansDeep:longint;
noAns:boolean;

procedure print(d:longint);
begin
if d>-1 then writeln(d)
else writeln(‘The patient will be dead.’);
halt;
end;

procedure _IDS(deep:longint;now:longint);
var
i:longint;
begin
if h[now] then exit;
h[now]:=true;
if deep=ansDeep then begin
noAns:=false;
if now=(1<<n)-1 then print(ansDeep);
h[now]:=false;
exit;
end;
for i:=1 to m do
_IDS(deep+1,(now or bTrue[i]) and (not bFalse[i]));
h[now]:=false;
end;

begin
ansDeep:=0;
randomize;
fillChar(h,sizeof(h),0);
repeat
noAns:=true;
inc(ansDeep);
_IDS(0,0);
until noAns or (ansDeep>=5+random(2));
print(-1);
end;

begin
init;
IDS;
end.

 

Malash
2009年10月10日 下午

这个题与Vijos 1019 补丁VS错误极为相似。对于1019这个题,许多人都想到了将每种状态对应成图中的点,每次安装补丁对应一条边,然后求一下单源最短路——SPFA。该算法写起来简单,效率也很高。

那么对于1026这道题,是不是也能这样做呢?

如果你有这个想法,然后去百度一下,结果只能是被泼了一盆凉水——第一条搜索结果赫然写着:“显然是一个NP问题……只能考虑搜索。”

Vijos1026 毒药?解药?的两种特殊题解 - Malash - Malash的OI生涯

据我猜测,许多人因此放弃了这个想法。

但我不认为此题必须要用搜索。在今天下午我用极其WS的方法Cheat掉这个题后,我又考虑了一下这个问题,发现转图的想法并没有不合理的地方。晚上(刚才),我用了不到15分钟写出了代码,并一次AC

编译通过…
├ 测试数据 01:答案正确… 0ms
├ 测试数据 02:答案正确… 0ms
├ 测试数据 03:答案正确… 0ms
├ 测试数据 04:答案正确… 0ms
├ 测试数据 05:答案正确… 0ms
├ 测试数据 06:答案正确… 0ms
├ 测试数据 07:答案正确… 0ms
├ 测试数据 08:答案正确… 0ms
├ 测试数据 09:答案正确… 0ms
├ 测试数据 10:答案正确… 0ms
————————-
Accepted 有效得分:100 有效耗时:0ms

秒杀。。。。

原理其实很简单,由于病症最多只有10个,可以转化成二进制,最大为1024-1。我们将所有可能出现的病症组合情况转为十进制后作为图的顶点,对于每一个点i,枚举每一种药品k,用位运算得出该组合转变为的组合j,然后在i和j间连一条权值为1的边。最后用Dijkstra或其他算法计算出全病0到痊愈1 shl n-1之间的最短路径长度,即为答案。若不存在路径则无解。

源代码如下:
program vijos_1026;

const
maxN=10;
maxM=100;
maxV=1<<maxN-1;
maxLong=maxLongint>>2;

var
n,m,v:longint;
bTrue,bFalse:array[1..maxM] of longint;
a:array[0..maxV,0..maxV] of longint;

procedure init;
var
i,j,t:longint;
begin
readln(n);
v:=1<<n-1;
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<<(j-1));
-1:bFalse[i]:=bFalse[i] or (1<<(j-1));
end;
end;
readln;
end;
end;

procedure main;
var
i,j,k:longint;
begin
fillDWord(a,sizeof(a)>>2,maxLong);
for i:=0 to v do begin
a[i,i]:=0;
for k:=1 to m do begin
j:=(i or bTrue[k]) and (not bfalse[k]);
if a[i,j]>1 then a[i,j]:=1;
end;
end;
end;

function dijkstra(s,t:longint):longint;
var
i,j,k,min:longint;
d:array[0..maxV] of longint;
b:array[0..maxV] of boolean;
begin
for i:=0 to v do d[i]:=a[s,i];
fillChar(b,sizeof(b),false);
b[s]:=true;
for i:=1 to v do begin
min:=maxLong;
for j:=0 to v do
if (not b[j]) and (d[j]<min) then begin
min:=d[j]; k:=j;
end;
if min=maxLongint then exit(d[t]);
if k=t then exit(d[t]);
b[k]:=true;
for j:=0 to v do
if (not b[j]) and (d[j]>d[k]+a[k,j]) then
d[j]:=d[k]+a[k,j];
end;
exit(d[t]);
end;

procedure print;
var
ans:longint;
begin
ans:=Dijkstra(0,1<<n-1);
if ans<maxLong then writeln(ans)
else writeln(‘The patient will be dead.’);
end;

begin
init;
main;
print;
end.

 

最后,我想引用写作《背包问题九讲》的dd_engi大牛的一句话:
“思考”是一个OIer最重要的品质。简单的问题,深入思考以后,也能发现更多。”

 

 

Malash

2009年10月11日0:03:00

文章评论: