T30382: 复制粘贴

greedy + dp/bfs, http://cs101.openjudge.cn/practice/30382/

Alice 有两个字符串 S 和 T，她的希望通过对字符串 T 进行一系列操作，使得字符串 S 为字符串T的一个子序列。这里的“子序列”是指通过从一个字符串中删除一些字符（可以是零个或多个，也可以不删），但不改变剩余字符的顺序，得到的新字符串。

Alice 可以进行的操作有两种：复制和粘贴。其中复制操作会将目前整个T串覆写到剪切板，粘贴操作会将剪切板的内容新增在T串的末尾。注意，一开始剪切板为空，并且粘贴操作不会清空剪切板。

现在，你需要回答，Alice 至少需要操作多少次才能达到目的？如果无论怎样操作，Alice 都无法达到目的，请你输出 “-1”（不包含引号）。

输入

第一行输入一个只包含小写字母的字符串 S(1≤|S|≤10^5)；第二行输入一个只包含小写字母的字符串 T(1≤|T|≤10^5)。

输出

输出一个整数，表示 Alice 需要操作的次数。

样例输入

abbbbbbbbb
cbaca

样例输出

提示

greedy + dp

来源

2025fall

这个问题可以分为两个主要步骤来解决：

计算最少需要的 $T$ 的副本数量 $k$ ：我们需要找到最小的正整数 $k$ ，使得字符串 $S$ 是 $k$ 个 $T$ 拼接而成的字符串 $T^{k}$ 的一个子序列。我们可以使用贪心算法：遍历字符串 $S$ 的每一个字符，尝试在当前的 $T$ 副本中找到它。如果当前副本中剩余的部分没有这个字符，我们就开启一个新的 $T$ 副本（即 $k$ 增加 1），并从新副本的开头开始匹配。为了高效地执行此操作，我们可以预处理字符串 $T$ ，记录每个位置之后每个字母下一次出现的位置（序列自动机思想）。
计算达到至少 $k$ 个副本的最少操作次数：这实际上是一个经典的动态规划问题：从 1 个副本开始，通过“复制全部”和“粘贴”操作，最少需要多少次操作可以得到至少 $k$ 个副本。
- 复制操作：将当前副本总数存入剪切板（消耗 1 次操作）。
- 粘贴操作：将剪切板中的副本数加到总数中（每次消耗 1 次操作）。假设当前有 $i$ 个副本，如果我们执行 1 次复制和 $j - 1$ 次粘贴，我们将得到 $i \times j$ 个副本，总共消耗了 $j$ 次操作。因此，状态转移方程为： $d p [i \times j] = min (d p [i \times j], d p [i] + j)$ 。由于我们需要的是“至少” $k$ 个，而有时候达到一个比 $k$ 大但因数分解更优的数（例如 $2^{n}$ ）可能比达到一个较大的质数 $k$ 更快，所以我们需要在 $[k, limit]$ 范围内取 $d p$ 的最小值。

Python 3 实现。

输入输出：使用 sys.stdin.read().split() 批量读取以提高效率。
字符串匹配：使用 bisect_left（二分查找）。
DP 计算：Python 的循环效率较低，但 $O (N \log N)$ 的算法（类似于埃氏筛法）在 $2 \times 10^{5}$ 的量级下配合简洁的循环体是可以跑通的。

python

import sys
from bisect import bisect_left

def solve():
    # 使用 sys.stdin.read 一次性读取，防止多次 I/O 带来的开销
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    s = input_data[0]
    t = input_data[1]
    
    n = len(s)
    m = len(t)
    
    # 1. 预处理 T 中每个字符出现的所有索引位置
    char_indices = [[] for _ in range(26)]
    ord_a = ord('a')
    for i, char in enumerate(t):
        char_indices[ord(char) - ord_a].append(i)
        
    # 2. 贪心计算最少需要的副本数 k
    k = 1
    curr_pos = 0 # 当前在 T 副本中的匹配位置
    
    for char in s:
        indices = char_indices[ord(char) - ord_a]
        if not indices:
            # S 中存在 T 中没有的字符，无法匹配
            print("-1")
            return
            
        # 使用二分查找寻找当前副本中第一个大于等于 curr_pos 的字符索引
        it = bisect_left(indices, curr_pos)
        
        if it < len(indices):
            # 在当前副本的剩余部分找到了
            curr_pos = indices[it] + 1
        else:
            # 当前副本匹配完了，需要开启一个新副本
            k += 1
            curr_pos = indices[0] + 1
            
    # 如果 1 个副本就够了，不需要任何操作
    if k == 1:
        print(0)
        return
        
    # 3. DP 计算最少操作次数
    # 这是一个经典的“复制与粘贴”问题，目标是得到至少 k 个副本。
    # 达到 x 个副本的最少次数等于其所有质因数之和。
    # 由于可以超过 k，我们需要在一个范围内寻找最小值。
    
    # 设置上限。考虑到 2^17 > 10^5，在这个范围内一定能找到最优解。
    limit = max(k + 500, 131072) 
    if limit > 200005: 
        limit = 200005
        
    # dp[i] 表示得到恰好 i 个副本的最少操作次数
    # 初始值设为 i，表示 1 次复制后进行 i-1 次粘贴
    dp = list(range(limit + 1))
    dp[0] = 0
    dp[1] = 0
    
    # 状态转移：从 i 个副本出发，复制一次，粘贴 (j-1) 次，得到 i*j 个副本
    # 总代价 = dp[i] + j
    for i in range(2, limit // 2 + 1):
        base_cost = dp[i]
        # v = i * j, 则 j = v // i
        # 这个循环类似于素数筛法，复杂度为 O(N log N)
        for v in range(i * 2, limit + 1, i):
            cost = base_cost + (v // i)
            if cost < dp[v]:
                dp[v] = cost
                
    # 在所有大于等于 k 的副本数中找最小值
    print(min(dp[k:]))

if __name__ == "__main__":
    solve()

关键点解析：

贪心策略：我们总是尽可能在当前的 $T$ 副本中多匹配字符。只有当当前副本中不再有目标字符时，才“消耗”一个新的副本。这保证了得到的 $k$ 是最小的。
DP 逻辑：
- 执行一次“复制”操作后，剪切板里有 $i$ 个副本。
- 随后执行 $j - 1$ 次“粘贴”，每次增加 $i$ 个。
- 总共得到 $i + (j - 1) \times i = i \times j$ 个副本。
- 操作次数增加 $1 (复制) + (j - 1) (粘贴) = j$ 次。
- 因此转移方程为 dp[i * j] = dp[i] + j。
为什么 min(dp[k:])？：有时候达到一个比 $k$ 稍大的数字（比如 $k = 13$ 时，达到 $16 = 2^{4}$ 只需要 8 步，而达到 13 需要 13 步）反而更划算。
性能：在 Python 中，range 步长循环（如 range(i*2, limit+1, i)）是由底层 C 实现的，速度非常快，足以在 1 秒内处理 $10^{5}$ 量级的数据。

这段代码的逻辑：
python
# 确定搜索范围：至少要到 k，但为了找更优解，往后多看一点
limit = max(k + 500, 131072) 
# 如果算出来的上限太大，把它压回到 200005，防止浪费时间
if limit > 200005:
    limit = 200005

# ... 后面进行 DP ...

# 最后结果取 [k, limit] 范围内的最小值
print(min(dp[k:]))
这一段的存在，是为了让程序不只是“死脑筋”地去找恰好 $k$ 个副本的方法，而是能聪明地发现：“哎呀，我多做一个副本，步数反而更短呢！”
这一段代码的核心逻辑是为了处理“达到 $k$ 个副本的最少操作次数”这一步。
简单来说：如果目标 $k$ 是一个很大的质数，直接达到 $k$ 会非常贵；但如果稍微多做几个副本（达到一个比 $k$ 大一点点的合数），操作次数反而可能更少。
我们可以从以下几个维度来拆解这段逻辑：
1. 为什么可以超过 $k$ ？
题目要求“使得字符串 S 为字符串 T 的一个子序列”。如果你通过操作得到了 $k$ 个 $T$ 拼接成的字符串，满足了条件，那么如果你通过更少的操作得到了 $m$ 个 $T$ （只要 $m > k$ ）， $S$ 显然也一定是这 $m$ 个 $T$ 的子序列。因此，我们的目标是：求达到任意 $m \geq k$ 的副本数所需的最少操作次数。
2. 操作次数的规律（合数 vs 质数）
在“复制+粘贴”模型中，得到 $x$ 个副本的代价，本质上是把 $x$ 进行因数分解，代价等于所有质因子的和。
例子 A： 假设 $k = 13$ （质数）。
为了刚好得到 13 个，你只能：1次复制，12次粘贴。总次数 = 13。
例子 B： 观察比 13 大一点的数，比如 $14 = 2 \times 7$ 或 $15 = 3 \times 5$ 或 $16 = 2 \times 2 \times 2 \times 2$ 。
得到 14：(1复1粘)得到2，(1复6粘)得到14。总次数 = $2 + 7 = 9$ 。
得到 15：(1复2粘)得到3，(1复4粘)得到15。总次数 = $3 + 5 = 8$ 。
得到 16：(1复1粘)得到2，(1复1粘)得到4... 总次数 = $2 + 2 + 2 + 2 = 8$ 。
结论： 即使我们需要 13 个，但多做 2 个达到 15 个，反而能省下 5 次操作。
3. 为什么设置这些具体的数字？
131072 ( $2^{17}$ ): 因为 $| S | \leq 10^{5}$ ，所以 $k$ 最大也就是 $10^{5}$ 左右。 $2^{17} = 131072$ 是第一个大于 $10^{5}$ 的 2 的幂。通过不断的“复制+粘贴一次（翻倍）”，达到 $2^{17}$ 的总步数只需要 $2 \times 17 = 34$ 步。这是一个非常小的代价。所以，无论 $k$ 是多少，最优解的步数绝对不会超过 34 步（除非 $k$ 本身很小）。为了保证 DP 能搜到这些“便宜”的 $2^{n}$ 的数，我们将上限至少设到这个规模。
k + 500: 这是一个经验性的增量。通常在 $k$ 附近的几百个数内，一定能找到一个由小质数（2, 3, 5）组成的合数，它的代价会远低于 $k$ 本身。
limit = 200005: 这是一个安全上限。防止 $k$ 加上增量后超过了我们预设的数组范围（ $2 \times 10^{5}$ 是此类题目常见的数组大小）。即使 $k$ 达到上限 $10^{5}$ ，我们也只搜到 $2 \times 10^{5}$ 为止，这在时间复杂度（ $O (N \log N)$ ）上是可以接受的。

第二部分bfs实现

python

def count_copies():
    import bisect
    s = input()
    t = input()
    char_indices = [[] for _ in range(26)]
    for ind, i in enumerate(t):
        char_indices[ord(i) - ord('a')].append(ind)
    cou, last = 1, -1
    for i in s:
        ind = ord(i) - ord('a')
        if not char_indices[ind]:
            return -1
        if last >= char_indices[ind][-1]:
            last = -1
            cou += 1

        pla = bisect.bisect_right(char_indices[ind], last)
        last = char_indices[ind][pla]
    return cou


def bfs(i):
    if i == 1:
        return 0
    from collections import deque
    visited = set()
    queue = deque([(0, 1, 0)])  # steps, now, clip
    visited.add((1, 0))

    while queue:

        steps, now, clip = queue.popleft()
        if now + clip >= i:
            return steps + 1

        if clip:  # 操作1: 粘贴
            queue.append((steps + 1, now + clip, clip)) # 使当前数增加clipboard
            visited.add((now + clip, clip))

        if now > clip:  # 操作2: 复制
            queue.append((steps + 1, now, now))  # 使clipboard=当前数
            visited.add((now, now))


if __name__ == '__main__':
    needed = count_copies()
    print(-1 if needed == -1 else bfs(needed))

T30382: 复制粘贴 ​

T30382: 复制粘贴