codeforces-#659-B

codeforces-#659-B

七月 25, 2020

B2. Koa and the Beach (Hard Version)

B1. Koa and the Beach (Easy Version)

题意

一个人从岸边位置0 游到 岛上位置n+1

中间n个水域的深度为d[i]

同时由于潮汐海水深度一直在周期的变化d[i]+p[tmod2k]

其中p=[0,1,2,…,k−2,k−1,k,k−1,k−2,…,2,1]

而这个人不能通过深度为L的水域 问最后这个人能否到达对岸

题解

easy version

可以将{位置,潮汐增加高度,是否处于涨潮期}这个状态视为一个结点

而当前结点是否能转移到其他结点x的条件是d[x]+潮汐增加高度<=l

于是将所有状态点构成一个图 进行dfs搜素是否能够到达n+1位置 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=100+5;
int deep[Max];
int n,k,l;bool ok;
set<pair<int,pair<int,bool> > >vis;
///官方用tuple<int,int,bool>可能编译器问题一直报错
void dfs(int pos,int tide,bool down){
    //vis[pos]++;
    //if(vis[pos]>=17*k)return;
    ///不用三元组标记每个状态是否访问
    ///尝试用vis[pos]被访问到一定次数则表明不能通到下一个点
    ///但是这种方式可能由于到达当前位置的状态太多
    ///无法准确给出一个限定最多访问的次数上界
    if(pos>n){
        ok=1;
        return;
    }
    if(vis.count({pos,{tide,down}}))return;
    else vis.insert({pos,{tide,down}});
    tide+=(down?-1:1);
    if(tide==k||tide==0)down=!down;
    //cout<<pos<<" "<<tide<<" "<<down<<endl;
    if(deep[pos+1]+tide<=l)dfs(pos+1,tide,down);
    if(deep[pos]+tide<=l)dfs(pos,tide,down);
    //if(deep[pos-1]+tide<=l)dfs(pos-1,tide,down);
    if(deep[pos]+tide<l&&deep[pos+1]+tide>l)return;
}
int main() {
    //Turnoff;
    int t;cin>>t;
    while(t--){
        ok=0;cin>>n>>k>>l;
        deep[0]=-k,deep[n+1]=-k;
        vis.clear();
        for(int i=1;i<=n;i++)cin>>deep[i];
        dfs(0,0,0);
        if(!ok)cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

hard version

先找到所有安全的水域 safepos即无论何时 他都不会溺水deep[i]+k<=l

然后问题被分解成能否顺利从一个safepos到达下一个safepos

v形曲线表示落潮-涨潮

策略是当他处于某个安全水域时

在落潮到下个点的深度在下一秒刚好不溺水时假设为 t0 游到下一个点

然后反复使用这个策略到达下一个安全点最后t1时刻到达下一个安全点

或者说落潮时当下一个点恰好能安全通过时最快的通过它的策略能避免溺水

假设不是处于t0时游到下一个点 而时t0’

那么最早到达下一个安全点时为t1’

那么会比“在落潮到下个点的深度在下一秒刚好不溺水时”出发 在t1~t1’所在的水域会多出一些深度

当最优的策略也无法通过时就输出”NO”

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
ll deep[Max];
/*
20 26 32
31 27 14 7 2 23 22 21 19 27 31 12 23 31 0 11 28 20 31 30
 
*/
int main() {
    //Turnoff;
    int t;cin>>t;
    while(t--){
        ll n,k,l;
        cin>>n>>k>>l;
        vector<int>safe;
        for(int i=1;i<=n;i++){
            cin>>deep[i];
            if(deep[i]+k<=l)safe.push_back(i);
        }
        safe.push_back(n+1);deep[n+1]=-k;
        int now=0;bool flag=0;
        for(auto i:safe){
            ll tide=min(k,l-deep[now+1]);///下一秒到下一个点时涨潮的高度
            if(tide<0)flag=1;bool down=1;///若涨潮高度为负表示无论如何不能过,down表示是否在落潮
            //cout<<now<<" "<<tide<<endl;
            while(now<i){
                if(tide+deep[now+1]<=l)now++;///如果下一秒能过就过
                else {
                	///当下一秒不能直接到达下一个点则选择等待合适的时机
                    ll ntide=min(k,l-deep[now+1]);///等到 到达下一个点恰好到不被淹死的高度
                    if(ntide<0)flag=1;
                    if(!down&&deep[now]+k>l)flag=1; 
                    //如果已经处于涨潮阶段而且当前的水域到高潮时会被淹死则不能过
                    else if(!down&&deep[now]+k<=l)down=!down;
                    //否则可以通过得等到下次落潮
                    tide=ntide;now++;
                    ///这里直接当成我已经到达下一个点了
                    ///于是直接讨论下下个点
                }
                if(tide==0||tide==k)down=!down;///判断下一秒时是涨潮还是落潮
                if(down)tide--;
                else tide++;
                if(flag)break;
            }
            if(flag)break;
        }
        if(flag)cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}