P10877 Solution

irris · 2022-12-18 18:42:21 · 题解

Preface

致敬传奇题目 技巧性的块速递推。

Solution

设经过 n 次操作后，生成的新字符串为 T。显然我们只关心 \forall 1 \leq i \leq n，a_i = [S_i = T_i] 的值（在知道 S 和 a 后可以唯一确定 T），而我们的操作可以看做对初始全部为 0 的 a_1\dots a_n 修改，因此断言 S 是无用的，只有 n 是有用的。

n = 2

已在样例解释中给出，答案为 1。

n = 3

考虑只有 3 种区间：[1, 2]\ [1, 3]\ [2, 3]。因为一个区间操作偶数次等于没有操作，因此可以验证操作 3 次的所有可能只等价于下述四种情况：

• 操作 [1, 2]，a = \tt 110。
• 操作 [2, 3]，a = \tt 011。
• 操作 [1, 3]，a = \tt 111。
• 操作 [1, 2]\ [1, 3]\ [2, 3]，a = \tt 010。

故答案为 4。

n \geq 4

感性理解，如果有一个目标状态 b，那么将 a 变成 b 大约要花 \frac n2 + C 的操作次数。

在操作 n 次的情况下，如果一个状态 最小 可以花费不超过 n - 2 次操作或恰好花费 n 次操作得到，那一定可以通过 n 次得到，证明是由于 2p + 3q = t 的非负整数解存在性，而我们显然分别存在可以使得：「连续操作 2 次后，a 保持不变」和「连续操作 3 次后，a 保持不变」的方案。

那么渐进意义下，答案在 n 很大时，应当直接变为 2^n。

假设我们将 b 划分为 k 个连续段，那么经过简单的计算，如果我们选择 \lfloor \frac{k - 1}{2} \rfloor 次操作，每次操作分别选择 l, r 为最左的、最右的 a_i \neq b_i 的位置，这样操作后最多剩余 1 个 a_i \neq b_i 的连续段。若连续段的长度不为 1，最多使用 1 次操作；否则，我们存在方案可以使用 2 次操作和 3 次操作，那么只要 \lfloor \frac{k - 1}{2}\rfloor + 2 \leq n 就一定有解（考虑两个数 \lfloor\frac{k - 1}{2}\rfloor + 2，\lfloor\frac{k - 1}{2}\rfloor + 3，在前者不超过 n 时，每个数都大于 n 或等于 n - 1 的不合法情况不可能出现）。

如何实行 2 次操作：

在 n \geq 4 时总是能做到。

如何实行 3 次操作：

（k = 1 的情况是简单的）这时你会发现若 k = 2 则有可能无法实行 3 次操作，这形如 \texttt{00\dots 01}，而这时的最小操作步数是 2，2p + 3q = n - 2 依旧有解。于是这不会影响答案。

由于 k \leq n - 1，则 \lfloor \frac{n}{2} \rfloor + 1 \leq n，显然在 n \geq 4 时合法，所以此时答案为 2^n。