题解 CF1368B 【Codeforces Subsequences】

liuyongle · 2020-08-27 13:34:34 · 题解

假设我们要寻找的是 abcd 子序列，而不是 codeforce 子序列。然后，在最佳字符串中，所有 a 都出现在前面。将 a 的任何其他事件移到最前面将使所有其他事件保持不变，并且仅可能创建新事件。由于类似的原因，所有 b 都应立即跟随，然后再移动所有 c，依此类推。

问题在于：我们应该取多少个 a，b，或是其他字符？

我们应该使每个字母的数量尽可能地接近。实际上，子序列的数量是 n_a \times n_b \times n_c \times n_d \times n_e，其中 n_a,n_b,\dots是每个字母的出现次数。如果说，n_a - n_b > 1，那么不难证明将 a 转换为 b 会增加乘积。现在，可以简单地通过循环增加 n_a,n_b,\dots 来获得最佳分布。一旦乘积至少为 k，我们应该停止。

但是，如果子序列重复出现字母，则此方法将无法很好地工作。当然，很自然地希望相同的模式适用于具有代码强制子序列的最佳字符串：它具有很多独特的字母，重复的字母相距甚远。几乎没有必要，但是这是证明模式有效的一种方法：

字母 d，f，r，s 应形成连续的块。例如，如果两个 d 被其他字母分隔，我们可以查看哪个 d 存在于子序列中的数量更少，而在出现次数更多的子序列中更多。相同的思想适用于所有其他字母。 在 e 和 d 之间放置除 e 之外的其他任何内容都没有意义。确实，任何其他字母都不会出现在任何子序列中。同样，在 f 和 r 之间只能有 o。现在我们知道该字符串看起来像 ddddeeefffooorrrsss。 最后，只有 c 和 o 可以位于 d 之前，并且将 o 置于 c 之前没有意义。同样，c 和 e 以此顺序占据 r 和 s 之间的空间。 因此，可以采用与上述相同的解决方案来解决该问题。