【2025牛客五一集训派对day4 C】题解

比赛链接

题目链接

题目大意

给定 $N$ 个字符串，问怎么拼接使得组成的整数最小。

Solution

结论：将数组 $s$ 按照 $s_i+s_j<s_j+s_i$ 排序输出是最优的。

• $+$ 是字符串拼接，例如 $1+2=12$；
• $<$ 是按照字典序来的，例如 $10<2$，$23<232$。

正解是 $O(N)$ 的 $\text{Trie + z}$ 函数，但是不太会，所以下面只讲这样排序可行的证明。

考虑偏序关系 $A\prec B$ 表示 $AB<BA$，其中 $AB=A+B,BA=B+A$。

首先考虑三个等长字符串 $A,B,C$，若 $A\prec B$ 且 $B\prec C$，显然有 $A\prec C$。

• 设 $L=|A|=|B|=|C|$，$A\prec B$ 表示 $AB<BA$，那么一定可以找到最小的 $i\in [1,L]$ 使得 $A_i<B_i$，否则 $A=B$，就有 $AB=BA$，矛盾；
• 同理可以找到最小的 $j\in [1,L]$ 使得 $B_j<C_j$；
• 若 $i=j$，则 $A_i<B_i=B_j<C_j$；
• 若 $i<j$，则 $A_i<B_i=C_i$；
• 若 $i>j$，则 $A_j=B_j<C_j$。
• 所以 $A<C$。
• 而 $|A|=|C|$，拼起来也不改变前 $L$ 个字符，所以 $AC<CA$，即 $A\prec C$。

设 $A^n=\underset{共n个A}{\underbrace{AA\cdots A}}$，下证：对任意字符串 $A,B$，$A\prec B$ 等价于 $A^n\prec B$。

首先证明 $A\prec B\Rightarrow A^n\prec B$。考虑数学归纳法。

由 $A\prec B$ 有 $AB<BA$，在前面同时加上 $A$，得到 $AAB<ABA$，在后面同时加上 $A$，得到 $ABA<BAA$，这就得到了 $AAB<BAA$，也就有 $A^{2}B<B{A}^2$，即 $A^2\prec B$。

设 $A^{n-1}\prec B$，那么有 $A^{n-1}B<B{A}^{n-1}$，在前面同时加上 $A$，得到 $A^{n}B<AB{A}^{n-1}$，在 $AB<BA$ 后面同时加上 $A^{n-1}$，得到 $AB{A}^{n-1}<B{A}^n$，于是有 $A^{n}B<B{A}^n$，则 $A^n\prec B$。

而 $A\prec B^n$ 同理可证（就是把同时加 $A$ 改成同时加 $B$）。

接着证明 $A^n\prec B\Rightarrow A\prec B$。考虑反证法。

若 $A\nprec B$，那么一定有 $AB=BA$ 或 $B\prec A$。

• 若 $AB=BA$，则 $A^{n}B=A^{n-1}AB=A^{n-1}BA=\cdots =B{A}^n$，与 $A^n\prec B$ 矛盾；
• 若 $B\prec A$，则 $B\prec A^n$（这是上一段证明推导出的结论），与 $A^n\prec B$ 矛盾。

因此 $A\prec B⟺A^n\prec B⟺A\prec B^n$，再进一步就是

$$A\prec B⟺A^n\prec B^m.$$

其中 $n,m$ 是任意正整数。

这样，对于三个长度不同的字符串 $A,B,C$，我们可以找到它们的最小公倍数 $L=\text{lcm}(|A|,|B|,|C|)$，然后拼接成长度均为 $L$ 的字符串进行比较，即若

$$A\prec B\prec C,$$

则

$$A^{\frac{L}{|A|}}\prec B^{\frac{L}{|B|}}\prec C^{\frac{L}{|C|}},$$

而长度相同的传递性显然，所以有

$$A^{\frac{L}{|A|}}\prec C^{\frac{L}{|C|}},$$

再由 $A\prec B⟺A^n\prec B^m$，得到

$$A\prec C.$$

这样对于任意字符串传递性都保证了。

C++ Code

#include <bits/stdc++.h>template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {for (auto &x: v) {is >> x;}return is;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;std::cin >> N;std::vector<std::string> S(N);std::cin >> S;std::ranges::sort(S, [&](const auto &a, const auto &b) {return a + b < b + a;});for (const auto &s: S) {std::cout << s;}return 0;
}