AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 题解

题意：

定义 $f(S)$ 为：对于一个字符串 $S$，每次将它最左边的字符放置到字符串末尾生成的字符串集合中，字典序最小的字符串。例如：对于 $S$ 为 babca 的情况，$f(S)$ 即为 babca、abcab、bcaba、cabab、ababc 中最小的那个，即 ababc。

你需要构造一个字符串 $T$，共包含 $X$ 个字符 a、$Y$ 个字符 b 和 $Z$ 个字符 c，使得 $f(T)$ 尽可能大，输出这个 $f(T)$。

数据范围：$1 \le X + Y + Z \le 50$ 。

非常有趣的贪心题。注意到 $X=Y=Z$ 时，最优方案是 $\tt abc$ 。

考虑递归的构建字符串。设 $s_1,s_2,s_3$ 是当前最优的三个字符串，规定 $s_1 < s_2 < s_3$ 。

显然我们会选择 $s_1s_3s_2$ 的形式，因为在 $s_1,s_2,s_3$ 最优的情况下你怎么转这个都是最优的。

若此时再加入一个 $s_4 > s_3$ ，考虑把它放到 $s_3$ 的前面，即 $s_1s_4s_3s_2$ ，也可以证明是最优的。

有趣的是，这种情况下，相当于不断地把当前最小和最大的合并，即 $s_1s_4$ ，然后 $s_1s_4s_3$ ，最后加上 $s_2$

这使得我们考虑，是否对于任意的 $k$ ，最优方案为 $s_1s_k \cdots s_2$ 。可以证明这是正确的。

证明考虑归纳法证明。假设对于某个 $k$ ，小于等于 $k$ 的情况均成立，考虑 $k+1$ 的情况。

对于串 $s_{k+1}$ ，此时 $s_1$ 依然在最前面，而因为 $s_{k+1} > s_k$ ，所以 $s_k$ 后面的串都是小于 $s_{k+1}$ 的

如果我们把 $s_k\cdots s_2$ 看作一个整体，那么这个串就是原来的 $s_2$ ，而 $s_{k+1}$ 相当于 $s_3$ 。

采用 $s_1s_3s_2$ 的规则，可得 $s_1s_{k+1}s_k\cdots s_2$ ，故 $k+1$ 的情况也满足。 $\square$

那么我们可以用一个 multiset<string> 来维护这个东西，每次取出当前的最小值和最大值合并即可。

时间复杂度 $\mathcal{O}(n^2 \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

multiset<string> s; int a,b,c;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> a >> b >> c;
    while(a--) s.insert("a");
    while(b--) s.insert("b");
    while(c--) s.insert("c");
    while(s.size() > 1)
    {
        auto x = s.begin(), y = prev(s.end());
        s.insert((*x) + (*y)); s.erase(y); s.erase(x);
    }
    cout << *s.begin() << '\n';
    return 0;
}