Codeforces Round 754 C.Dominant Character
给出长度为 $n$ 的, 仅由
a,b,c组成的字符串. 问长度最小的满足条件的子串, 条件为:
- 长度至大于等于 $2$
a在字串中的出现次数严格大于b的出现次数a在字串中的出现次数严格大于c的出现次数不存在输出
-1.
记录一下一个小时没写出来的简单题, 主要讲讲这种思维题怎么想.
贪心很容易知道, 子串开头结尾一定是两个 a.
然后没有很好的思路, 于是可以考虑从小数据开始玩, 尝试发掘性质.
题目问长度, 所以从长度小的开始玩.
aa, 满足条件, aba, aca 也满足条件. axxa 这样的东西(x 不能是 a), 如果是 abba 或者 acca 就不满足了, 如果是 abca 或者 acba 才满足.
然后 axxxa 根据鸽子原理, 一定会有两个 b 或者两个 c, 一定不满足.
再接着考虑 axxxxa, 如果 x 还是填 b 或 c, 也一定不满足, 如果填 a, 则有一定满足的字串.
但是再长一点, 就不一样了. axxxxxa, 如果在中间填 a, 变成 axxaxxa, 根据之前分析的情况, 如果一组连续的 x 是不同字符, 则最小串就是他和两边的 a; 如果是相同字符, 这种 axxaxxa 才可能是最小字符串. 枚举情况, 仅有 abbacca 或者 accabba 恰好满足条件, abbabba 或 accacca 不满足.
再往上推, 可以发现, 不能马上确定的字符串, 形如 axxabbacca. xx 无论是填 bb 还是 cc, 都无法使这个字符串满足条件. 归纳总结, axxa..abbacca..axxa 也不能.
其他情况, 要么存在 a 的间距小于 $2$ 的字串一定满足, 要么存在 a 的间距大于 $3$, 一定不会把他包含到任何字符串中(因为贡献为负数).
这就证明了最小长度不大于 $7$.