给一个字符串，包含字符 \(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;
}