题解 CF1559B【Mocha and Red and Blue】
Chinshyo
2021-08-16 16:31:57
## 一句话题意
输入一个字符串，用 `B` 或 `R` 代替字符串中的 `?` ，输出一种解，使得字符串中连续的字符最少。
## 思路1：
一种较为繁琐的思路。
找到所有含 `?` 的子串，分类讨论两头的字符和子串长度进行填充。本人刚开始使用了这种方法，代码将近90行，而且要考虑很多细节。**不推荐使用这种方法**
## 思路2：
读入一个字符串，将该字符串从头到尾扫一遍，每次若发现当前字符不是 `?` ，那么从当前位置向两头扫。在扫的过程中发现 `?` 就将其替换为与前一步到达的字符不相同的。一旦找到非 `?` 的，停止循环扫描。这样就能保证重复最小。
### 用样例举例:
刚开始扫一遍扫到了黑色箭头所指的位置，然后向两头找，每次都取与上一次不一样的字符。
### 特殊情况
本题数据中存在字符串全是 `?` 的情况，这种算法找不到非 `?` 的就什么操作也不会做。因此要特殊处理，将所有都用 `B` ， `R` 交替赋值。
```cpp
if(s.find('B') == s.npos && s.find('R') == s.npos){
for(int i = 0; i < s.size(); i++) {
if(i % 2 == 0) s[i] = 'B';
else s[i] = 'R';
}
}
```
## 代码
```cpp
#include<bits/stdc++.h>
#define debug cout << "Helloworld" << endl
using namespace std;
int main() {
int T;
cin >> T;
for(int i = 1; i <= T; i++) {
int n;
cin >> n;
string s;
cin >> s;
if(s.find('B') == s.npos && s.find('R') == s.npos){//特殊情况，全都是问号
for(int i = 0; i < s.size(); i++) {
if(i % 2 == 0) s[i] = 'B';
else s[i] = 'R';
}
}
for(int j = 0; j < s.size(); j++) {
if(s[j] != '?') {
//找到问号，向两头扫
for(int k = j - 1; k >= 0; k--) {
if(s[k] != '?') break; //当前位置有字符，无需填充，直接跳过
s[k] = (s[k + 1] == 'B') ? 'R' : 'B';//当前位置填充与上一次不同的。
}
for(int k = j + 1; k < s.size(); k++) {
if(s[k] != '?') break;
s[k] = (s[k - 1] == 'B') ? 'R' : 'B';
}
}
}
cout << s << endl;
}
return 0;
}
```