一句话题意

输入一个字符串，用 B 或 R 代替字符串中的 ? ，输出一种解，使得字符串中连续的字符最少。

思路1：

一种较为繁琐的思路。

找到所有含 ? 的子串，分类讨论两头的字符和子串长度进行填充。本人刚开始使用了这种方法，代码将近90行，而且要考虑很多细节。不推荐使用这种方法

思路2：

读入一个字符串，将该字符串从头到尾扫一遍，每次若发现当前字符不是 ? ，那么从当前位置向两头扫。在扫的过程中发现 ? 就将其替换为与前一步到达的字符不相同的。一旦找到非 ? 的，停止循环扫描。这样就能保证重复最小。

用样例举例:

刚开始扫一遍扫到了黑色箭头所指的位置，然后向两头找，每次都取与上一次不一样的字符。

特殊情况

本题数据中存在字符串全是 ? 的情况，这种算法找不到非 ? 的就什么操作也不会做。因此要特殊处理，将所有都用 B ， R 交替赋值。

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';
    }
}

代码

#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;
}