题解：P1012 [NOIP 1998 提高组] 拼数

hhhqx · 2025-08-09 09:23:21 · 题解

前置知识：

• 对于一个以 y 为循环节的小数，设其分数 x 满足 0 < x < 1。
• 显然 x \times 10^{|y|} - y = x，得到 x = \dfrac{y}{10^{|y|} - 1}。
• 所以 \dfrac{y}{10^{|y|} - 1} = 0.yyyyyy\cdots。

回到这题，想要多个数字拼起来最大，即拼接后的字典序最大（因为长度显然是固定的）。

按 s_i + s_j > s_j + s_i(i < j) 排序然后依次拼接就是字典序最大，证明如下：

• 设 s_i 长度是 n，s_j 长度是 m。
• 设 a_i 为 s_i 的数字形式。
• 推式子：
• 根据前置知识，得 s_i + s_j > s_j + s_i \iff s_i + s_i + s_i + \cdots > s_j + s_j + s_j + \cdots。

现在唯一问题就是要证这个排序能得到最优解。

法一

假设前面的选完了，我们要在在后面选一个。肯定优先选字典序大的，但是长度不一样怎么办。

现在在我们考虑范围内的字符串，类似这样（相同颜色的字符串相等）：

设两个字符串 s 和 s + t，按照我们那个排序方式。

• 如果 s + s > s + t \iff s > t 肯定先选 s 没问题，因为这两个串至少可以拼成 s + s + t。
• 如果 s + t < s + s \iff s > t 肯定先选 s+t 没问题，因为你选 s 后，后面能拼的开头肯定也都是 s。

法二

如果没有排序完，一定存在 s_i + s_i + \cdots < s_{i+1} + s_{i+1} + \cdots。

证明交换 s_i,s_{i+1} 不会更劣即可。

和法一末尾部分一样。

Code

我这证法还是太tang了，我是先转化排序条件，再证最优性。

建议去看看 喵仔牛奶 的题解喵。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n;
string a[30];

bool cmp(string x, string y){
  return x + y > y + x;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n, cmp);
  for(int i = 1; i <= n; i++){
    cout << a[i];
  }
  return 0;
}