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;
}