题解：P17857 「GLR-R5」立秋 / autumnascit

· · 题解

验题人题解。本题解以 L,R,l,r,M 代表对应字符的出现次数。

Step 1

一个 L 能产生贡献当且仅当：

R 是对称的。贪心地考虑，由于 R 和 M 可以在 L 的前面或者后面出现，L 和 M 可以在 R 的前面或者后面出现，为了最大化利用它们，我们希望尽可能多地出现 LRL, RLR, XMX（X 是大写字母）的结构。

由于 R 前面可以没有字符，容易想到以 RLRL... 的结构开头，直到 L 或 R 用完为止。下面我们假设 L 用完了，R 用完了的情况可以对称处理。

为了最大化 M 的利用率，剩下的 R 我们采用 RMRM... 的结构，直到 R 和 M 的其中一个用完。我们在 Step 2 - 1 讨论 M 用完的情况，Step 2 - 2 讨论 R 用完的情况。

Step 2 - 1

当 M 用完时，我们希望剩下的 R 能够继续产生贡献，此时新的 R 右边只能放 r，而 r 的右边不能直接接 R，只能接 l。

于是得到 RrlRrl...Rr 的结构。注意可以以 Rr 结尾，那么 Rrl 的重复次数是 \min\{R-1,r-1,l\}。

接下来 R, l, r 三者中有至少一个会用完，如果还有剩下的 R 就一定不能产生贡献，所以我们据情况重复 Rr, Rl, lr 的结构即可。

在完成上述步骤后只会剩下一种字符。如果剩下的是 R，可以随意插入到合法的位置；否则如果剩下 l 或 r，由于随意插入可能会减少贡献，我们在 Step 3 讨论。

Step 2 - 2

当 R 用完时，考虑到可能 M 很大的情况，我们先尽可能把 M 插入到前面 RLRL...RMRM... 的结构中。但我们不希望出现 RML 的结构，因为 R 和 L 指向了同一个 M，导致贡献减少。

考虑先不管 R 和 L 之间的空隙，我们会得到 MRLMRL...MRMRM... 的结构。假如此时 M 还有剩余，一个简单的调整是选择长为 3x 的前缀，将其替换成 x 个 ML 和 x 个 MR，这样可以多塞入 x 个 M。x 的具体取值是剩下的 M 数量与 RL 数量的 \min。

:::info[x=3 的例子] MRLMRLMRL \to MLMLMLMRMRMR。 :::

现在我们处理 l 和 r。一个自然的结构是 rlrl...，可以直接拼在后面，这样 l 和 r 只会剩下其中一种。假如还有 M，我们可以重复 Ml 或 Mr 做到只剩一种字符。

与 Step 2 - 1 类似，如果剩下的是 M，可以随意插入到合法的位置；否则如果剩下 l 或 r，由于随意插入可能会减少贡献，我们在 Step 3 讨论。

Step 3

假设剩下最后一种字符 r，l 的情况是对称的。

在合法的前提下，我们先填充所有 l 和 M 前面的位置（以及最后一个位置），之后的填充一定会减少贡献，直接乱填即可。

Step 4

下面分析一下答案。由于我们的构造充分利用了 Step 1 开头所提的 RLR, LRL, XMX 等结构，容易分析出一个上界是 \min\{L,R+r+M+1,R+l+M\}+\min\{R, L + l + M + 1, L + r + M\}。

此外，Step 3 中我们提到可能剩下的 l 或 r 乱放导致贡献减少，由于最后剩下的 l 或 r 数量是 |l-r|-M-1，另一个上界是 L+R-\max(0,|l-r|-M-1)。

两个上界取 \min 即是答案。