← 返回题目列表

Codeforces · 1559/B

B. 摩卡咖啡和红蓝

中文机器翻译题面 查看原题

随着他们的故事被揭开,一个永恒的故事再次被讲述......

Shirahime 是 Mocha 的朋友,热衷于玩音乐游戏 Arcaea 并分享 Mocha 需要解决的有趣谜题。这一天,白姬想出了一个新的简单谜题,并希望摩卡能够解决它们。然而,这些谜题对摩卡来说太容易解决,所以她希望你解决它们并告诉她答案。谜题描述如下。

有 $$$n$$$ 个方块排成一排,每个方块都可以涂成红色或蓝色。

这些方格中,有的已经被绘制,有的则是空白。您可以决定在每个空白方块上绘制哪种颜色。

一些相邻的方块对可能具有相同的颜色,这是不完美的。我们将缺陷定义为共享相同颜色的相邻方块对的数量。

例如,“BRRRBBR”的不完美性是$$$3$$$,其中“BB”出现了一次,“RR”出现了两次。

您的目标是最大程度地减少缺陷并在绘画后打印出正方形的颜色。

输入

每个测试包含多个测试用例。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。每个测试用例由两行组成。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 100$$$) — 方块行的长度。

每个测试用例的第二行包含一个字符串$$$s$$$,长度为$$$n$$$,包含字符“B”、“R”和“?”。这里“B”代表蓝色方块,“R”代表红色方块,“?”对于一个空白的正方形。

输出

对于每个测试用例,打印一行,其中包含仅包含“B”和“R”的字符串,即绘制后方块的颜色,从而最大限度地减少缺陷。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?

输出 #1

BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR

注意

在第一个测试用例中,如果方块被涂成“BRRBRBR”,则缺陷为 $$$1$$$ (因为方块 $$$2$$$ 和 $$$3$$$ 具有相同的颜色),这是可能的最小缺陷。