B. Mocha and Red and Blue（贪心）

曾经终败给现在 2022-09-05 13:57 93阅读 0赞

（1）如果第一个位置是问号，分别把当做是R/B，往下模拟  
（2）如果第一个位置是B，那就直接往下模拟  
（3）如果第一个位置是R，还是直接往下模拟  
第二个和第三个只需要一个字符串组就可以完成，但为了copy代码，以及适应下面的求和取最小的计算，需要变成两个字符串组。

// Problem: B. Mocha and Red and Blue
    // Contest: Codeforces - Codeforces Round #738 (Div. 2)
    // URL: https://codeforces.com/contest/1559/problem/B
    // Memory Limit: 256 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int inf=0x3f3f3f3f;
    const int N=1e2+100;
    int n;
    char a[N],b[N],c[N];
    
    void solve()
    { 
    	cin >> n;
    
    	rep(i,1,n) cin >> a[i];
    	
    	if(a[1]=='?')
    	{ 
    		b[1] = 'B';
    		c[1] = 'R';
    		rep(i,2,n)
    		{ 
    			if(a[i]!='?') 
    			{ 
    				b[i] = a[i];
    				c[i] = a[i];
    				continue;
    			}
    			if(b[i-1]=='B') b[i]='R';
    			if(b[i-1]=='R') b[i]='B';
    			if(c[i-1]=='B') c[i]='R';
    			if(c[i-1]=='R') c[i]='B';
    		}
    	}
    	else if(a[1]=='B')
    	{ 
    		b[1] = 'B';
    		c[1] = 'B';
    		rep(i,2,n)
    		{ 
    			if(a[i]!='?') 
    			{ 
    				b[i] = a[i];
    				c[i] = a[i];
    				continue;
    			}
    			if(b[i-1]=='B') b[i]='R';
    			if(b[i-1]=='R') b[i]='B';
    			if(c[i-1]=='B') c[i]='R';
    			if(c[i-1]=='R') c[i]='B';
    		}
    	}
    	else{ 
    		b[1] = 'R';
    		c[1] = 'R';
    		rep(i,2,n)
    		{ 
    			if(a[i]!='?') 
    			{ 
    				b[i] = a[i];
    				c[i] = a[i];
    				continue;
    			}
    			if(b[i-1]=='B') b[i]='R';
    			if(b[i-1]=='R') b[i]='B';
    			if(c[i-1]=='B') c[i]='R';
    			if(c[i-1]=='R') c[i]='B';
    		}
    	}
    	
    	
    	int a1=0, a2=0;
    	rep(i,1,n-1)
    	{ 
    		if(b[i]==b[i+1]) a1++;
    		if(c[i]==c[i+1]) a2++;
    	}
    	if(a1>=a2) rep(i,1,n) cout << c[i];
    	else rep(i,1,n) cout << b[i];
    	cout << endl; 
    }
    
    int main()
    { 
    
    	ios::sync_with_stdio(false);cin.tie(0);
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }