题意简述
给你一个长为 $n$ 的字符串 $S$ ,你可以进行下面的操作 $k$ 次:
将 $S$ 翻转后接在 $S$ 后面得到一个长为 $2n$ 的字符串 $U$,再将 $S$ 改为 $U$ 的一个长为 $n$ 的子串。
求最后所得字典序最小的字符串。
$1\le n\le 5000, 1\le k\le 10^9$ 。
主要思路
设 $S$ 中最小的字符为 $c$ , $U$ 中最长的连续 $c$ 的个数为 $mxl$ 。
若 $2^k\times mxl \ge n$ ,则我们可以每次将最长连续 $c$ 的结尾作为选择的新 $S$ 的结尾,这样最后字符串将变为 $n$ 个 $c$ 。
否则,最后字符串必定开头有 $2^k\times mxl$ 个 $c$ 。而后面的 $n - 2^k\times mxl$ 个字符为第一次选择的新 $S$ 的翻转后的 $[mxl + 1, mxl + n - 2^k\times mxl]$ 字串。
注意到 $n\le 5000$ ,暴力比对取字典序最小即可。
若 $n$ 较大,也可使用各种后缀排序的算法 $O(n\log n)$ 或 $O(n)$ 解决。
果然这场的难度是乱序排的……另外这题在kenkoooo上的难度是 2845 ,在 AGC 的 E 来说是评分很低的。
参考代码
1 |
|