ACM-ICPC-OJ训练营

问题 C: 翻硬币

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 37
[提交][状态][讨论版][命题人:]

题目描述

桌子上有 n 枚硬币围成一个圆圈，每枚硬币要么朝上，要么朝下。小贺和小刘轮流玩下面的游戏，小贺先玩。

在每次操作中，玩家选择一枚正面朝上的硬币，取出硬币并翻转与其相邻的两枚硬币。如果(操作前)只剩下两枚硬币，则取出一枚，另一枚不翻转(因为会翻转两次)。如果(操作前)只剩下一枚硬币，则不会翻转任何硬币。如果(操作前)没有正面朝上的硬币，玩家就输了。

如果两人都以最佳方式下棋，谁会赢呢？可以证明，游戏将在有限次的操作中结束，其中一人将获胜。

输入描述

每个测试包含多个测试用例。第一行包含测试用例的数量 ( 1<= t<= 100)。测试用例说明如下。

每个测试用例的第一行只包含一个正整数 ( 1 <= n <= 100 )，代表硬币的数量。

每个测试用例的第二行后面都有一个长度为 n 的字符串 s，其中只包含 "U "和 "D"，代表每个硬币朝上或朝下。

输出描述

对于每个测试用例，如果小贺将赢得游戏，则打印 "YES"，否则打印 "NO"。

样例输入

3
5
UUDUD
5
UDDUD
2
UU

样例输出

YES
NO
NO

提示

在第一个测试案例中，游戏过程可能如下。

- 小贺选择第一枚硬币，s 变成 "DDUU"。

- 小刘选择最后一枚硬币，s 变成 "UDD"。

- 小贺选择第一枚硬币，s 变成 "UU"。

- 小刘选择第一枚硬币， s 变成 "U"。

- 小贺选择了唯一一枚硬币，s变成了 "空"。

- 小刘现在不能选择任何一枚硬币，他输掉了游戏。

可以证明，如果两人都以最优方式下棋，小刘总是会输。

[提交][状态]