关于本题难度的一些解释

争端太多了。主要是因为 LA 已经吵完的东西我真的懒得再给每个人都解释一遍，就发了这个帖子。应该能解决

99\%

的问题。

首先你可以将自己分为以下三类人，然后到对应的板块查看理由：

我没做过这题，但难道结论不是一眼出？

好的。那么请你认真思考并确认你的解法是否正确，再与正解进行比较。注意，如果你在得出正解前查看，你的体感题目难度将作废。

结论

这是几乎唯一正确的结论。如果你的结论与这个不符或无法通过简单方式转化，那么极大概率你错完了。

称

S\preceq T

当且仅当

S+T\le T+S

。按

\preceq

从大到小排序拼接即可。

如果你不能独立得出这一结论，那么请你慎重参与后续讨论。

对的那些说这题最高难度在于 sort 的，我说的就是你们。给我闭上嘴。

证明也没多难啊，胡一胡就完了吧？

这是一个邻项交换问题。你需要证明的是邻项交换的比较条件

\preceq

满足是一个弱序关系，即：

注意，不要对着调整法瞎胡，否则你有近乎

100\%

的概率是错误的，错法包括但不限于错失全局最优解。同样的，请确保你的证明是独立得出的。如果你已经看过题解证明，那么你的体感证明难度将作废。请慎重参与后续讨论。

具体如何证明？

大致两种证法：

通过分讨 $S$ 与 $T$ 的前缀包含关系，可以证明 $S+T\le T+S$ 等价于 $S+S+S+\cdots\le T+T+T+\cdots$ ，从而转化为弱序关系。
通过将字符串转化为 $k$ 进制正整数，移项后可以将两边独立开，从而转化为弱序关系。

欸这个题范围很小啊，是不是暴力搞一搞也对？

现在请你给出一个复杂度正确的所谓“暴力”。如果不能，请慎重参与后续讨论。

一种可能的解法

考虑状态压缩 dp，直接转移可以做到

\mathcal{O(2^nn\log V)}

。但是会面临一个两个很尴尬的问题：

所以并不是大家所说的“暴力”可以随便过。如果你没想到这一步，也请你慎重参与后续讨论。

看完这些后你应该可以理性思考了。

讨论操作