NOI OJ 6043 哆啦A梦的时光机 题解

搜索算法中是一个很重要的思想。宽搜能尽量快的找到最优解,但是在性能要求极高的地方宽搜的复杂度已经力不从心了。双向宽搜采用的是从终点与起点同时出发,在中间相遇而计算出最优解的搜索思想。本文通过NOI OJ 6043为例,讲一下双向宽搜的一般思路。

题目大意就是,时光机需要从时刻$S (0 < S < 1,000,000)$跳跃到时刻$T (0 < T < 1,000,000)$,当位于时刻$A$时,你可以跳转到时刻$A/2$(当$A$为偶数)、$A+1$、$A-1$、$A*2$,求最少需要的跳跃步数。

这题我一开始想到的是宽搜,但是提交上去却得到了一个TLE。在百般思索后我注意到,对于这个问题,每个合法的跳转步骤都:

  1. 不会相互影响;
  2. 可逆,如你可以从$A$跳到$A+1$,也可以从$A+1$跳到$A$;
  3. 边界性相同,如对于每个时刻$A$,都有相同的$A>0$。

最后我选择了双向宽搜。双向宽搜是通过从出发点比如$S$,和结束点比如$T$,同时开始宽搜的搜索方法。它对解决这样的问题非常好用,而且会极大地节约时间。

和单向宽搜一样,双向宽搜需要写一个标记数组。但是对于这道题我遇到了棘手的麻烦:比如当$S=999,999,T=500,000$时,最优的跳跃步骤是这样的:

$$
999,999 → 1,000,000 → 500,000
$$

我们发现出现了$1,000,000$——在时刻跳跃的过程中,我们可以暂时让时刻超出$999,999$的上界,我们甚至不知道暂时出现的“超限”出的时刻的上界会有多大!这就意味着,在64MB内存显得捉襟见肘的情况下,双向宽搜的标记数组的容量需要经过谨慎的论证。经过 Spylft神犇 的教导,我最终选择了$4,000,005$作为数组的大小。(注:这里不能用vector,因为vector效率不高,会得到TLE)

最后贴个AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cstdlib>
#define FOR(x,f,t) for(x=f;x<=t;++x)
#define MEMSET(a,b) memset(a,b,sizeof(a))
using namespace std;
#define ll long long
#define M 4000005
const int MM=2000000;
int mk[M],mk1[M];
struct AC{int t,step;};
queue<AC> Q,R; //需要用两个队列,一个正向,一个反向
int min1(int a,int b) {
if (a==-1) return b;//a==INF
if (b==-1) return a;//b==INF
return a>b?b:a;
}
int solve(int from,int to) { //双向宽搜
MEMSET(mk,-1);
MEMSET(mk1,-1);
while(!Q.empty()) Q.pop();
while(!R.empty()) R.pop();
Q.push((AC) {from,0});
R.push((AC) {to,0});
while(!Q.empty()&&!R.empty()) {
AC n2=Q.front();Q.pop();
AC n3=R.front();R.pop();
int t=n2.t,s=n2.step;
int tt=n3.t,ss=n3.step;
mk[t]=min1(mk[t],s);
if (mk1[t]!=-1) {
return mk1[t]+mk[t];
}
mk1[tt]=min1(mk1[tt],ss);
if (mk[tt]!=-1) {
return mk1[tt]+mk[tt];
}
//下一层情况的条件
if (t*2<=MM) if(mk[t*2]==-1) Q.push((AC){t*2, s+1});
if (tt%2==0) if(mk[tt*2]==-1) R.push((AC){tt/2, ss+1});
if (t%2==0) if (mk[t/2]==-1) Q.push((AC){t/2, s+1});
if (tt*2<=MM) if (mk[tt*2]==-1) R.push((AC){tt*2, ss+1});
if (t+1<=MM) if (mk[t+1]==-1) Q.push((AC){t+1, s+1});
if (tt-1>=0) if (mk[tt-1]==-1) R.push((AC){tt-1, ss+1});
if (t-1>=0) if(mk[t-1]==-1) Q.push((AC){t-1, s+1});
if (tt+1<=MM) if(mk[tt+1]==-1) R.push((AC){tt+1, ss+1});
}
return 0;
}
int N,S,T;
void rd(int &a) { //读入外挂
char c;a=0;
while(c=getchar(),!isdigit(c));
do a=(a<<3)+(a<<1)+(c^48);
while(c=getchar(),isdigit(c));
}
void rd1() { //解决每个情况
rd(S),rd(T);
int ans=solve(S,T)*2;
cout<<ans<<endl;
}
int main(){
cin>>N;
int i;
FOR(i,1,N) rd1();
}

这题最好的写法应该是用逐层加深式的双向宽搜,在这里我的代码抛砖引玉,希望各位大神轻喷。

by lmlstarqaq