题解：P10087 [ROIR 2022 Day 1] 跳跃机器人

HD0X · 2024-11-23 20:39:06 · 题解

Solution

Subtask 0

暴力枚举起点和初始能力值，时间复杂度 O(n^2 \times d) ，预期得分 \text{15} 分。

应该没有人只打了这一档吧

Subtask 1

暴力枚举起点，O(n) 扫一转，能力值走到哪里不够了就加上去，时间复杂度 O(n^2)，综合上述算法，预期得分 \text{32} 分。

Subtask 2 & 4

模拟即可，时间复杂度 O(n)。综合上述算法，预期得分 \text{47} 分。

Subtask 3

未知奇妙小做法。

Subtask 6

考虑动态规划。

题解区都有，不做过多赘述。

设 f_i 表示从 i 号木桩出发的最小初始能力值。

则：

预处理前缀最大以及后缀最大的 d_j - j，可以做到 O(1) 转移。

时间复杂度 O(n) ，非常优秀。

综合上述算法，预期得分 \text{100} 分，至此，本题可通过。

其他做法

上述 dp 做法的时间复杂度正确，但需要开 \text{3} 个 10^7 的数组，而且也不是特别快。

考虑贪心。

在跳一圈的过程中，瓶颈实际在于 \max(d_i)，所以从最大处向前开始模拟，能走就走，走不动了就加到当前值加一（因为跳之前应是正好相等最优），走一圈就跳出。

正确性显然，时间复杂度 O(n)，且只需要开 \text{2} 个 10^7 的数组，甚至可以通过 5 \times 10^7的加强数据。

至此，本题又可通过，甚至截至目前次优解。

code

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e7+10,mod=1e9;
int n,f,d[MAXN],m,x,y,z,mx,id,fa[MAXN],ans,as;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while('0'<=ch && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}

void init()
{
    n=read(),f=read();
    for(int i=2;i<=n;i++) fa[i]=i-1;
    fa[1]=n;
    if(f==1)
    {
        for(int i=1;i<=n;i++) d[i]=read(),(d[i]>mx?mx=d[i],id=i:i=i); 
    }
    else
    {
        m=read(),x=read(),y=read(),z=read();
        for(int i=1;i<=n;i++)
        {
            if(i<=m) d[i]=read();
            else d[i]=(1ll*x*d[i-2]+1ll*y*d[i-1]+z)%mod+1;
            if(d[i]>mx) mx=d[i],id=i;
        }
    }
    return ;
}

void solve()
{
    int ret=id;
    ans=INT_MAX;
    while(true)
    {
        if(fa[id]==ret) break;
        if(mx-1<d[fa[id]])
        {
            if(ans>mx)
            {
                ans=mx;
                as=id;
            }
            mx=d[fa[id]]+1;
        }
        --mx;
        id=fa[id];
    }
    if(ans>mx)
    {
        ans=mx;
        as=id;
    }
    cout<<ans<<" "<<as<<endl;
    return ;
}

signed main()
{
    init();
    solve();
    return 0;
}