526互联

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

发布时间 2023-09-05 21:25:57作者: zsxuan

有三个字符串 \(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;
}