← 返回题目列表

Codeforces · 2029/F

F. 回文无处不在

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

给定一个循环,其中包含 $$$n$$$ 顶点,编号从 $$$0$$$ 到 $$$n-1$$$。对于每个 $$$0\le i\le n-1$$$,顶点 $$$i$$$ 和顶点 $$$((i+1)\bmod n)$$$ 之间有一条无向边,颜色为 $$$c_i$$$($$$c_i=\texttt{R}$$$ 或 $$$\texttt{B}$$$)。

确定以下条件对于每对顶点 $$$(i,j)$$$ ($$$0\le i<j\le n-1$$$) 是否成立:

- 顶点 $$$i$$$ 和顶点 $$$j$$$ 之间存在回文路由。请注意,路线可能并不简单。形式上,必须存在一个序列 $$$p=[p_0,p_1,p_2,\ldots,p_m]$$$ 使得: $$$p_0=i$$$, $$$p_m=j$$$; 对于每个 $$$0\leq x\le m-1$$$,$$$p_{x+1}=(p_x+1)\bmod n$$$ 或 $$$p_{x+1}=(p_{x}-1)\bmod n$$$; 对于每个满足$$$x+y=m-1$$$的$$$0\le x\le y\le m-1$$$,$$$p_x$$$和$$$p_{x+1}$$$之间的边与$$$p_y$$$和$$$p_{y+1}$$$之间的边具有相同的颜色。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3\leq n\leq10^6$$$) — 循环中的顶点数。

第二行包含长度为 $$$n$$$ 的字符串 $$$c$$$($$$c_i=\texttt{R}$$$ 或 $$$\texttt{B}$$$) - 每条边的颜色。

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

输出

对于每个测试用例,如果任意一对节点之间存在回文路由,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

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

示例

输入 #1

7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB

输出 #1

YES
YES
YES
NO
NO
YES
NO

注意

在第一个测试用例中,很容易证明任意两个顶点之间存在回文路线。

在第二个测试用例中,对于任意两个顶点,都存在一条只有红色边缘的回文路线。

在第三个测试用例中,循环如下: $$$0\color{红色}{\overset{\texttt{R}}{\longleftrightarrow}}1\color{蓝色}{\overset{\texttt{B}}{\longleftrightarrow}}2\color{蓝色}{\overset{\textt t{B}}{\longleftrightarrow}}3\color{红色}{\overset{\texttt{R}}{\longleftrightarrow}}4\color{蓝色}{\overset{\texttt{B}}{\longleftrightarrow}}0$$$。以$$$(i,j)=(0,3)$$$为例,则$$$0\color{红色}{\overset{\texttt{R}}{\longrightarrow}}1\color{蓝色}{\overset{\texttt{B}}{\longrightarrow}}2\color{蓝色}{\overset{\texttt{B}}{\longrightarrow}}3\color{red}{\overset{\tex ttt{R}}{\longrightarrow}}4\color{蓝色}{\overset{\texttt{B}}{\longrightarrow}}0\color{蓝色}{\overset{\texttt{B}}{\longrightarrow}}4\color{红色}{\overset{\texttt{R}}{\longrightarrow}}3$$$是一条回文路线。因此,条件适用于 $$$(i,j)=(0,3)$$$。

在第四个测试用例中,当$$$(i,j)=(0,2)$$$时,不存在回文路由。