需要从一个字符出发，用最少的操作构造一个长度为 $n$ 的字符串。

子任务 1

一个状态可以由当前字符串长度、光标位置，以及剪贴板的内容或大小描述。把光标位置表示为它到字符串右端的偏移量会更方便。这样，无论插入内容有多长，光标位置的偏移量都只增加 $1$。

状态数为 $O(n^3)$，每个状态需要考虑 $4$ 种操作。对较小的 $n$，直接使用广度优先搜索即可。

子任务 2

通过一些观察，可以减少需要考虑的状态数。

首先，似乎完全不需要把光标向右移动。其次，可以先反复复制、粘贴单个字符，得到长度为 $O(\sqrt n)$ 的字符串；再复制整个字符串，并粘贴 $O(\sqrt n)$ 次。于是，可以用

$$L=O(\sqrt n)$$

次操作构造出长度为 $n$ 的字符串。

因此，没有必要搜索光标位置超过上界估计 $L$ 的状态：仅把光标移动到该位置所需的操作数，就已经足够构造出一个答案。类似地，剪贴板大小也不会超过 $L$。这样，状态空间可以缩小为

$$O(n\sqrt n\sqrt n)=O(n^2).$$

子任务 3

观察长度 $n$ 逐渐增大时的最优解，会发现操作序列由若干块组成；每一块都先向左移动若干次，然后复制，再执行若干次粘贴。

当 $n$ 较大时，$O(n^2)$ 的空间复杂度会成为问题，因为还需要还原具体方案。可以把状态数降至 $O(n\sqrt n)$，状态只记录字符串大小和光标位置。

两个状态之间的转移由至多 $O(\sqrt n)$ 次向左移动、一次复制，以及至多 $O(\sqrt n)$ 次粘贴组成。可以分别优化移动次数和粘贴次数，得到时间复杂度为 $O(n^2)$、空间复杂度为 $O(n\sqrt n)$ 的解法。

子任务 4～6

为了处理更大的数据，继续观察目前能够算出的答案。较小的 $n$ 对应的最优解并没有明显规律；但当 $n$ 较大时，例如 $n>1000$，答案会呈现良好的单调增长趋势。还可以观察到，向左移动已经不再重要。因此，可以用前述方法解决较小的情况，只重点考虑较大的 $n$。

令 $f(m)$ 表示用 $m$ 次操作能够构造出的最长字符串。仍把光标位置表示为到右端的偏移量；一次粘贴会使该偏移量增加 $1$。

为了构造尽可能长的字符串，显然可以忽略向右移动；向左移动也可以忽略，因为用一次粘贴代替它，效果不会更差。最优操作序列因而由 $k$ 组“复制一次，再粘贴若干次”的操作构成，即形如 YP...P。令第 $i$ 组的粘贴次数为 $n_i$，则

$$m=n_1+n_2+\cdots+n_k+k,$$

并且

$$\begin{aligned} f(n_1,\ldots,n_k) &=1+1\cdot n_1+(1+n_1)n_2+(1+n_1+n_2)n_3+\cdots\\ &=1+\frac{(m-k)^2}{2}+(m-k)-\frac{\sum_{i=1}^{k}n_i^2}{2}. \end{aligned}$$

可见，各组的顺序无关紧要；影响最终字符串长度的只有各组大小。固定组数 $k$ 后，在约束

$$n_1+n_2+\cdots+n_k=m-k$$

下，需要最小化 $\sum_{i=1}^{k}n_i^2$。理想情况下，各个 $n_i$ 应尽量相等，即接近 $(m-k)/k$。先把该值向下取整，再把余数逐一分配给若干个 $n_i$，每次增加 $1$。

译注：英文原文此处写作“最大化 $\sum n_i^2$”，但这与上式中的负号及后续“令各项尽量相等”的结论相矛盾；此处按公式订正为“最小化”。

从小到大枚举 $m$，直到找到首个满足 $f(m)\ge n$ 的值。所需操作数为 $O(\sqrt n)$。为了计算 $f(m)$，可以枚举所有

$$k\in[1,m/2].$$

总时间复杂度为 $O(n)$。还可以进一步优化到次线性复杂度，但没有必要。到这里，我们只说明了答案的大小，还没有说明如何真正构造操作序列，因此只能得到一半分数。

现在已知答案需要 $m$ 次操作。然而，按照“构造最长字符串”的策略得到的长度可能大于 $n$。目标是调整各个 $n_i$，使 $f(n_1,\ldots,n_k)$ 恰好降到 $n$。

一种可行策略如下。若 $n_i=n_j$，把其中一个减 $1$、另一个加 $1$，会使最终字符串长度恰好减少 $1$。因此，如果有许多大小相等的组，就能对答案长度进行细粒度调整。

首先，在仍能生成足够长字符串的前提下，尽量增加最长方案中的组数。这样可以得到更多组，并缩小与目标长度的差距。随后，反复把一次粘贴操作从第二大的组移动到最大的组，也就是减小前者的 $n_i$、增大后者的 $n_i$。这样会尽量增大最大组，同时让其他组继续保持大小相近。

如果继续增大最大组会使构造结果短于 $n$，之后就忽略这个最大组，转而用其余大小相近的组继续调节答案长度。组数相对较少，所以这个过程不必特别高效。

可以在一段 $n$ 的取值范围上测试该策略或其他策略，检验它们是否确实能把最长方案 $f(m)$ 调整为恰好长度 $n$。还可以形式化证明：当 $n$ 足够大时，例如 $n>10000$，上述方法一定能找到一个方案。

生成式人工智能辅助说明

本文由 OpenAI Codex 根据用户提供的 CEOI 2026 第二日官方英文题解翻译、排版并统一数学公式格式；算法思路、论证与复杂度均来自原文。两处原文中与上下文矛盾的明显公式笔误已在译文中订正，并分别附有译注。