← 返回题目列表

Codeforces · 1972/B

B. 硬币游戏

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

桌子上有 $$$n$$$ 硬币,围成一个圆圈,每个硬币要么朝上,要么朝下。 Alice 和 Bob 轮流玩下面的游戏,Alice 先玩。

在每次操作中,玩家选择一枚面朝上的硬币,取出该硬币,然后翻转与其相邻的两枚硬币。如果(在操作之前)只剩下两枚硬币,那么一枚将被移除,而另一枚将不会被翻转(因为它会被翻转两次)。如果(操作前)只剩下一枚硬币,则不会翻转任何硬币。如果(在操作之前)没有面朝上的硬币,玩家就输了。

如果双方都发挥最佳,决定谁将赢得比赛。可以证明,游戏会在有限次数的操作中结束,其中一次获胜。

输入

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

每个测试用例的第一行只包含一个正整数$$$n$$$ ($$$1 \leq n \leq 100$$$),代表硬币的数量。

每个测试用例的第二行后面跟着一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含“U”和“D”,表示每个硬币朝上或朝下。

输出

对于每个测试用例,如果 Alice 将赢得游戏,则打印“YES”,否则打印“NO”。

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

示例

输入 #1

3
5
UUDUD
5
UDDUD
2
UU

输出 #1

YES
NO
NO

注意

在第一个测试用例中,游戏可能会如下进行。

- Alice 选择第一个硬币,$$$s$$$ 变成“DDUU”。
- Bob 选择最后一个硬币,$$$s$$$ 变成“UDD”。
- Alice 选择第一个硬币,$$$s$$$ 变成“UU”。
- Bob 选择第一个硬币,$$$s$$$ 变成“U”。
- Alice 选择唯一的硬币,$$$s$$$ 变空。
- 鲍勃现在无法选择任何硬币,他输了游戏。

可以证明,如果他们都发挥最佳,鲍勃总是会输。