如果用二进制数表示问题的状态，那么我们可以用0..2^n -1来表示所有的状态。

如果一个状态可以迁移到另一个状态，那么就是说，经过一种补丁可以修改它，这一类补丁中，应当取那个时间最小的。

然后Dijkstra,总共519ms通过。(Evolution smdCn)

DFS+HASH，可惜没有秒杀.......也许自己的DFS写的很扯吧。

话说我浪费了一次AC，将1019程序交到1017了............莫名的106

没有秒杀可能是什么原因？

晕啊...m

Program Vijos_P1019;

Var

a: Array [1..32768] Of Word;

b: Array [0..32767] Of Word;

d: Array [1..32768] Of dWord;

v: Array [0..32767] Of Boolean;

km, kn, rm, rn: Array [1..100] Of Word;

ti: Array [1..100] Of dWord;

i, j, mj, mjx, x, xa, t, l, r, m, n: dWord; c: Char;

Begin

ReadLn(n, m);

For i:=1 To m Do Begin

Read(ti[i], c);

For j:=1 To n Do Begin

Read(c);

km[i]:=km[i] Shl 1+Ord(c='+');

kn[i]:=kn[i] Shl 1+Ord(c'-')

End;

Read(c);

For j:=1 To n Do Begin

Read(c);

rm[i]:=rm[i] Shl 1+Ord(c='+');

rn[i]:=rn[i] Shl 1+Ord(c'-')

End

End;

r:=1 Shl n;

FilldWord(d, r, \(FFFFFFFF); d[1]:=0;
FillChar(v, r, True);
For i:=1 To r Do
Begin a[i]:=i-1; b:=i End;
a[1]:=r-1; a[r]:=0;
b[0]:=r; b[r-1]:=1;
While v[0] Do Begin
If d[1]=\)FFFFFFFF Then Break;

mj:=a[1]; mjx:=d[1]; x:=d[r]; xa:=a[r]; Dec(r); l:=2;

While la[l]

Then Begin

d[l Shr 1]:=d[l];

a[l Shr 1]:=a[l];

b[a[l]]:=l Shr 1;

Inc(l, l)

End

Else Break

End;

d[l Shr 1]:=x; a[l Shr 1]:=xa; b[xa]:=l Shr 1; v[mj]:=False;

For i:=1 To m Do

If (mj Or km[i]) And kn[i]=mj Then Begin

t:=(mj Or rm[i]) And rn[i]; x:=mjx+ti[i];

If (v[t]) And (x1 Do

If d[l Shr 1]>x

Then Begin

d[l]:=d[l Shr 1];

a[l]:=a[l Shr 1];

b[a[l]]:=l;

l:=l Shr 1

End

Else Break;

d[l]:=x; b[x]:=l; a[l]:=t

End

End

End;

If v[0] Then WriteLn(0) Else WriteLn(mjx)

End.

第一次看 m

...无语问苍天。

难道是字符串处理的问题。。我从早做到晚啊。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

杯具啊！第一次用chrome交了……

于是两次才过= =

话说我这题的程序在noicn的题库上才90分，不解

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

rp真好~~1次AC~~

用二进制表示状态BFS即可~~

原来想着spfa的，但最后两个T了，只好在邻接标上DFS了，结果秒杀= =

bfs+hash AC!

我加了一限制条件：若当前解劣于已有解，则停止扩展

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

加了点点位运算

SPFA建图超时。。。。(1

唉。。交了4次才AC。。

第一次，忘了复制程序。。No compiled。。

接着就是3次纠错了。。先做的毒药解药再做的这题，一些观念还是毒药解药的观念。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

话说，卡时是一个十分强大的东西.........

扩展节点大于300000直接输出就可以的说...........

额.........不会用位运算只好用数组模拟的小菜飘过 。。。。。。

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

我对自己无语了...

本来可以一次AC的...

但是由于很多题目无解时是输出-1,所以...第一次90分...

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

问题可表示为一张图.

错误的状态为顶点,补丁为边(从状态a使用某补丁变为状态b).

从而使问题转换为SSSP.

状态可用二进制表示,1为错误,0为无错.

不过初始化有一点点麻烦.

启发式dfs

注意，不要枚举二进制状态，枚举补丁！

第i个补丁，因为它的运行环境，所以状态是有限制的，这样可以减少枚举量。

位运算是精华！

一开始写宽搜，WA了。改成宽搜的时候会更改当前最优解。写完之后发现就是SPFA。看了题解才知道此题是一个隐式图。

begin

init;

spfa;

end.

生成图的dfs过程写得比较ws，嗯~