Jumping on Walls CodeForces

应该是一个隐式图的bfs，或者叫dp。

先是一个TLE的O(nklogn)

 1 #include<cstdio>
 2 #include<set>
 3 using namespace std;
 4 typedef pair<bool,int> P;
 5 set<P> ss[2];
 6 P t;
 7 char s[2][100100];
 8 int n,k,ii;
 9 int main()
10 {
11     int i,num,hei;
12     scanf("%d%d",&n,&k);
13     scanf("%s",s[0]+1);
14     scanf("%s",s[1]+1);
15     if(s[0][1]!='X')    ss[0].insert(P(0,1));
16     for(i=1;i<=n;i++)
17     {
18         ii^=1;
19         ss[ii].clear();
20         for(auto t:ss[ii^1])
21         {
22             num=t.first;
23             hei=t.second;
24             if(hei+k>n)
25             {
26                 puts("YES");
27                 return 0;
28             }
29             if(hei-1>i&&s[num][hei-1]!='X')
30                 ss[ii].insert(P(num,hei-1));
31             if(hei+1>i&&s[num][hei+1]!='X')
32                 ss[ii].insert(P(num,hei+1));
33             if(hei+k>i&&s[num^1][hei+k]!='X')
34                 ss[ii].insert(P(num^1,hei+k));
35         }
36     }
37     puts("NO");
38     return 0;
39 }

View Code

后来意识到了同样的位置，在较早的时间到过之后在较晚的时间再到那里一定不会比较早的时间更好，因此相同状态只需遍历一次，可以把复杂度优化到O(nlogn)（话说这不是显而易见吗，怎么就没有想到呢）

 1 #include<cstdio>
 2 #include<set>
 3 using namespace std;
 4 typedef pair<bool,int> P;
 5 set<P> ss[2];
 6 P t;
 7 char s[2][100100];
 8 int n,k,ii;
 9 bool vis[2][100100];
10 int main()
11 {
12     int i,num,hei;
13     scanf("%d%d",&n,&k);
14     scanf("%s",s[0]+1);
15     scanf("%s",s[1]+1);
16     if(s[0][1]!='X')    ss[0].insert(P(0,1));
17     for(i=1;i<=n;i++)
18     {
19         ii^=1;
20         ss[ii].clear();
21         for(auto t:ss[ii^1])
22         {
23             num=t.first;
24             hei=t.second;
25             if(hei+k>n)
26             {
27                 puts("YES");
28                 return 0;
29             }
30             if(hei-1>i&&s[num][hei-1]!='X'&&(!vis[num][hei-1]))
31                 ss[ii].insert(P(num,hei-1)),vis[num][hei-1]=1;
32             if(hei+1>i&&s[num][hei+1]!='X'&&(!vis[num][hei+1]))
33                 ss[ii].insert(P(num,hei+1)),vis[num][hei+1]=1;
34             if(hei+k>i&&s[num^1][hei+k]!='X'&&(!vis[num^1][hei+k]))
35                 ss[ii].insert(P(num^1,hei+k)),vis[num^1][hei+k]=1;
36         }
37     }
38     puts("NO");
39     return 0;
40 }

View Code

upd20190310:

啧，貌似我以前假了。直接ans[i][j]表示到达i墙j位置的最小时间，如果在这个时间水位已经没过这个点了那么这个点就是废的，不要从这个点去更新其他点

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 struct P
14 {
15     int x,y;
16 };
17 queue<P> q;
18 int n,K;
19 int ans[2][100011];
20 char s[2][100011];
21 char v1[2][100011];
22 int main()
23 {
24     P t;int x,y;
25     scanf("%d%d",&n,&K);
26     scanf("%s",s[0]+1);
27     scanf("%s",s[1]+1);
28     memset(ans,0x3f,sizeof(ans));
29     ans[0][1]=0;v1[0][1]=1;q.push((P){0,1});
30     while(!q.empty())
31     {
32         t=q.front();q.pop();
33         x=t.x;y=t.y;
34         if(y<=ans[x][y])    continue;
35         if(s[x][y]=='X')    continue;
36         if(y+1>n || y+K>n)
37         {
38             puts("YES");
39             return 0;
40         }
41         if(y>1 && !v1[x][y-1])
42         {
43             v1[x][y-1]=1;ans[x][y-1]=ans[x][y]+1;
44             q.push((P){x,y-1});
45         }
46         if(!v1[x][y+1])
47         {
48             v1[x][y+1]=1;ans[x][y+1]=ans[x][y]+1;
49             q.push((P){x,y+1});
50         }
51         if(!v1[x^1][y+K])
52         {
53             v1[x^1][y+K]=1;ans[x^1][y+K]=ans[x][y]+1;
54             q.push((P){x^1,y+K});
55         }
56     }
57     puts("NO");
58     return 0;
59 }

View Code