首页 > > 程序设计 > C/C++ >

Jumping on Walls CodeForces - 198B

2018-06-17 21:45:59来源：未知阅读 ()

应该是一个隐式图的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 }

后来意识到了同样的位置，在较早的时间到过之后在较晚的时间再到那里一定不会比较早的时间更好，因此相同状态只需遍历一次，可以把复杂度优化到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 }