25.6.17 闲话：拼数怎么做？

喵仔牛奶 · 2025-06-17 19:44:28 · 题解

邻项交换

问题：

• 有一全序集 S 上的全序 \prec，给定 S 中元素组成的序列 p。
• 定义了序列的价值 f(p)，若 q 是 p 交换了一对 p_{i+1}\prec p_i 的 p_i,p_{i+1} 之后的排列，有 f(q)\le f(p)。
• 如何排列 p 以最小化 f(p)？

结论：排序 p 使得 p_i\prec p_{i+1}，此时 f(p) 最小。

证明：如果没有完成排序，一定存在 p_i\succ p_{i+1}。一直交换这样的对，可以得到排序后的 p 的 f(p) 不大于当前的 f(p)。

如果是偏序，这个结论就不一定正确了。

拼数

考虑最小化，最大化是一样的。

考虑构造这么一个全序 \prec：

• 定义 A\prec B 当且仅当 A+B<B+A，此处 + 为字符串拼接。

可以证明这是一个全序：

• 定义 a,b 分别为 A,B 在 \lvert\Sigma\rvert 进制下的数。
• 因此 a\prec b\land b\prec c\Longrightarrow a\prec c。

而交换相邻的 a_i\succ a_{i+1} 不会是答案变劣，根据前面的结论，这是对的。

不能比出大小的串按编号定义顺序，这样就是全序了。