← 返回题目列表

Codeforces · 1669/D

D. 彩色邮票

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

给出一行 $$$n$$$ 单元格,最初都是白色的。使用图章,您可以标记任意两个相邻单元格,使一个变为红色,另一个变为蓝色。印章可以旋转,即它可以以两种方式使用:作为 $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$$$ 和 $$$\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$$$。

在使用过程中,图章必须完全适合给定的 $$$n$$$ 单元格(它不能部分位于单元格之外)。印记可以多次应用于同一单元格。每次使用图章都会重新着色图章下方的两个单元格。

例如,制作图片 $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$$$ 的可能序列可以是 $$$\texttt{WWWWW} \to \texttt{WW}\color{棕色}{\下划线{\color{红色}{\texttt{R}}\color{蓝色}{\texttt{B}}}}\texttt{W} \to \颜色{棕色}{\下划线{\颜色{蓝色}{\texttt{B}}\颜色{红色}{\texttt{R}}}}\颜色{红色}{\texttt{R}}\颜色{蓝色}{\texttt{B}}\texttt{W} \到\颜色{蓝色}{\texttt{B}}\颜色{棕色}{\下划线{\颜色{红色}{\texttt{R}}\颜色{蓝色}{\texttt{B}}}}\颜色{蓝色}{\texttt{B}}\texttt{W}$$$。这里 $$$\texttt{W}$$$、$$$\color{red}{\texttt{R}}$$$ 和 $$$\color{blue}{\texttt{B}}$$$ 分别代表白色、红色或蓝色单元格,使用印记的单元格用下划线标记。

给定最终图片,是否可以使用图章零次或多次?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 图片的长度。

每个测试用例的第二行包含一个字符串 $$$s$$$ — 您需要制作的图片。保证$$$s$$$的长度为$$$n$$$,并且$$$s$$$仅由字符$$$\texttt{W}$$$、$$$\texttt{R}$$$和$$$\texttt{B}$$$组成,分别代表白色、红色或蓝色单元格。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

输出 $$$t$$$ 行,每行包含相应测试用例的答案。作为答案,如果可以使用标记零次或多次制作图片,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW

输出 #1

YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO

注意

第一个测试用例在语句中进行了解释。

对于第二个、第三个和第四个测试用例,不可能对单个单元格进行标记,因此答案是“否”。

对于第五个测试用例,您可以按如下方式使用图章: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \颜色{棕色}{\下划线{\颜色{蓝色}{\texttt{B}}\颜色{红色}{\texttt{R}}}}\颜色{蓝色}{\texttt{B}}$$$。

对于第六个测试用例,您可以按如下方式使用图章: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \颜色{棕色}{\下划线{\颜色{红色}{\texttt{R}}\颜色{蓝色}{\texttt{B}}}}\颜色{蓝色}{\texttt{B}}$$$。

对于第七个测试用例,您根本不需要使用标记。