本文涉及知识点

C++前后缀分解

[ROIR 2022 Day 1] 跳跃机器人

题目背景

翻译自 ROIR 2022 D1T2。

某公司正在开发一种跳跃机器人。为了测试机器人，他们在一个多边形平台上设置了一个由 $n$ 个特殊平台组成的环形路线，平台从 $1$ 到 $n$ 编号。第 $i$ 个平台与 $i+1$ 个平台之间的距离为 $d_i$，最后一个平台与第一个平台之间的距离为 $d_n$（假设长度分别为 $d_1,d_2,\dots ,d_n$ 的边可以组成一个 $n$ 边形）。

机器人配备了人工智能，在测试过程中学习跳得更远。在任何时刻，机器人通过一个整数 $a$ 来表示它的灵敏度。如果 $a$ 大于等于 $d_i$，机器人可以从平台 $i$ 跳到平台 $i+1$；同样地，如果 $a$ 大于等于 $d_n$，机器人可以从最后一个平台跳到第一个平台。每次跳跃后，机器人的灵敏度增加 $1$。

题目描述

机器人的开发人员选择一个平台作为起始平台。如果机器人可以完成 $n$ 次跳跃，回到原来的平台，他们认为实验是成功的。开发人员需要确定机器人的最小起始灵敏度是多少，并选择哪个平台作为起始平台。

输入格式

第一行包含一个整数 $n$。

第二行包含一个整数 $f$。

• 如果 $f=1$，则第三行包含 $n$ 个整数 $d_1,d_2,\dots ,d_n$，意义见题目背景。
• 如果 $f=2$，则第三行包含一个整数 $m$，以及三个整数 $x,y,z$。第四行包含 $m$ 个整数 $c_1,c_2,\dots ,c_m$。此时距离值 $d_i$ 根据以下公式计算：
  • 如果 $1\le i\le m$，则 $d_i=c_i$。
  • 如果 $m+1\le i\le n$，则 $d_i=((x\times d_{i-2}+y\times d_{i-1}+z)\mathrm{mod}10^9)+1$。

输出格式

输出两个整数，即最小允许的起始灵敏度 $a$ 和可用于放置机器人的起始平台编号。如果有多个最小起始灵敏度对应的起始平台，可以输出任意一个。

样例 #1

样例输入 #1

5
1
3 7 4 2 5

样例输出 #1

4 3

样例 #2

样例输入 #2

10
2
5 1 2 3
1 2 3 4 5

样例输出 #2

653 1

提示

样例说明：

在第二个示例中，距离数组为 $[1,2,3,4,5,18,45,112,273,662]$。

根据公式计算 $d_6$ 到 $d_{10}$ 的值：

• $d_6=((1\cdot d_4+2\cdot d_5+3)\mathrm{mod}10^9)+1=((1\cdot 4+2\cdot 5+3)\mathrm{mod}10^9)+1=18$；
• $d_7=((1\cdot d_5+2\cdot d_6+3)\mathrm{mod}10^9)+1=((1\cdot 5+2\cdot 18+3)\mathrm{mod}10^9)+1=45$；
• $d_8=((1\cdot d_6+2\cdot d_7+3)\mathrm{mod}10^9)+1=((1\cdot 18+2\cdot 45+3)\mathrm{mod}10^9)+1=112$；
• $d_9=((1\cdot d_7+2\cdot d_8+3)\mathrm{mod}10^9)+1=((1\cdot 45+2\cdot 112+3)\mathrm{mod}10^9)+1=273$；
• $d_{10}=((1\cdot d_8+2\cdot d_9+3)\mathrm{mod}10^9)+1=((1\cdot 112+2\cdot 273+3)\mathrm{mod}10^9)+1=662$。

本题使用捆绑测试。

子任务	分值	特殊性质
$0$	$15$	$n\le 300,f=1,d\le 300$
$1$	$17$	$n\le 5000,f=2$
$2$	$10$	$n\le 100000,f=1$ 且保证从第一个平台开始跳是最佳选择
$3$	$20$	$n\le 100000,f=1$
$4$	$5$	$f=2$ 且保证从第一个平台开始跳是最佳选择
$5$	$33$	$f=2$

对于 $100\%$ 的数据，$3\le n\le 10^7$。当 $f=1$ 时 $1\le d_i\le 10^9$，当 $f=2$ 时 $2\le m\le \min (n,10^5)$，$0\le x,y,z\le 10^9$，$1\le c_i\le 10^9$。

注：本题的算法标签部分参考了官方题解中用到的解法。

多键有序映射

多键有序映射s记录 c[i]-i
从平台0开始，需要初始敏捷为s的最大值。
从平台1开始，从s中删除c[0]-0，将c[0]-(n-1)+1 放到s中。 s的最大值-1就是需要的初始敏捷值。
从平台i开始，从s中删除c[i-1]-i-1，将c[i-1]-(n-1)+i放到s中。s的最大值-i就是需要的初始敏捷值。
可以在处理结束时：删除i，而不是处理之前，删除i-1。
本题的n，最大1e7，内存256M，用有序集合，内存很可能超。
前4个子任务，可以通过。第五个子任务，可以特殊处理。第六子任务无法过。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;

template<class T = int>
vector<T> Read() {
	int n;
	scanf("%d", &n);
	vector<T> ret(n);
	for(int i=0;i < n ;i++) {
		cin >> ret[i];
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {
	cin >> pr.first >> pr.second;
}

class Solution {
public:
	pair<int, int> Ans(vector<int>& d) {
		const int N = d.size();
		multiset<int> s;
		for (int i = 0; i < d.size(); i++) {
			s.emplace(d[i] - i);
		}
		pair<int, int> ans(*s.rbegin(), 1);
		for (int i = 1; i < d.size(); i++) {
			s.erase(s.find(d[i - 1] - (i - 1)));
			s.emplace(d[i - 1] - (N - 1) - i);
			if (*s.rbegin() + i < ans.first) {
				ans = make_pair(*s.rbegin() + i, i + 1);
			}
		}
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	int n, f;
	cin >> n >> f;
	vector<int> d;
	if (1 == f) {
		d = Read<int>(n);
	}
	else {
		int m;
		long long x, y, z;
		cin >> m >> x >> y >> z;
		d = Read<int>(m);
		d.resize(n);
		for (; m < n; m++) {
			d[m] = (d[m - 2] * x + d[m - 1] * y + z) % ((int)1e9) + 1;
		}
	}
#ifdef _DEBUG	
	/*printf("N=%d,K=%d,T=%d,", N, K,T);*/
	Out(d, "d=");
#endif	
	auto res = Solution().Ans(d);
	cout << res.first << " " << res.second << std::endl;
	return 0;
}

单元测试

	vector<int> d;
		TEST_METHOD(TestMethod11)
		{
			d = { 3,7,4,2,5 };
			auto res = Solution().Ans(d);
			AssertEx({ 4,3 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			d = { 1,2,3,4,5,18,45,112,273,662 };
			auto res = Solution().Ans(d);
			AssertEx({ 653,1 }, res);
		}

前后缀分解

若干从x开始跳，x$\in$[0,n-1]，那需要的灵敏值以下两者的较大值是：
$$\{\begin{array}{llc}max(d[j]-x)& & j>=x\\ max(d[j]-(n-x)-j)& & j<x\end{array}$$
数组r记录前者,数组left记录后者，后者可以省略。

代码

class Solution {
		public:
			pair<int,int> Ans(vector<int>& d) {
				const int N = d.size();
				vector<int> r(N);
				int iMax = INT_MIN / 2;
				for (int i = N - 1; i >= 0; i--) {
					r[i] = iMax = max(d[i], iMax - 1);
				}		
				iMax = INT_MIN / 2;
				pair<int, int> ans(INT_MAX/2,1);
				for (int i = 0; i < N;i++) {
					if (max(r[i], iMax) < ans.first) {
						ans = make_pair(max(r[i], iMax), i + 1);
					}
					iMax = max(d[i]-(N-1), iMax + 1);
				}
				return ans;
			}
		};

扩展阅读

计算几何为骨，排样优化为魂
作品：亲士CAD工具箱
经典文章推荐：二维排样
万物皆数学
查阅鄙人的博文，请点击博文下载学院导航
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。