Znzryb's Blog
0%

Codeforces Round 987 (Div. 2) — D. Penchick and Desert Rabbit

Posted on Edited on

AC代码

不难发现，只要知道该点能够跳到的最远点，就能够顺利求出答案。

1
2
3
4
5
// upA[i]表示i位置之前（包括i位置）出现的最大的height。
// upj[i]表示i位置能跳到的最远位置
for(int i=1;i<=n;++i)
      cout<<upA[upj[i]]<<" ";
cout<<endl;

那问题就变成了怎么求 i 位置能跳到的最远位置

我们使用记忆化搜索

1
2
3
for(ll i=1;i<=n;++i) {
      upj[i]=max(upI[upA[i]-1],i);
}

upj[i]的初始化是指我们先给upj[i]赋上一个跳一次或者两次（一定往前跳）的值

1
2
3
4
5
6
7
ll dfs(ll x) {
    if(vis[x])
        return upj[x];
    vis[x]=true;
    upj[x]=dfs(upj[x]);
    return upj[x];
}

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e5)+10;
ll n,T,A[N],upI[N],upA[N],upj[N];   // upj is max idx you can jump to in this pos
bool vis[N];

ll dfs(ll x) {
    if(vis[x])
        return upj[x];
    vis[x]=true;
    upj[x]=dfs(upj[x]);
    return upj[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        for(int i=1;i<=n;++i)   // initialize
            upI[i]=0,vis[i]=false;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
        }
        for(int i=1;i<=n;++i) {
            // upI[x] means the max index of x, in other words, farthest x's idx
            upI[A[i]]=i;
        }
        ll maxUpi=0;
        for(int i=1;i<=n;++i) {
            // 大的点肯定能跳到小的点最远的位置
            maxUpi=max(upI[i],maxUpi);
            upI[i]=maxUpi;
        }
        ll maxA=0;
        for(int i=1;i<=n;++i) {
            // upA[i]表示i位置之前（包括i位置）出现的最大的height。
            maxA=max(maxA,A[i]);
            upA[i]=maxA;
        }
        for(ll i=1;i<=n;++i) {
            upj[i]=max(upI[upA[i]-1],i);
        }
        for(int i=1;i<=n;++i) {
            if(vis[i])
                continue;
            upj[i]=dfs(i);
        }
        for(int i=1;i<=n;++i)
            cout<<upA[upj[i]]<<" ";
        cout<<endl;
    }
    return 0;
}
// AC https://codeforces.com/contest/2031/submission/291771622

心路历程（WA，TLE，MLE……）