SPFA+位运算

...总算过掉它了..感觉这题比毒药解药还要困难一些...但比CTSC的原数据要弱一些

.CTSC的数据原先n

搜索或spfa

详见http://blog.sina.com.cn/s/blog_5dc10e510100cje6.html

type csa=array[1..2] of longint;

var

n,m,x,i,j,y,l,r:longint;

b,f:array[1..100] of csa;

t:array[1..100] of longint;

bool:array[0..32767] of longint;

d:array[1..500000] of longint;

ch:char;

begin

readln(n,m);x:=1 shl n -1;

for i:=1 to m do

begin

read(t[i]);read(ch);

for j:=1 to n do

begin

read(ch);y:=1 shl (j-1);

if ch='+' then b:=b or y

else if ch='-' then b:=b or y;

end;

read(ch);

for j:=1 to n do

begin

read(ch);y:=1 shl (j-1);

if ch='+' then f:=f or y

else if ch='-' then f:=f or y;

end;

f:=f xor x;

readln;

end;

for i:=0 to 32767 do bool[i]:=maxlongint;

bool[x]:=0;l:=1;r:=1;d[1]:=x;

while l

位运算bfs..

我的CTSC数据包里的这题 标准输出错了2个 - -

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

wa了9次,终于AC...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最多2^N种状态,用一个HASH[0..32767]数组存每种方案的最小耗时

BFS求解

数据这么弱，愧对我程序

编译通过...

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

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

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

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

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

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

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

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

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

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

直接bfs+位运算，不判重，开个300000队列。。

编译通过...

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

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

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

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

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

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

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

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

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

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

搞了半天，不是我的错，是 凭测机 的错。 一遇到 1019的 题目就一直RUNNING。

我直接 用的 宽搜，再加上个剪枝。 所以 第3个点525MS 其他都0MS。！哈哈！

虽然这道题目 宽搜算法 不能保证最优。 但是数据太弱了。直接宽 就行了！

若要 使宽搜正确，把注释符号的内容加上，就OK了。 round是判重函数。

function round(a:node):boolean;

var

x:longint;

begin

for x:=1 to op do

if same(a,blok[x]) then

// begin

// if a.time

MAB 我排序的时候用的STRING[15]没有CHAR不知道为什么会错 多交了3次

第一次80，原来这题不能简单判重，有些状态可以重复达到并且更新最优值

第1800次提交+BFS+位运算=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+位运算=秒杀……

读入数据的时候要将Bi+、Bi-、Fi+、Fi-都分别处理成2进制数，再处理的时候都用位运算……不然容易超时……前几次我都是因为这个最后两点TLE……

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

标号法 一次AC 第59题

注意BFS的话 第一次出现的不一定是最优解

BFS+位运算 第100题啊~~~

本来以为可以一次AC的，没想到第一次搜到的可行解并不一定是最优解！！！！！

而且碰到搜索的同样情况的时候还要比较原来的最优值，取小的！

不幸啊...居然把或搞成了异或...

minheap+hash+bfs=AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

呵呵，让ZKKMJ先发言了，我在讨论中讲一下我的解法吧，仅供参考！

我的解法有些DP的味道，呵呵

编译通过...

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

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

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

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

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：运行时错误...|错误号: -1073741819

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：40 有效耗时：0ms

编译通过...

├ 测试数据 01：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 02：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 03：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 04：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 05：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 06：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 07：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 08：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 09：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 10：运行时错误...| 错误号: 106 | 无效数字格式

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

Unaccepted 有效得分：0 有效耗时：0ms

...交错程序了

编译通过...

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

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

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

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

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

├ 测试数据 06：答案错误...　├ 标准行输出 15

　├ 错误行输出 17

├ 测试数据 07：答案错误...　├ 标准行输出 22

　├ 错误行输出 23

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

├ 测试数据 09：答案错误...　├ 标准行输出 338

　├ 错误行输出 676

├ 测试数据 10：答案错误...　├ 标准行输出 644

　├ 错误行输出 164...

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

Unaccepted 有效得分：50 有效耗时：0ms

终于AC！感谢BOYZKK！我们都是ZKK！

用堆优化的DIJ最短路为什么有7个点输出是0啊。。。本来想用SPFA的但想到数据可能很WS所以用这个保证不超时。。。但结果这么郁闷。。。诶~~早知道SPFA可以就用他了~~

回ntzhouhao：

SPFA=宽搜 ^_^

啊啊啊啊啊啊为什么用10分钟写个SPFA就一次AC了。。。。

第一次写堆的DIJ就受挫了。。呃啊。。90行啊。。泪。

预处理那个Fi-时把不是‘-’的都用1标上

for j:=1 to n do begin

case s[j] of

'+':begin inc(fp[i]); inc(fm[i]); end;

'0':inc(fm[i]);

end;

if j=n then break;

fp[i]:=fp[i] shl 1;

fm[i]:=fm[i] shl 1;

end;

这样在用的时候用一个AND 就可以了。（P是+，M是-）

while bf do begin

l:=gout;

for i:=1 to m do

if ( l and bp[i] = bp[i] ) and ( l and bm[i] = 0 ) then begin

r:=l or fp[i];

r:=r and fm[i];

if min[r]>min[l]+time[i] then begin

min[r]:=min[l]+time[i];

if vis[r]=0 then gin(r);

end;

end;

end;