官解yyds

UnyieldingTrilobite · 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，观察到它本身就是答案，矛盾！

综上，证毕。

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