Codeforces Round 843 (Div. 2) A2. Gardener and the Capybaras (hard version)

zsxuan / 2023-09-05 / 原文

有三个字符串 $s_1, s_2, s_3$ ，每个字符串只有 $a, b$ 组成。三个字符串顺序连接在了一起。满足以下条件之一：

$s1 \leq s_2, s_3\leq s_2$
$s1 \geq s_2, s_3\geq s_2$
以上为字典序比较。

给出连接的三个字符串，输出一组可能的 $s_1, s_2, s_3$ 。

(easy) 当数据范围较小时，不妨枚举 $s_2$ 的两个端点。枚举复杂度 $O(n^2)$ ，判断复杂度 $O(n)$ ，总时间复杂度 $O(n^3)$ 可以解决。适用于任何情况。

(hard) 考虑线性做法，利用题中所给条件结合字典序性质。

字典序：

考虑字典序时，先考虑字符。显然能考虑到当前位置，则此前的位置一定全是字典序相等的。
考虑完字符再考虑位置，只有当字符不等时，考虑到的位置才有意义。

观察一：题目所给条件即，要么 $s_2$ 字典序最大，要么 $s_2$ 字典序最小。

观察二：只需要满足一个条件的情况，可以任选一个角度作为开始考虑，每个角度的考虑难度不同。此选项中，字典序最小更容易考虑。

考虑让 $s_2$ 字典序最小，则 $s_2$ 为 $a$ 即可，由于保证 $s_1, s_3$ 非空，可以找任意 $x \in [2, n - 1]， S_x = a$ ，让 $s_2 = S_{x}, s_1 = S_{1, x-1}, s_3 = S_{x+1,n}$ 。
当不存在上述情况，则 $S_{2, n-1} = b \cdots b$ ，则让 $s_1 = S_1, s_2 = S_{2, n-1}, s_3 = S_{n}$ 。

view

#include <bits/stdc++.h>
void solve() {
	std::string s; std::cin >> s;
	int n = s.length();
	for (int i = 1; i < n - 1; i++) if (s[i] == 'a') {
		std::cout << std::string(s.begin(), s.begin() + i) << ' ' << s[i] << ' ' << std::string(s.begin() + i + 1, s.end()) << '\n';
		return;
	}
	std::cout << s[0] << ' ' << std::string(s.begin() + 1, s.end() - 1) << ' ' << s[n-1] << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}