JOISC2022 Day2 题解

First Post:

Last Update:

事实上没有通信题题解。

这两题都没想出完整做法，不知道是不是睡眠质量的问题。按道理来说都应是 “刚好会做” 的题。

按体感难度排序。

loj3690 团队竞技

题意： https://loj.ac/p/3690

老老实实地想了除最后一个包的所有点。

无语住了。

按 从小到大排序，扫描 最大的那个人，剩下两人都要在他前面。设剩下两人为 ，那么有 。

我们加入一个 的时候，其实就可以找到与其配对的另一个人 (满足 的 中 最大的，以及满足 的 中 最大的)。

将 与和其配对的点合成一对 ，扔到一个二维数据结构里面。扫描到 时，查询 的 最大值即可。

时间复杂度 。

loj3688 复制粘贴 3

题意 : https://loj.ac/p/3688

想到了区间 DP，但脑子不在状态，只是描绘了一个复制粘贴的形态，没有在纸上细推，导致转移没有编出来。

至于如何想到，其实可以考虑观察样例 的构造过程。其没有明显的顺序或倒序构造的特征，不过仍然是从小串构造出包含它的大串，即 ，这反映到区间上就是 。一条区间 DP 的转移路径。

那么我们可设 表示不管当前的剪贴板是什么，构造出 的最小步数。

考虑我们剪切了一个串后，用其构造出来的串一定形如 （其中 都是我们手打的字符）。

其中头尾两段不是很好处理，我们考虑编两个转移来包含这两段。

显然有 (其中 表示 )。

考虑 怎么办 ，我们设 表示构造出 ，且最后一次操作是粘贴的最小步数。

当我们从 向外转移时，可以先令 ，然后 。

依据 的定义，我们可以转移 。

至此， 和 都处理完了。

那么我们多次粘贴 时，可以默认我们构造出来的串开头是 ，结尾也是 。

那么我们设 表示 最早的出现位置使得该位置不在 中。

那么我们每次转移暴力跳 即可转移。

因为我们至多跳 次，复杂度是 的 ( 是调和级数)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline void ckmin(T &x,const T &y) { if(x > y) x = y;}
const int N = 2.5e3 + 5;
typedef unsigned long long ull;
const ull base = 13331;
int n;
int A,B,C;
char s[N];
int nxt[N][N];
long long f[N][N],g[N][N];
ull hsh[N],Pow[N];
ull h[N][N];
map<ull,int> ton;
int main()
{
	cin >> n;
	cin >> (s + 1);
	cin >> A >> B >> C;
	Pow[0] = 1;
	for(int i = 1;i <= n;i++) Pow[i] = Pow[i - 1] * base;
	for(int i = 1;i <= n;i++) hsh[i] = hsh[i - 1] * base + (s[i] - 'a' + 1);
	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j++)
			h[i][j] = hsh[j] - hsh[i - 1] * Pow[j - i + 1];
	for(int l = 1;l <= n;l++)
	{
		ton.clear();
		for(int i = n - l + 1;i + l - 1 > n - l;i--)
		nxt[i][i + l - 1] = n + 1;
		for(int i = n - l - l + 1;i >= 1;i--)
		{
			ton[h[i + l][i + l + l - 1]] = i + l;
			if(ton.find(h[i][i + l - 1]) == ton.end())
				nxt[i][i + l - 1] = n + 1;
			else nxt[i][i + l - 1] = ton[h[i][i + l - 1]];
		}
	}
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	for(int i = 1;i <= n;i++)
		f[i][i] = A;
	for(int len = 1;len <= n;len++)
	{
		for(int i = 1;i + len - 1 <= n;i++)
		{
			int j = i + len - 1;
			ckmin(f[i][j],g[i][j]);
			if(j < n) ckmin(f[i][j + 1],f[i][j] + A);
			int now = nxt[i][j],cnt = 2;
			while(now <= n)
				ckmin(f[i][now + len - 1],f[i][j] + B + 1ll * cnt * C + 1ll * A * (now + len - i - cnt * len)),
				++cnt,now = nxt[now][now + len - 1];
		}
		for(int i = 2;i + len - 1 <= n;i++)
			ckmin(f[i - 1][i + len - 1],f[i][i + len - 1] + A);
	}
		
	cout << f[1][n] << endl;
	return 0;
}
≡