题解 [email protected]洛谷 | [email protected] 【Largest Smallest Cyclic Shift】

这题在 AtCoder 的评分是 3266,感觉肯定是黑题,但是咋就通过了呢(

题意翻译的不够清楚,重新解释一遍:(做这题的时候看了好久也没看懂,然后就去原题看英文题面了)

定义 f(S)f(S) 为:对于一个字符串 SS,每次将它最左边的字符放置到字符串末尾生成的字符串集合中,字典序最小的字符串。例如:对于 SSbcbca 的情况,f(S)f(S) 即为 babcaabcabbcabacabababcbc 中最小的那个,即 abcbc

你需要构造一个字符串 TT,共包含 XX 个字符 aYY 个字符 bZZ 个字符 c,使得 f(T)f(T) 尽可能大,输出这个 f(T)f(T)


思路:

要使得 f(T)f(T) 尽可能大,每次循环求一遍显然不现实,最好构造出一种 TT 使得它本身就是 f(T)f(T)(即:T=f(T)T=f(T))。

那么怎么构造呢?

我们可以使用 multiset 来记录所有供选择的字符串,每次合并两个字符串,直到集合中只剩一个为止。合并的方法是取最小的字符串 aa 与最大的字符串 bb,将 bb 拼接到 aa 后面,重新加入集合。

这种情况下,这个前缀因为是最小的,所以从任何其它地方开头取字符串均不会更小,保证了 T=f(T)T=f(T)


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;

int x, y, z; multiset<string> qwq;

int main() {
	scanf("%d%d%d", &x, &y, &z);
	rep(i, 1, x) qwq.insert("a");
	rep(i, 1, y) qwq.insert("b");
	rep(i, 1, z) qwq.insert("c");
	while(qwq.size() ^ 1) {
		multiset<string>::iterator         it1 = qwq.begin();
		multiset<string>::reverse_iterator it2 = qwq.rbegin();
		string a = (*it1), b = (*it2), _ = a + b;
		qwq.erase(qwq.lower_bound(a)); qwq.erase(qwq.lower_bound(b));
		qwq.insert(_);
	}
	multiset<string>::iterator it = qwq.begin();
	cout<<(*it)<<endl;
	return 0;
}

(顺带一提,无意中还抢到了 R42600000,虽然有个地方错了 QAQAQ)