【题解】CF1972B Coin Games

Solution

一道博弈题，从操作的性质方面入手。

对于依次操作的位置，受到影响的就是其两边的硬币，无非分为以下几种情况：

• 两边都是 U，删去元素后两边都变成 D，U 的个数少了 $3$个（包括操作的那一个）。
• 一边是 U，一边是 D，操作后 U 的个数少了 $1$ 个。
• 两边都是 D，操作后 U 的个数增加了 $1$ 个。

不难发现无论怎么操作，U 的个数的奇偶性始终不会改变。对于最后一种操作，如果 U 的个数便为 $0$，那么游戏结束。

我们可以统计出初始状态 U 的个数，如果 U 为奇数，则 Alice 获胜，否则 Bob 获胜。

AC Code

1
2
3
4
5
6
7
8

void solve()
{
    int res = 0;
    cin >> n >> s + 1;
    for (int i = 1; i <= n; i ++)
        res += s[i] == 'U';
    cout <<( (res & 1) ? "YES\n" : "NO\n");
}