E. 石头剪刀布机器人 详细题解

1. 机器人行为与 Monocarp 的策略 机器人的手势序列完全由 Monocarp 的手势序列决定：

第 $1$ 轮机器人出 Rock（$R$）。

对于 $i \ge 2$，机器人第 $i$ 轮出的手势是 $\text{beat}($ Monocarp 的第 $i-1$ 轮手势 $)$。

这里 $\text{beat}(x)$ 表示能击败 $x$ 的手势：$\text{beat}(R)=P$，$\text{beat}(P)=S$，$\text{beat}(S)=R$。

反过来，若我们确定了机器人的手势序列 $B[1..m]$（其中 $B[1]=R$），则 Monocarp 的手势序列 $M[1..m]$ 也随之确定：

对于 $i=1 \dots m-1$，$M[i] = \text{lose\_to}(B[i+1])$，这里 $\text{lose\_to}(y)$ 是会被 $y$ 击败的手势；

$M[m]$ 可以任意选择，我们可以让它击败 $B[m]$ 从而稳稳拿到 $1$ 分。

因此，问题转化为：寻找一个长度为 $m$ 的机器人手势序列 $B$，满足

$B[1]=R$；

$s$ 是 $B$ 的连续子串；

对应的总比分 Monocarp 净胜 $>0$（即 Monocarp 胜场 $-$ 机器人胜场 $>0$）。 求最小的 $m$。

2. 相邻手势的得分贡献 将三种手势映射为数字： $R=0$，$P=1$，$S=2$。 对于第 $i$ 轮（$1 \le i \le m-1$）， $M[i]$ 与 $B[i]$ 的胜负由 $B[i]$ 与 $B[i+1]$ 的关系决定（因为 $M[i] = \text{lose\_to}(B[i+1])$）。 具体计算可得，第 $i$ 轮的净得分（Monocarp 得分 $-$ 机器人得分）为：

$+1$：若 $B[i+1] - B[i] \equiv 2 \pmod 3$（即 $R \to S$，$P \to R$，$S \to P$）；

$-1$：若 $B[i] = B[i+1]$；

$0$：若 $B[i+1] - B[i] \equiv 1 \pmod 3$（即 $R \to P$，$P \to S$，$S \to R$）。

最后一轮 $m$，Monocarp 可自由选择获胜，固定 $+1$ 分。 设整个序列的所有相邻对得分之和为 $\Sigma$，则总净胜 $>0$ 等价于 $\Sigma \ge 0$。

3. 包含 $s$ 的最优序列 我们将 $B$ 设计为：一段前缀 $P$ + 子串 $s$ + 一段后缀 $Q$，其中前缀以 $R$ 开始并以 $s[0]$ 结束，后缀从 $s[-1]$ 出发可以走到任意状态结束。 设 $s$ 内部的相邻对得分之和为 $\text{inner}$（固定值），所需的最小额外得分 $K = -\text{inner}$（若 $\text{inner} \ge 0$ 则 $K \le 0$）。 前缀的内部得分记为 $sp$，边数（转移步数）为 $\text{len}_P = |P|-1$；后缀的步数为 $q$，我们总可以让后缀每一步都获得 $+1$（沿着 beat 方向行走），因而后缀得分 $sq = q$。 总净得分条件化为 $sp + \text{inner} + q \ge 0 \implies sp + q \ge K$。 我们需要最小化额外总长度 $L = \text{len}_P + q$，最终答案 $m = |s| + L$。

4. 前缀的最优选择 从 $R$ 走到 $x = s[0]$ 的最优路径可以只考虑无环的基础路径，因为任何绕圈都可以用长度为 $3$ 的“beat 环”替代，该环长度增加 $3$、得分增加 $3$，不改变 $(\text{len}_P - sp)$ 的值。

三种目标状态的基础路径如下（给出 $\text{len}_P$、得分 $sp$ 和 $D = \text{len}_P - sp$）：

$x = R$： 路径 $E$：$\text{len}=0$，$sp=0$，$D=0$。

$x = P$： 路径 $A$：$R \to P$，$\text{len}=1$，$sp=0$，$D=1$； 路径 $B$：$R \to S \to P$，$\text{len}=2$，$sp=2$，$D=0$。

$x = S$： 路径 $C$：$R \to S$，$\text{len}=1$，$sp=1$，$D=0$； 路径 $D$：$R \to P \to S$，$\text{len}=2$，$sp=0$，$D=2$。

对于一条基础路径，我们可以任意添加若干个长度为 $3$ 的 beat 环（每个环增加 $3$ 长度和 $3$ 得分）来调节 $sp$ 的大小。 使用后缀填补得分的代价是 $q = \max(0, K - sp)$，于是该路径的总代价为 $C = \text{len}_P + \max(0, K - sp)$。 若 $sp \le K$，可取 $q = K - sp$，此时 $C = K + D$； 若 $sp > K$，则 $q = 0$，$C = \text{len}_P$。

对所有可能的基础路径取最小 $C$，即得到最小额外长度 $L$。

5. 算法总结

计算 $s$ 的内部得分 $\text{inner}$，令 $K = -\text{inner}$。

若 $K \le 0$：不需额外得分，只需保证 $B[1]=R$。

若 $s[0] = R$，则 $m = |s|$；

否则需要至少一步前缀（$R \to s[0]$），$m = |s| + 1$。

若 $K > 0$：根据 $x = s[0]$ 枚举上述基础路径，按公式计算最小代价 $L$，答案 $m = |s| + L$。

具体而言：

$x = R$： $L = K$。

$x = P$：

若 $K \ge 2$，可选用路径 $B$ 得到 $L = K$；

否则比较路径 $A$（$L = K + 1$）和路径 $B$（$L = 2$），取 $\min(K+1, 2)$。

$x = S$：

若 $K \ge 1$，路径 $C$ 给出 $L = K$；

否则（实际上 $K > 0$ 时 $K \ge 1$）$L = K$；路径 $D$ 只会更大。

时间复杂度：每个测试用例 $O(|s|)$，总复杂度 $O(\sum |s|) \le 2 \cdot 10^5$。