25.6.17 闲话：拼数怎么做？

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

邻项交换

对于一个集合 S，定义二元关系 \prec 是它上的严格全序，当且仅当：

• 反自反性：\forall a\in S,\lnot(a\prec a)，即 a 不能“小于”自己。
• 非对称性：\forall a,b\in S, a\prec b\implies \lnot(b\prec a)，即 a“小于”b 则 b 不能“小于”a。
• 传递性：\forall a,b,c\in S, (a\prec b\land b\prec c)\implies a\prec c，即如果 a“小于”b 且 b“小于”c 则 a“小于”c。
• 连接性：\forall a,b\in S,a\neq b\implies(a\prec b\lor b\prec a)，即任意两个不同数都可以“比大小”。

问题：

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

结论：找到 p 的排列 q' 使得 \forall i\in[1,n),q'_i\prec q'_{i+1}，f(q') 即为答案。

证明：

• 由于是严格全序且没有相同元素，q' 是唯一的。
• 因此如果 q\neq q'，一定存在 q_i\succ q_{i+1}。
• 对于任意 p 的排列 p，一直交换这样的对，最后会得到 q'（每次逆序对减少 1，只有 q 逆序对为 0）。
• 根据性质，每次交换后 f(q) 不会变大，因此 f(q)\ge f(q')。

因此邻项交换的证明需要注意：证明是严格全序，尤其是传递性与连接性；证明交换后不变劣。

拼数

定义一个二元关系 \prec，A\prec B 当且仅当以下两个条件满足一个：

对于字符串 A，设它的编号是 id_A，在 10 进制下的数是 a，则定义它的权值 f(A)=-\frac{a}{10^{\lvert A\rvert}-1}+\epsilon\times id_A（可以认为其中 \epsilon=10^{-100}）。

此时，A\prec B 当且仅当 f(A)<f(B)：

• 当 A+B\neq B+A 时，A\prec B\Longleftrightarrow A+B>B+A\Longleftrightarrow a\cdot10^{\lvert B\rvert}+b>b\cdot10^{\lvert A\rvert}+a\Longleftrightarrow\frac{a}{10^{\lvert A\rvert}-1}>\frac{b}{10^{\lvert B\rvert}-1}\Longleftrightarrow f(A)<f(B)；
• 当 A+B=B+A 时，A\prec B\Longleftrightarrow id_A< id_B\Longleftrightarrow f(A)<f(B)。

显然 < 是 \mathbb R 上的严格全序，因此 \prec 是严格全序。

如果存在 a_i\succ a_{i+1}，令 A=a_i,B=a_{i+1}，那么：

• 要么 A+B<B+A，显然交换后这段字典序变大，剩下部分不变，不会变劣。
• 要么 A+B=B+A，此时交换后拼成的数不变，不会变劣。

因此证明完成：\prec 是严格全序；交换相邻的 a_i\succ a_{i+1} 不会使答案变劣。