Codeforces 1601B. Frog Traveler

传送门

题目大意

一只蛙，在地面以下 \(n(1\leq n\leq 3\times10^5)\) 米处，要向上爬到地面，在地面以下 \(i\) 米处蛙可以向上爬 \([0,a_i](0\leq a_i\leq i)\) 米，每爬完一次，蛙会休息一次，在地面以下 \(i\) 米处休息会滑落 \(b_i(0\leq a_i\leq n - i)\) 米。求蛙爬到地面需要的最少次数，并且输出方案，即每次攀爬（休息之前）所到达的高度。

思路

考虑直接 \(bfs\) ，记 \(f_v\) 为攀爬一次并且休息滑落后到达 \(v\) 需要的最小攀爬次数，从 \(v\) 我们显然可以爬到 \(u\in[v-a[v],v]\) ，然后滑落到 \(u+b_u\) 。此时如果 \(f_{u+b_u}\) 尚为更新，则 \(f_{u+b_u}=f_v+1\) ，我们用一个 \(set\) 来维护二元组 \((u,u+b_u)\) ，其中记录所有 \(f_{u+b_u}\) 尚为更新的节点，每次从 \(v\) 转移时，遍历 \(set\) 中 \(u\in[v-a[v],v]\) 的二元组，然后更新完 \(f_{u+b_u}\) 后，将 \(set\) 中所有第二维为 \(u+b_u\) 的元素删去，表示这些元组以后不会被更新，即转移时不会被遍历到，最后 \(f_0\) 即为答案。这样每个二元组至多被访问，删除 \(1\) 次，因此复杂度为 \(O(nlogn)\) 。对于输出方案，直接在 \(bfs\) 时记录一下前驱即可，注意因为要输出休息前的高度，而 \(bfs\) 中是休息后的高度，做一些修改即可。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair
//#define int LL
//#define lc p*2
//#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 300010;

int N, A[maxn], B[maxn], f[maxn], pre[maxn], fa[maxn];
vectorU[maxn], ans;
sets;

void solve()
{
	s.insert(PII(0, 0));
	for (int i = 1; i <= N; i++)
		s.insert(PII(i, i + B[i]));
	queueque;
	que.push(N);
	f[N] = 0, pre[N] = -1;
	for (auto& a : U[N])
	{
		auto  it2 = s.find(PII(a, N));
		if (it2 == s.end())
			break;
		s.erase(*it2);
	}
	while (!que.empty())
	{
		int v = que.front();
		que.pop();
		while (true)
		{
			auto it = s.lower_bound(PII(v - A[v], 0));
			if (it == s.end() || it->first > v)
				break;
			int k = it->second;
			f[k] = f[v] + 1;
			pre[k] = it->first;
			fa[it->first] = pre[v];
			que.push(k);
			for (auto& a : U[k])
			{
				auto it2 = s.find(PII(a, k));
				if (it2 == s.end())
					break;
				s.erase(*it2);
			}
		}
	}
	cout << (f[0] == inf ? -1 : f[0]) << endl;
	if (f[0] != inf)
	{
		int now = 0;
		while (now != -1)
		{
			ans.push_back(now);
			now = fa[now];
		}
		for (int i = f[0] - 1; i >= 0; i--)
			cout << ans[i] << ' ';
		cout << endl;
	}
}

int main()
{
	IOS;
	cin >> N;
	for (int i = 0; i <= N; i++)
		f[i] = inf;
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	for (int i = 1; i <= N; i++)
		cin >> B[i], U[B[i] + i].pb(i);
	U[0].pb(0);
	solve();

	return 0;
}