自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

搬运于2025-08-24 21:50:30，当前版本为作者最后更新于2022-12-27 11:16:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题的做法属于是官解吊打题解区了。

我们有一个结论：最终答案一定要么左端点在最左的三个之一，要么右端点在最右的三个之一。这是我们需要证明的。

运用反证法，反之，每一个最优解都满足左右至少有三格的位置可以扩展，也就是字符串的形式至少是 a b c w d e f，其中数字代表未知的字母，而 w 代表其中一个最优解（将符合条件的解称为“答案”）。注意 w 是字符串，其他六个字母都是字符。

记 $|X|$ 表示字符 $X$ 在 w 中出现的次数，其中 $X$ 是题目给出的三种字符之一。

让我们分几类情况讨论：

1. w 中只含一种字母。

由于整个字符串单第一个字符也可以构成一个长度为 1 的答案，所以 w 的长度一定超过 1。不妨 $|B|>1$ 而 $|C|=|S|=0$。

这样我们考察 c w这个串，如果 c 是 $B$，那么显然 c w 只含一种字符，是可行的答案。否则，不妨 c 是 $C$，那么在 c w 中 $|B|'>1=|C|'>0=|S|'$ 成立，那么 c w 也是答案，矛盾。

2. w 中不止一种字母。

不妨 $|B|>|C|>|S|$。

那么显然 c 和 d 都不是 $B$，否则不妨 c 是 $B$，那么在 c w 中 $|B|'=|B|+1>|B|>|C|=|C|'>|S|=|S|'$，则 c w 也是答案，矛盾。

否则：

• 若 c 和 d 中有 $C$，不妨 c 是 $C$。

考察 c w，它不是答案的唯一可能性就是 $|C|'=|B|'$，换而言之 $|C|+1=|B|$。那么再考虑 c w d，此时若 d 或 b 是 $B$ 或 $C$ 都已经使得 c w d 是答案推出矛盾，所以 b 和 d 都是 $S$。接着考虑 c w d e，若 e 是 $B$ 或者 $C$ 都已经使得 c w d e 是答案推出矛盾，所以 e 是 $S$。

那么考虑 w d，它不是答案的唯一可能性就是 $|S|'=|C|'$，换而言之 $|S|+1=|B|$。观察 w d e 这个串，他满足 $|S|'=|B|'=|C|'+1$。那么 f 如果是 $S$ 或者 $B$ 的话 w d e f 就是答案了，推出矛盾。 所以 f 是 $C$。

如此一来我们可以先看一下现在的字符串长什么样：a S C w S S C。

在 S C w S S C 中已经有 $|S|'=|C|'=|B|'+1$，为了使得 a S C w S S C 不是答案，需要 a 是 $B$。但这个时候 B S C w 是答案，矛盾！

• 若 c 和 d 全是 $S$：

考察 c w 和 c w d，它们都不是答案只可能是 $|B|=|C|+1=|S|+2$。

考察 b c w d，它不是答案说明了 b 是 $C$，同理 e 是 $C$。

考察 w d e f，它不是答案说明了 f 是 $S$，同理 a 是 $S$。

那么字符串变成了 S C S w S C S，观察到它本身就是答案，矛盾！

综上，证毕。

代码很好写，暴力枚举端点扫过去就可以了。