← 返回题目列表

Codeforces · 1704/F

F. 着色游戏

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

Alice 和 Bob 正在玩游戏。一行中有 $$$n$$$ 个单元格。最初,每个单元格要么是红色,要么是蓝色。爱丽丝先走。

在每一回合中,Alice 选择两个包含至少一个红色单元格的相邻单元格,并将这两个单元格涂成白色。然后,Bob 选择两个包含至少一个蓝色单元格的相邻单元格,并将这两个单元格涂成白色。无法采取行动的玩家就输了。

如果 Alice 和 Bob 都表现最佳,则找到获胜者。

请注意,只要其他单元格满足约束条件,所选单元格就可以是白色。

输入

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

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — 单元格数量。

第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$ — 单元格的初始状态。如果 $$$s_i = $$$ R,则第 $$$i$$$ 个单元格为红色;如果 $$$s_i = $$$ B,则为蓝色。

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

输出

对于每个测试用例,在单独的行中输出获胜者的姓名。

示例

输入 #1

8
3
BRB
5
RRBBB
6
RBRBRB
8
BBRRBRRB
6
BRRBRB
12
RBRBRBRBRRBB
12
RBRBRBRBBBRR
4
RBBR

输出 #1

Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob

注意

在注释中,单元格编号从左到右增加。

在 Alice 的第一个测试用例中,她有两个选择:绘制第一个和第二个单元格,或者绘制第二个和第三个单元格。无论Alice做出什么选择,Alice移动后都会有一个蓝色单元格。鲍勃只需要把蓝色的格子和它的邻居涂上颜色,然后每个格子都会变成白色,爱丽丝就不能移动了。所以鲍勃是赢家。

在第二个测试用例中,无论 Alice 选择什么,Bob 都可以选择以 $$$2$$$ 轮流绘制第四个和第五个单元格。

首先在第三个测试用例中,Alice 绘制了第三个和第四个单元格。 Bob 绘制第一个和第二个单元格还是第五个和第六个单元格并不重要,因为 Alice 可以绘制其他两个单元格。

首先,在第四个测试用例中,Alice 绘制了第二个和第三个单元格。如果鲍勃绘制第五和第六个单元格或第四和第五个单元格,那么爱丽丝绘制第七和第八个单元格。如果鲍勃绘制第七个和第八个单元格,那么爱丽丝绘制第五个和第六个单元格。

在第五个中,Alice首先选择了中间的两个单元格,那么Bob显然只有两个选择,无论他选择哪个变体,Alice都可以选择另一个并获胜。

在第八个中,无论Alice选择什么,Bob都可以选择另外两个对称的单元格。