广搜+位运算+hash。

就是说我们把患病，不患病看做0、1。这样就是把n中病患与不患转换为了二进制串，按n=10来看，总共的状态就有0~2^10-1=1024种。我们假定对于第k个病，患病为1，不患为0。为了方便，我定义两个数描述一种药，那么对于药i就有a,a来描述，a的二进制如果第j位为1，表示用药i会使患上j病，a二进制如果第j为为0表示，用药i会解除j病。那么(每种状态 or a)and(a)=用i后的新状态。

hash判重我改了一下，就是说不用布尔数组。直接用step表示到i状态的最小步数，初始值为正无穷，如果到状态i的步数小于正无穷，那么就不扩展改点for i:=1 to m do

相关代码：

for i:=1 to m do

begin

x1:=0;x2:=0;

for j:=1 to n do

begin

read(t);

x1:=x1

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

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

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

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

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

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

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

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

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

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

为什么？ 谁有数据

我的第一次BFS+hash的AC。。。。

所谓的hash就是“给每个状态加个独一无二的编号，保证编号与状态的对应关系唯一”，然后开个布尔编号表。。。

状态为是否患病。。然后用药。。。。。

怎么建 Dijkstra图?bang bang wo.

终于AC了。。。

其实就是BFS+hash判重吧。。

不过，呃。。问一下，什么是hash呃？我查不到相关的资料，就自己想了个。

我想的hash就是类似于电脑上的MD5，给每个状态加个独一无二的编号，保证编号与状态的对应关系唯一。。不知道对不对。。。

编译通过...

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

很水

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

额.....写扯了......本来应该是宽搜....

结果我写成了深搜.............囧到正无穷......

BFS 利用位运算判重

每种药肯定是用一次就够了～重复用是没有意义的，而顺序的问题可以无视，如以下两种情况

1 4

4 1 4

肯定是先搜到第一种情况，第二种会由于状态重复而不入队

so water

楼下的位运算很好

好水啊。。。。。。。。。。。。。。。。

f,d:array[1..2000] of longint;

h:array[1..2048] of boolean;

m:array[1..100,1..2] of longint;

数组不用多大。。用位运算可以秒杀。。

一些常用的位运算。。要用到的用红色标了出来

功能| 示例 | 位运算

　　---|---|---|---|---|---|---|-+---|---|---|---|---|---|---|---|---|+---|---|---|---|---|---|---|---|

　　去掉最后一位 | (101101->10110) | x shr 1

　　在最后加一个0　 | (101101->1011010) | x shl 1

　　在最后加一个1　 | (101101->1011011) | x shl 1+1

　　把最后一位变成1　 | (101100->101101) | x or 1

　　把最后一位变成0　 | (101101->101100) | x or 1-1

　　最后一位取反 | (101101->101100) | x xor 1

　　[red]把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1))

　　把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1))[/red]

　　右数第k位取反　 | (101001->101101,k=3) | x xor (1 shl (k-1))

　　取末三位 | (1101101->101) | x and 7

　　取末k位　 | (1101101->1101,k=5) | x and (1 shl k-1)

　　[red]取右数第k位　 | (1101101->1,k=4) | x shr (k-1) and 1[/red]

　　把末k位变成1　 | (101001->101111,k=4) | x or (1 shl k-1)

　　末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1)

　　把右边连续的1变成0 | (100101111->100100000) | x and (x+1)

　　把右起第一个0变成1 | (100101111->100111111) | x or (x+1)

　　把右边连续的0变成1 | (11011000->11011111) | x or (x-1)

　　取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1

　　去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1))

漏了个.

'The patient will be dead （.）

……………………………………

郁闷

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

BFS+位运算+细心 =1次AC ……

const

p:array[1..10]of longint=(1,2,4,8,16,32,64,128,256,512);

var

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

u:array[0..1100] of longint;

line:array[1..1100,1..2]of longint;

st,ed:longint;

i,j,k,n,m,d,ans,step:longint;

begin

read(n,m);

for i:=1 to m do

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

fillchar(u,sizeof(u),100);

fillchar(line,sizeof(line),0);

st:=1;ed:=2;

line[st][1]:=p[n]*2-1;

line[st][2]:=0;

k:=0; ans:=1000000;step:=0;

while (sted)and(step

把人是否健康作为状态

就有2^10种

然后只要广搜就可以了.

第一次提交没看到注释,害我80分没能AC

注释里面说了,无解也要输出一串字符

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

#include

#include

using namespace std;

typedef unsigned int INT

;

INT e[10];

INT tree[2048][2];

INT rec[101][2];

bool hash[1025];

int main() {

int n,m,l=0,r=1;

e[0]=1;

for (int i=1; i

不加优化的暴搜 ms……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

BFS+hash，好水的搜啊，一次AC

囧死。。。1..Maxm写成 1..Maxn。n次存取非法。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

const bigprime=19997;

Maxn=10;

Maxm=100;

type point=^rec;

rec=record

sum:longint;

v:integer;

next:point;

end;

var n,m:longint;

a:array[1..Maxm,1..Maxn]of integer;

cure,affect:array[1..Maxm]of integer;

hash:array[0..bigprime-1]of point;

q:array[0..400000]of rec;

procedure init;

var i,j:integer;

begin

readln(n);

readln(m);

for i:=1 to m do

begin

cure[i]:=0; affect[i]:=0;

for j:=1 to n do

begin

read(a);

if (a=0)or(a=-1) then cure[i]:=cure[i] or (1 shl (j-1));

if a=-1 then affect[i]:=affect[i] or (1 shl (j-1));

end;

readln;

end;

end;

procedure print(t:longint);

begin

writeln(t);

halt;

end;

function update(a,p:integer):longint;

begin

exit(a and cure[p] or affect[p]);

end;

function find(a:integer;sum:longint):boolean;

var now:point;

begin

if a=0 then begin print(sum); exit(false); end;

now:=hash[a mod bigprime];

while nowNIl do

begin

if now^.v=a then exit(true);

now:=now^.next;

end;

new(now);

now^.v:=a;

now^.sum:=sum;

now^.next:=hash[a mod bigprime];

hash[a mod bigprime]:=now;

exit(false);

end;

procedure bfs;

var i:integer;

f,r:longint;

begin

find(1 shl n -1,0);

f:=0; r:=1;

q[1].v:=1 shl n -1;

repeat

inc(f);

for i:=1 to m do

if not(find(update(q[f].v,i),q[f].sum+1)) then

begin

inc(r);

q[r].v:=update(q[f].v,i);

q[r].sum:=q[f].sum+1;

end;

until f>=r;

end;

begin

init;

bfs;

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

end.

呜呜~~~~(>_=tail;

end;

begin

init;

bfs;

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

end.

谁具体告诉我一下怎么哈希