HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】AT1976 [ARC058D] 文字列大好きいろはちゃん / Iroha Loves Strings
热度: loading...
这道题很罕见地题解数达到了通过数的 。
从 个字符串中选出一些字符串，在不改变相对位置的情况下将其拼接起来，使其长度为 。求字典序最小的方案。
对于每个长度 ，求出 表示 利用 到 的字符串能拼出长度为 的最右位置。即取了一些字符串后，想让剩下的字符串能拼出 的最远位置。
这个部分我们用 bitset 求解。设 bitset ，表示前 个串拼起来的长度为 时，用后面的串能拼到 。初始值设 ，设第 个串的长度为 ，那么 。如果 且 ，那么 。
考虑设 为选取一些串，拼成长度为 的串所能拼出的最小串， 为选取一些串，拼成长度为 的串所能拼出的最小串的最右位置。
考虑 dp。枚举 ，枚举一个长度 ，在 到 中找出字典序最小的长度为 的串，并用此更新 。最后输出 即可。
问题变成了求一个区间内长度相同的串中的最小串。枚举每个长度，对所有这个长度的串倍增 RMQ 预处理即可。
复杂度高，但常数较小，能过。至此本题全部完成。
赏
