题解：CF1968G1 Division + LCP (easy version)

2024 年 05 月 03 日

12 次浏览

634字数

题目翻译

给定长度为 $n$ 的字符串 $s$ 以及 $l,r$。

对于所有 $k\in[l,r]$ 求出将 $s$ 分成 $k$ 段后每段的 LCP 长度最大值。

LCP 是最长公共前缀。

$1\leq n\leq 2\times 10^5,1\leq l\leq r\leq n$。多测。$1\leq \sum n \leq 2\times 10^5$。

在 Easy Version 中，满足 $l=r$。

题目思路

也就是 Easy Version 只要求出一个 $k$ 对应的解。

我们考虑到 LCP 长度有单调性，可以二分答案。

当然开头的若干个就是需要判断是否合法的 LCP。

check 考虑贪心枚举每一位，判断将这一位作为开头是否有一个 LCP，如果可以直接跳掉。最后判一下是否有 $\geq mid$ 个位置开头能构成 LCP。

考虑到你不在前一位截出一个 LCP，在后一位开始只会导致少截出 LCP。贪心正确。

这个代码是 G2 过了交上的，但是问题不大。这里的 calc 函数就是求答案。直接 cout << calc(l) << endl; 是可以过 G1 的。