题目链接

本题码量不大，但是事实上是一道极其难想的思维题。

题目描述

你有 \(a\) 个 a，\(b\) 个 b，\(c\) 个 c。要求用这 \(a+b+c\) 个字母拼接成一个字符串，使得这个字符串的最小表示法在所有能拼成的字符串中最大。

补充：最小表示法，将一个字符串的最后一个字符放到首位，重复这个操作，最终得到的 \(n\) 个字符串中字典序最小的即为它的最小表示法。例如 \(\texttt{abacba}\) 重复上面操作会得到如下字符串：

它的最小表示法即为 \(\texttt{aabacb}\)。

数据范围：\(a+b+c \le 50\)。

加强版：\(a+b+c \le 10^5\)。

solution

先说下解法吧，首先我不会 ATcoder 给的二分 dp 做法，但是现在的主流做法都是用贪心。

具体算法流程比较简单：

1. 将所有字符串存下来。
2. 找到这些字符串中最小的和最大的，拼接到一起后插入，然后删除原来的两个字符串。
3. 重复 2 操作，直到只剩一个字符串为止。

看起来很简单，但是大部分人其实都想不到（包括我），接下来说一下这个做法的证明。

考虑数学归纳法，假设当你有三个字符串 \(s_1, s_2, s_3\)（假设 \(s_1 < s_2 < s_3\)）时，拼接的最优方案为 \(s_1 s_2 s_3\) 成立，那么当我们有一个串 \(s_1s_2\cdots s_k\) 时，有一个另外的字符串 \(s_{k+1}\)（\(s_1<s_2<\cdots < s_{k+1}\)），那么我们把后面 \(s_2s_3\cdots s_k\) 看作一个整体，即为 \(s\)，那么易知 \(s<s_{k+1}\)。那么我们可以得到最大的字符串即为 \(s_1 s_{k+1} s\)。

而当最小的情况（\(1\) 个 a，b，c）时，易证该情况成立。

因此我们上面的算法正确。

当然这里还有一点漏洞，就是我们必须保证集合中的所有字符串都为最小表示法。而我们的算法中最小和最大拼接的时候就可以保证这一点性质。因此可以这么做。

代码就不放了，用 multiset 就可以做。时间复杂度 \(O((a+b+c)\log (a+b+c))\)。