题解：CF2152F Triple Attack

我知道有人会说我非人哉但我还是要写这篇题解。

由于题目保证

x

单调不降，因此题意转化为选定区间内最大子集使得子集内所有下标差为 $2$ 的元素的差大于

z

。

不难证明从第一个或最后一个数开始选，贪心地选中第一个/最后一个（与上面对应）能保持条件满足的元素是最优的。这里我们从第一个数开始选。

首先对于每个数

x_i

预处理其后第一个与其差大于

z

的元素位置，记为

t_i

。

接下来，我们定义一个状态为一个二元组

(a,b)

。每个二元组

(a,b)

有一个唯一的后继状态，若

t_a=b

，则为

(b,t_a+1)

；否则为

(b,t_a)

。实际上，一个“状态”代表的是一个合法子集的最后两个元素的位置。

由上述定义可知，将区间长度小于

3

的特殊情况判掉之后，查询

(l,r)

的答案即为最大的整数

y+2

使得状态

(l,l+1)

的

y

次后继状态中的两个元素均不大于

r

。

每次查询暴力进行上述操作显然无法通过此题，因此考虑使用 map 存储所有的 pair 进行记忆化搜索。然而提交之后会出现 TLE 的情况，因此考虑将 pair 编码为 long long，使用 unordered_map 存储所有编码并进行记忆化搜索，可以在 2.9s 内通过此题。

时间复杂度未知。

这道题在我拥有前五道题的 AC 的基础上进一步扩大了我的优势，使我不仅在本次比赛中取得了 Master 更与 International Master 的距离更近了

60

左右。

// #define Redshift_Debug
#ifdef Redshift_Debug
#define debug(...) fprintf(stderr, __VA_ARGS__)
#include <chrono>
#else
#define debug(...)
#endif
#include <array>
#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;
const int N = 2.5e5 + 10, B = 20;
int n, z, q, a[N], nxt[N];
using pii = pair<int, int>;
using sta = array<pii, B>;
using ll = long long;
ll rmp(pii x)
{
	return 1ll * (x.first - 1) * n + x.second;
}
unordered_map<ll, sta> mp;
void init_global()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
}

void init_local()
{
	mp.clear();
	cin >> n >> z;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
}
void dfs(int x, int y)
{
	if (mp.count(rmp(pii{x, y})))
		return;
	if (nxt[x] + (y == nxt[x]) > n)
	{
		for (auto &i : mp[rmp(pii{x, y})])
			i = {n + 1, n + 1};
		return;
	}
	int tnxt = nxt[x] + (y == nxt[x]);
	dfs(y, tnxt);
	mp[rmp(pii{x, y})][0] = pii{y, tnxt};
	for (int i = 1; i < B; i++)
	{
		mp[rmp(pii{x, y})][i] = mp[rmp(mp[rmp(pii{x, y})][i - 1])][i - 1];
	}
}
void run()
{
	for (int i = 1, j = 1; i <= n; i++)
	{
		while (j <= n and a[j] - a[i] <= z)
			j++;
		nxt[i] = j;
	}
	for (auto &i : mp[rmp(pii{n + 1, n + 1})])
		i = pii{n + 1, n + 1};
	cin >> q;
	for (int i = 1, l, r, res; i <= q; i++)
	{
		cin >> l >> r;
		if (r - l + 1 <= 2)
		{
			cout << r - l + 1 << '\n';
			continue;
		}
		dfs(l, l + 1);
		res = 2;
		pii buf = {l, l + 1};
		for (int i = B - 1; ~i; i--)
		{
			if (mp[rmp(buf)][i].second > r)
				continue;
			res += (1 << i);
			buf = mp[rmp(buf)][i];
		}
		cout << res << '\n';
	}
}
int main()
{
#ifdef Redshift_Debug
	auto st = chrono::high_resolution_clock::now();
#endif
	int T = 1;
	init_global();
	cin >> T;
	while (T--)
	{
		init_local();
		run();
	}
#ifdef Redshift_Debug
	auto ed = chrono::high_resolution_clock::now();
	fprintf(stderr, "%.9lf\n", (ed - st).count() / 1e9);
#endif
}

题解：CF2152F Triple Attack

文章操作

相关推荐

评论

题解：CF2152F Triple Attack