mydcwfy's Blog

AT Code Festival 2017 Qual B F Largest Smallest Cyclic Shift

Posted on
Symbols count in article: 2k Reading time ≈ 4 mins.

神秘贪心 + 构造题。

题意：有 $x$ 个 a，$y$ 个 b，$z$ 个 c，所有由这些字符组成的字符串中，设 $f(S)$ 为 $S$ 的最小表示，求最大的 $f(S)$。$A + B + C\leq 50$。

有一个神秘的做法：首先需要保证 $S = f(S)$，然后保证 $S$ 最大；维护一个 std::multiset，表示所有待合并的字符串。每次拿出最小的和最大的，拼起来放回去，最后就可以得到答案。

怎么证明？不太会，谁叫官方题解和这个做法一点关系没有 /kk，网上的证明大多是没有说明白的，找到了 CF 上的 讨论，大概知道了。

首先我们需要判断这两个构造方案是相同的。打一个表就可以发现时刻 std::multiset 里面都只有 3 种串。也是好证明的，因为我们拿着两种串”厮杀“，最后肯定会有一个串没有了，产生的串都是一种，所以时刻都只有 3 种串。接着自己手动推一下，其实就是 CF 讨论的构造方法。

下面我们来证明一下正确性。首先我们看到剩下的 3 种串一定都是严格有比较大小的，也就是我们把 a 放在开头一定是比 b 放在开头小，b 比 c 放在开头小。对于第一种变化后的情况 ac, b, c，开头不一样，显然合法。a, ac, b，虽然 a 和 ac 相同，但是我们找不到其他的前缀满足接在 a 后面还能和 ac 相同的，所以一旦 a 放在前面，肯定比 ac 放在前面小。

那么根据上面的说法，我们很容易得到最小表示的开头一定是 a，显然考虑贪心，我们如果在所有的 a 后面都接上 c，这样的最小表示一定是最大的，我们就可以递归下去计算答案；如果 a 无法全部接 c，那么剩余的 a 也是剩下的 3 种串中最小的，我们还是在 a 的后面接最大的串，这个其实又是相当于递归计算的过程了。

综上，我们就可以得到该算法的正确性了。下面有 std::multiset 和递归写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
	int A, B, C;
	std::cin >> A >> B >> C;
	while (A --) all.insert("a");
	while (B --) all.insert("b");
	while (C --) all.insert("c");
	while (all.size() > 1)
	{
		auto itera = all.begin(), iterb = -- all.end();
		std::string add = *itera + *iterb;
		all.erase(itera), all.erase(iterb), all.insert(add);
	}
	std::cout << *all.begin() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::string solve(std::vector<std::string> s, std::vector<int> cnt)
{
	if (!cnt[0] && !cnt[2]) return s[1] * cnt[1];
	if (cnt[0] && cnt[2]) {
		if (cnt[0] >= cnt[2])
			return solve({s[0], s[0] + s[2], s[1]}, {cnt[0] - cnt[2], cnt[2], cnt[1]});
		else return solve({s[0] + s[2], s[1], s[2]}, {cnt[0], cnt[1], cnt[2] - cnt[0]});
	}
	if (!cnt[0]) {
		if (!cnt[1]) return s[2] * cnt[2];
		else return solve({s[1], "", s[2]}, {cnt[1], 0, cnt[2]});
	} else {
		if (!cnt[1]) return s[0] * cnt[0];
		else return solve({s[0], "", s[1]}, {cnt[0], 0, cnt[1]});
	}
}
 
int main()
{
	int A, B, C;
	std::cin >> A >> B >> C;
	std::cout << solve({"a", "b", "c"}, {A, B, C}) << '\n';
	return 0;
}