[ABC434F] Concat (2nd) 题解

· · 题解

十一月二十九日，吾与 ABC 之试，乱搞而解 F，得效值（Performance）二千四百，甚悦。

解法

简化问题

最小的排列方式是很典的。考虑先求出这个东西。

考虑邻项交换。将所有字符串按照 s+t<t+s 排序，就能得到最小的拼接方法。

直接写 s+t < t+s 作为排序规则会被卡掉，所以需要优化。

考虑把 s+t 和 t+s 分成三段，从前往后，使用字符串比较大小的方法判断大小即可。

比较字符串的经典套路是，找到它们的最长公共前缀（LCP），然后比较 LCP 后一个位置谁大谁小。找 LCP 可以使用哈希加二分解决。单次查找 O(\log |S|)。

时间复杂度不知道，总之跑的飞快。

原题

开始考虑次小字符串。

记最小的排列方法为 s_{p_1},s_{p_2},\dots,s_{p_n}，其中 p 是一个 1 \sim n 的排列。

如果存在相邻的 p_i,p_{i+1} 使得 s_{p_i}+s_{p_{i+1}}=s_{p_{i+1}}+s_{p_i}，则次小排列可以通过交换这一对得到。

当且仅当上述条件满足时，次小字符串与最小字符串相同。

这个东西可以使用 s+t=t+s 判断。时间复杂度 O(\sum |S|)。

由此我们继续猜测，猜测次小的排列是在最小的基础上，交换一对 p_i 和 p_{i+1} 得到的。

根据直觉，这个 i 一定在老后面。所以对于最后 50 个 i 进行尝试即可 AC。

时间复杂度 O(能过)。Submission。

彩蛋