CF1704F Colouring Game

Alice 和 Bob 正在玩一个游戏。有 $n$ 个格子排成一行。最初每个格子要么是红色，要么是蓝色。Alice 先手。 每一回合，Alice 选择两个相邻的格子，只要这两个格子中至少有一个是红色的，就可以将这两个格子涂成白色。然后，Bob 选择两个相邻的格子，只要这两个格子中至少有一个是蓝色的，就可以将这两个格子涂成白色。无法进行操作的一方判负。 如果 Alice 和 Bob 都采取最优策略，求谁会获胜。 注意，被选择的格子中可以有白色，只要另一个格子满足条件即可。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 对于每个测试用例，第一行包含一个整数 $n$（$2 \leq n \leq 5 \cdot 10^5$），表示格子的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，表示格子的初始状态。第 $i$ 个格子是红色当且仅当 $s_i = $ R，是蓝色当且仅当 $s_i = $ B。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一行，表示获胜者的名字。

在样例说明中，格子的编号从左到右递增。 在第一个测试用例中，对于 Alice，她有两种选择：涂第一个和第二个格子，或者涂第二个和第三个格子。无论 Alice 做出哪种选择，Alice 操作后都会剩下一个蓝色格子。Bob 只需将蓝色格子及其相邻格子涂白，此时所有格子都变成白色，Alice 无法再操作。因此 Bob 获胜。 在第二个测试用例中，无论 Alice 如何选择，Bob 都可以在两步内将第四和第五个格子涂白。 在第三个测试用例中，Alice 首先涂第三和第四个格子。无论 Bob 涂第一和第二个格子还是第五和第六个格子，Alice 都可以涂剩下的两个格子。 在第四个测试用例中，Alice 首先涂第二和第三个格子。如果 Bob 涂第五和第六个格子或第四和第五个格子，Alice 就涂第七和第八个格子。如果 Bob 涂第七和第八个格子，Alice 就涂第五和第六个格子。 在第五个测试用例中，Alice 首先选择中间的两个格子，然后 Bob 显然只有两种选择，无论他选择哪一种，Alice 都可以选择另一种并获胜。 在第八个测试用例中，无论 Alice 如何选择，Bob 都可以选择另外两个对称的格子。 由 ChatGPT 4.1 翻译