CF 2225 F 题解

• 题目链接

首先，我们来证明将字符串恰好分割成 k 个部分总是最优的。假设我们将其分割成 x > k 个部分；如果我们合并两个相邻的部分，可以证明按排序顺序排列的第 k 个部分的长度不会减少。$k$假设我们把它切成几部分。$x \gt k$各个部分；如果我们合并两个相邻的部分，可以证明：$k$按排序顺序排列的第 1 部分不会减少。

证明：某个多重集的第 k 个最小元素可以定义为满足以下条件的最小值：该多重集包含至少 k 个不大于 a 的元素。假设我们合并字符串的两个部分：$t_i$和$t_{i+1}$；那么合并后的部分构成的多重集中会移除元素$t\_i$和$t_{i+1}$，并插入一个新元素$t'_i = t_i + t_{i+1} > t_i$。对于任意字符串 a，不大于 a 的多重集中的元素个数不可能增加；因此，满足该多重集元素个数至少为 k 的最小值 a 不可能减少。所以，我们可以合并任意两个相邻的部分，结果都不会变差。$k$某个多重集的第个最小元素可以定义为最小值$a$使得多重集至少包含$k$元素不大于$a$假设我们将字符串的两个部分合并，$t_i$和$t_{i+1}$然后是元素$t_i$和$t_{i+1}$从结果部件的多重集中移除，并添加一个新元素。$t'_i = t_i + t_{i+1} \gt t_i$插入。对于每个字符串$a$多重集中的元素个数不大于$a$不能增加；因此，最小值$a$其中此类元素的数量至少为$k$不能减少。因此，我们可以合并任意两个相邻的部分，结果不会变差。

所以现在我们总是把字符串切成正好$k$部分。当$k=1$时，这意味着原始字符串本身就是答案（如果它的长度至少为$l$）；当$k \gt 1$时，我们需要考虑几个可能的答案，并从中选择最佳答案。$k$部分。当$k=1$这意味着原始字符串本身就是答案（如果它的长度至少为 1）。$l$）; 什么时候$k \gt 1$我们需要考虑几个可能的答案，并从中选择最佳答案。

假设我们要检查子串 $t = s_{L} s_{L+1} \dots s_R$ 是否可能是答案。那么必须满足以下条件：$t = s_{L} s_{L+1} \dots s_R$这可能是答案。那么必须满足以下条件：

• 位置 $L$ 之前的前缀可以切成长度至少为 $l$ 的字符串；$L$可以剪成至少一定长度的条状$l$；
• 位置 $R$ 之后的后缀可以截断为长度至少为 $l$ 的字符串；$R$可以剪成至少一定长度的条状$l$；
• 前缀和后缀可以被截断，使得它们组合在一起正好形成 $(k-1)$ 个字符串，并且所有这些字符串在字典序上都不大于 $t$。$(k-1)$字符串，并且所有这些字符串的字典序都不大于$t$。

第一和第二个条件很容易检查——如果前缀或后缀包含的字符数超过 $0$ 且少于 $l$，则它不能被分割成长度至少为 $l$ 的部分。然而，第三个条件的检查就困难得多。我们不直接检查它，而是利用我们感兴趣的最大合适字符串 $t$ 的特性。这使得我们可以简化第三个条件，去掉剩余部分在字典序上不能大于 $t$ 的要求——如果存在一个字典序大于 $t$ 的字符串，那么我们也将其视为候选字符串，这意味着当前的字符串 $t$ 无论如何都不可能是答案。$0$且少于$l$如果是字符，那么它至少不能被切割成若干长度的部分。$l$然而，第三个条件更难验证。我们不直接验证它，而是利用我们感兴趣的是最大合适字符串这一事实。$t$这样，我们就可以简化第三个条件，去掉剩余部分在字典序上不能大于某个特定值的要求。$t$— 如果在这些部分中存在一个字符串，其字典序大于$t$那么，我们也会将其视为候选字符串，这意味着当前字符串$t$无论如何，这都不可能是答案。

这样，我们可以将条件重新表述如下：

• 位置 $L$ 之前的前缀可以切成长度至少为 $l$ 的字符串；$L$可以剪成至少一定长度的条状$l$；
• 位置 $R$ 之后的后缀可以截断为长度至少为 $l$ 的字符串；$R$可以剪成至少一定长度的条状$l$；
• 前缀和后缀可以被截断，使得它们组合在一起正好形成长度至少为 $l$ 的 $(k-1)$ 个字符串。$(k-1)$长度至少为$l$。

对于单个子串，这些条件可以在 $O(1)$ 内检查，这给我们提供了 $O(n^2)$ 个候选对象。$O(1)$这使我们有$O(n^2)$候选人。

利用从位置$L$到位置$(R+1)$的子串在字典序上总是大于从位置$L$到位置$R$的子串这一事实，可以将候选子串的数量减少到$O(n)$。因此，我们可以遍历左边界$L$，并为每个左边界找到满足所有条件的最大右边界$R$。这可以通过一个相当简单的计算来实现——我们需要确定前缀可以得到多少个子串，这将表明最小后缀长度是多少。$O(n)$利用位置子字符串这一事实$L$定位$(R+1)$始终在字典序上大于位置 的子字符串。$L$定位$R$因此，我们可以遍历左边界。$L$并找到它们各自的最大右边界$R$满足所有条件。这可以通过一个相当简单的计算来实现——我们需要确定前缀可以分成多少个部分，这将表明后缀的最小长度必须是多少。

现在我们有 O(n) 个字符串，每个字符串都是原字符串的子串，我们需要从中选择字典序最大的那个。遗憾的是，问题中的约束条件过于严格，无法方便地使用后缀结构（至少我们无法让后缀数组足够快速地工作）。我们提出两种解决方案：$O(n)$多个字符串，每个字符串都是原始字符串的子字符串。$s$其中我们需要选择字典序最大的那个。遗憾的是，问题中的约束条件过于严格，无法方便地使用后缀结构（至少我们无法让后缀数组运行得足够快）。我们提出两种解决方案：

方法 1 — 哈希值 (FelixArg)

为字符串的所有前缀构建多项式哈希，并预先计算哈希基的所有幂（以及可能的模逆——尽管这不是必需的）。这使我们能够在$O(1)$中检查两个子串是否相等。$O(1)$。

但仅仅比较相等性是不够的；我们需要确定两个子串哪个更大，哪个更小。我们可以使用二分查找法，在 O(log n) 的时间复杂度内计算出两个子串的最长公共前缀。最长公共前缀之后的下一个字符就告诉我们哪个子串更大。一旦我们能够在 O(log n) 的时间复杂度内比较两个子串，我们就可以轻松地在 O(n log n) 的时间复杂度内找到其中的最大值。$O(\log n)$使用二分查找法比较子串的长度。最长公共前缀之后的下一个字符可以告诉我们哪个子串更长。一旦我们能够比较两个子串的长度，$O(\log n)$我们可以很容易地找到其中的最大值。$O(n \log n)$。

为避免碰撞问题，我们建议使用双基/模哈希。

方法 2 — z 函数 (BledDest)

取候选答案 $t$，构建字符串 $t + d + s$ 的 z 函数，其中 $d$ 为分隔符。z 函数将显示 $t$ 与其他每个候选答案的最长公共前缀的长度。这使我们能够将 $t$ 与其他候选答案进行比较，从而将它们分成三组：$t$并为该字符串构建 z 函数$t + d + s$， 在哪里$d$是某种分隔符。z 函数将显示最长公共前缀的长度$t$以及其他每位候选人的答案。这使我们能够进行比较。$t$与其他候选人一起，因此将他们分成三组：

• 小于 $t$;$t$；
• 等于 $t$;$t$；
• 大于 $t$。$t$。

如果第三个集合为空，那么$t$就是问题的答案，因为它是最大值。否则，我们只对第三个集合感兴趣，可以继续分析它，而无需分析所有候选集合。$t$由于它是最大值，因此是问题的答案。否则，我们只对第三组感兴趣，可以继续分析它，而无需分析所有候选集。

如果我们随机选择候选答案，平均需要处理 $O(\log n)$ 个候选答案（这可以用与随机快速排序的递归深度或随机笛卡尔树的深度大致相同的方式证明）。每个候选答案的检查时间为 $O(n)$，因此总复杂度为 $O(n \log n)$。$O(\log n)$候选答案的平均值为（这可以用与随机快速排序的递归深度或随机笛卡尔树的深度大致相同的方式证明）。每个候选答案都会被检查。$O(n)$，总复杂度为$O(n \log n)$。