AGC007F Shik and Copying String(贪心,实现)

题目链接

洛谷

AtCoder

题意简述

给你初始串 $S_0$ 和目标串 $T$,每一步操作可以将当前串 $S_i$ 变成 $S_{i+1}$,其中:

$$S_{i+1}[j]=\begin{cases}S_i[1]&j=1\\S_i[j]\text{ 或 }S_{i+1}[j-1]&j>1\end{cases}$$

求最少需要几次操作可以将当前串变为 $T$。

串长 $10^6​$。

这题题解真的难写..之前觉得别人的题解写的不清楚,然而自己也写的不是很清楚…

简要做法

首先,这个过程可以用折线表示:

(如果您在色觉方面存在障碍,还请见谅。)

可以发现,每条折线都尽量靠右是最优的,一旦画不下了,就加一行。

现在问题变成了如何高效地维护这一贪心。

当 $S_0=T$ 时,先特判掉,输出 $0​$。

由于每次拐点都会往左下移动一格,我们可以用队列来维护当前折线的每个拐点(折线往右拐的点,也就是 $S_i[j]=S_i[j-1]$ 的 $j-1$ 这个点)(不包括最后一行的拐点),其中靠近队首表示靠下(离 $T$ 较近)的拐点,靠近队尾表示靠上(靠近 $S_0$)的拐点。

详见代码(因为这题文字写出来不如代码好理解):

参考代码

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
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int n, ans;
string s, t;
queue<int> q;

int main()
{
cin >> n >> s >> t;

if (s == t) // 特判两串相等
{
puts("0");
return 0;
}

int up = n - 1, down = n - 1;

while (down >= 0)
{
while (down && t[down - 1] == t[down]) --down; // 找到当前折线在最后一行最左的位置
while (up >= 0 && (up > down || s[up] != t[down])) --up; // 找到当前折线在第一行最左的位置
if (up < 0) // 如果第一行没有对应的字符,输出无解
{
puts("-1");
return 0;
}
while (!q.empty() && q.front() - q.size() >= down) q.pop(); // 把当前折线不会碰到的部分弹出
if (up != down) q.push(up); // 如果当前折线真的是“折线”而不是竖直下来不拐弯,就把 S1 的拐点压入队列
ans = max(ans, (int)q.size() + 1); // 后文会解释为什么这样更新答案
--down;
}

cout << ans;

return 0;
}

补充说明

这个维护拐点的方式应该画画图就能明白。

最后剩下一个问题:为什么是这样更新答案?

换句话说:为什么答案是拐点个数的历史最大值?(加一是因为没有维护最后一行的拐点)

如果没有这个 pop 操作,应该是很显然的。但 pop 操作破坏了“队列中每个元素对应除最后一行外每一行最左位置”这个性质。

这里需要一个引理:

除了最后一行的拐点,其它拐点一定位于连续的前几行。

我们可以归纳地证明:

  • 对于最右的那条折线,显然成立。
  • 对于之后的每条折线,一定是先贴着上一条折线,再直接往下到最后一行。由于上一条折线满足引理,如果中途有一段没有拐点而后又出现拐点,中途的那一段就没有紧贴上一条折线。

有了这个引理,就可以感性理解说明为什么有 pop 操作的情况下答案依然是拐点个数的历史最大值了。