生命不息,奋斗不止

题解 CF1559B【Mocha and Red and Blue】

2021-08-16 16:31:57


一句话题意

输入一个字符串,用 BR 代替字符串中的 ? ,输出一种解,使得字符串中连续的字符最少。

思路1:

一种较为繁琐的思路。

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

思路2:

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

用样例举例:

样例举例

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

特殊情况

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

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