去年做这道题，一直没有感觉。
现在学了hash以后就知道了
因为n的范围小，总共的状态不会超过2^n
所以搜索+hash就可以
其实判重直接在已经有的状态里找一遍有没有相同的也行。
因为就算2^n^2也不会超

DXE-SYF

点击查看程序源码+详细题解

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

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进制然后背包

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

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

可怜的90分啊~呜呜 TAT 

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

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分啊！！！！

楼上正解

这道题拿到之后第一反应就是宽搜，但是时间肯定很恶心。既然想到了宽搜，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

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

暴力bfs,秒杀

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

├ 测试数据 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

编译通过...

├ 测试数据 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

我做的不是题，是水

一晚上啊,我的时间就耗在这上面了！！！不过第一次写位运算的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是不会超的.

有人听懂没？都没听，好，那我就不说了.

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

编译通过...

├ 测试数据 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错误

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

伟大的位运算+搜索~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

宽搜hash。。秒杀