526互联

Codeforces Round 738 (Div. 2) B. Mocha and Red and Blue

发布时间 2023-09-26 17:57:17作者: zsxuan

给一个字符串，包含字符 \(B\) ， \(R\) ，\(?\) 。其中 \(?\) 可能为 \(B\) 或 \(R\) 。

规定不完美数为字符串中相同字符连续出现的次数，询问一个字符串的最少可能不完美数。

观察到 \(BR\) 或 \(RB\) 需要尽可能多，于是考虑尽可能让相邻字符不同。

容易证明从左往右扫和从右往左扫贡献一样。

  • 对于一串 \(t\) ，\(xty\) 和 \(ytx\) 贡献一样。

于是可以从左到右扫，让当前的 \(?\) 变为不同于左侧字符的字符。

问题在于若 \(?\) 在第一位如何解决。

于是可以枚举 \(s_0\) 为 \(R\) 和 \(B\) ，得到 \(s_1, s_2\) ，再计算更优的一个。

view 
#include <bits/stdc++.h>
int calc(std::string s) {
	int ret = 0;
	for (int i = 2; i < s.length(); i++) ret += s[i] != s[i-1];
	return ret;
}
void solve() {
	int n; std::cin >> n;
	std::string str; std::cin >> str;
	std::string a = "R" + str;
	std::string b = "B" + str;
	for (int i = 1; i <= n; i++) {
		if (a[i] == '?') {
			if (a[i-1] == 'R') a[i] = 'B';
			if (a[i-1] == 'B') a[i] = 'R';
		}
		if (b[i] == '?') {
			if (b[i-1] == 'R') b[i] = 'B';
			if (b[i-1] == 'B') b[i] = 'R';
		}
	}
	if (calc(a) > calc(b)) std::cout << std::string(a.begin()+1,a.end()) << "\n";
	else std::cout << std::string(b.begin()+1, b.end()) << "\n";
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}