ouuan 的博客

ouuan 的博客

题解 AT2173 【Shik and Copying String】

posted on 2019-08-17 23:05:58 | under 题解 |

博客链接

题目链接

洛谷

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$ )的拐点。

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

参考代码

#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 操作的情况下答案依然是拐点个数的历史最大值了。