专栏文章

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

HHD0X
P10087题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mir0vdr0
此快照首次捕获于
2025/12/04 13:55
3 个月前
此快照最后确认于
2025/12/04 13:55
3 个月前
查看原文

Solution

Subtask 0

暴力枚举起点和初始能力值，时间复杂度 O(n2×d)O(n^2 \times d)，预期得分 15\text{15} 分。
应该没有人只打了这一档吧

Subtask 1

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

Subtask 2 & 4

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

Subtask 3

未知奇妙小做法。

Subtask 6

考虑动态规划。
题解区都有，不做过多赘述。
设 fif_i 表示从 ii 号木桩出发的最小初始能力值。
则：
\begin{aligned} d_j + i - j,j \in (i,n] \\ d_j + i - j - n,j \in [1,i)\\ \end{aligned} \right.
预处理前缀最大以及后缀最大的 dj−jd_j - j，可以做到O(1) O(1) 转移。
时间复杂度 O(n)O(n) ，非常优秀。
综合上述算法，预期得分 100\text{100} 分，至此，本题可通过。

其他做法

上述 dpdp 做法的时间复杂度正确，但需要开 3\text{3} 个 10710^7 的数组，而且也不是特别快。
考虑贪心。
在跳一圈的过程中，瓶颈实际在于 max⁡(di)\max(d_i)，所以从最大处向前开始模拟，能走就走，走不动了就加到当前值加一（因为跳之前应是正好相等最优），走一圈就跳出。
正确性显然，时间复杂度 O(n)O(n)，且只需要开 2\text{2} 个 10710^7 的数组，甚至可以通过 5×1075 \times 10^7的加强数据。
至此，本题又可通过，甚至截至目前次优解。

code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...