CF #738（div2）B. Mocha and Red and Blue（構造）

B. Mocha and Red and Blue

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

As their story unravels, a timeless tale is told once again…

Shirahime, a friend of Mocha’s, is keen on playing the music game Arcaea and sharing Mocha interesting puzzles to solve. This day, Shirahime comes up with a new simple puzzle and wants Mocha to solve them. However, these puzzles are too easy for Mocha to solve, so she wants you to solve them and tell her the answers. The puzzles are described as follow.

There are n squares arranged in a row, and each of them can be painted either red or blue.

Among these squares, some of them have been painted already, and the others are blank. You can decide which color to paint on each blank square.

Some pairs of adjacent squares may have the same color, which is imperfect. We define the imperfectness as the number of pairs of adjacent squares that share the same color.

For example, the imperfectness of “BRRRBBR” is 3, with “BB” occurred once and “RR” occurred twice.

Your goal is to minimize the imperfectness and print out the colors of the squares after painting.

Input

Each test contains multiple test cases.

The first line contains a single integer t (1≤t≤100) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains an integer n (1≤n≤100) — the length of the squares row.

The second line of each test case contains a string s with length n, containing characters ‘B’, ‘R’ and ‘?’. Here ‘B’ stands for a blue square, ‘R’ for a red square, and ‘?’ for a blank square.

Output

For each test case, print a line with a string only containing ‘B’ and ‘R’, the colors of the squares after painting, which imperfectness is minimized. If there are multiple solutions, print any of them.

Example

inputCopy

5

7

?R???BR

7

???R???

1

?

1

B

10

?R??RB??B?

outputCopy

BRRBRBR

BRBRBRB

B

B

BRRBRBBRBR

Note

In the first test case, if the squares are painted “BRRBRBR”, the imperfectness is 1 (since squares 2 and 3 have the same color), which is the minimum possible imperfectness.

B. 摩卡和紅藍

每次測試的時間限制1秒

每個測試的內存限制 256 兆字節

輸入標準輸入

輸出標準輸出

隨著他們的故事解開，一個永恒的故事再次被講述…

摩卡的朋友白姬熱衷于玩音樂游戲Arcaea并分享摩卡有趣的謎題來解決。這一天，白姬想出了一個新的簡單謎題，并希望摩卡能夠解決它們。然而，這些謎題對于摩卡來說太容易解決了，所以她希望你解決它們并告訴她答案。謎題描述如下。

有n個正方形排成一排，每個正方形都可以涂成紅色或藍色。

在這些方格中，有的已經畫好了，有的則是空白的。您可以決定在每個空白方塊上繪制哪種顏色。

一些相鄰的方塊可能具有相同的顏色，這是不完美的。我們將缺陷定義為共享相同顏色的相鄰方塊對的數量。

例如，“BRRRBBR”的不完美度為3，“BB”出現一次，“RR”出現兩次。

你的目標是盡量減少不完美，并在繪畫后打印出正方形的顏色。

輸入

每個測試包含多個測試用例。

第一行包含一個整數 t (1≤t≤100)——測試用例的數量。每個測試用例由兩行組成。

每個測試用例的第一行包含一個整數 n (1≤n≤100)——正方形行的長度。

每個測試用例的第二行包含一個長度為 n 的字符串 s，包含字符 ‘B’、‘R’ 和 ‘?’。這里’B’代表藍色方塊，‘R’代表紅色方塊，’?'為一個空白方塊。

輸出

對于每個測試用例，打印一行只包含 ‘B’ 和 ‘R’ 的字符串，即繪制后正方形的顏色，將缺陷最小化。如果有多個解決方案，請打印其中任何一個。

例子

輸入副本

5

7

?R???BR

7

???R???

1

?

1

乙

10

?R??RB??B?

輸出副本

BRRBRBR

BRRBRBRB

乙

乙

BRRBRBBRBR

筆記

在第一個測試案例中，如果方塊被涂成“BRRBRBR”，則缺陷為 1（因為方塊 2 和 3 具有相同的顏色），這是最小可能的缺陷。

對于最長的“ ？ ”，它優化了“ RBRB… ”或“ BRBR… ”的涂色，所以它所做的不完美僅與它兩側的顏色有關。

為每個最長的“ ？ ”周期選擇不完美的一個○ ( n ) 是可以接受的。

更優雅的是，如果“ ？ ”左邊或右邊的方塊是畫的，只需用與它不同的顏色畫“ ？ ”。這可以通過考慮奇偶性來證明達到最小缺陷。

#include typedef long long LL; using namespace std; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ int n; cin>>n; string s; cin>>s; for(int i = 1; i < n; i++){ if(s[i]=='?'){ if(s[i-1]=='B')s[i]='R'; if(s[i-1]=='R')s[i]='B'; } } for(int i = n-2; i>=0; i--){ if(s[i]=='?'){ if(s[i+1]=='B')s[i]='R'; if(s[i+1]=='R')s[i]='B'; } } if(s[0]=='?'){ for(int i = 0; i < n; i++){ if(i%2==0)cout<<"B"; else cout<<"R"; } cout<<"\n"; continue; } cout<

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。