Codeforces Round 754 C.Dominant Character

警告
本文最后更新于 2021-11-29,文中内容可能已过时。

给出长度为 $n$ 的, 仅由 a, b, c 组成的字符串. 问长度最小的满足条件的子串, 条件为:

  1. 长度至大于等于 $2$
  2. a 在字串中的出现次数严格大于 b 的出现次数
  3. a 在字串中的出现次数严格大于 c 的出现次数

不存在输出 -1.

记录一下一个小时没写出来的简单题, 主要讲讲这种思维题怎么想.

贪心很容易知道, 子串开头结尾一定是两个 a.

然后没有很好的思路, 于是可以考虑从小数据开始玩, 尝试发掘性质.

题目问长度, 所以从长度小的开始玩.

aa, 满足条件, aba, aca 也满足条件. axxa 这样的东西(x 不能是 a), 如果是 abba 或者 acca 就不满足了, 如果是 abca 或者 acba 才满足.

然后 axxxa 根据鸽子原理, 一定会有两个 b 或者两个 c, 一定不满足.

再接着考虑 axxxxa, 如果 x 还是填 bc, 也一定不满足, 如果填 a, 则有一定满足的字串.

但是再长一点, 就不一样了. axxxxxa, 如果在中间填 a, 变成 axxaxxa, 根据之前分析的情况, 如果一组连续的 x 是不同字符, 则最小串就是他和两边的 a; 如果是相同字符, 这种 axxaxxa可能是最小字符串. 枚举情况, 仅有 abbacca 或者 accabba 恰好满足条件, abbabbaaccacca 不满足.

再往上推, 可以发现, 不能马上确定的字符串, 形如 axxabbacca. xx 无论是填 bb 还是 cc, 都无法使这个字符串满足条件. 归纳总结, axxa..abbacca..axxa 也不能.

其他情况, 要么存在 a间距小于 $2$ 的字串一定满足, 要么存在 a间距大于 $3$, 一定不会把他包含到任何字符串中(因为贡献为负数).

这就证明了最小长度不大于 $7$.