「postOI」Colouring Game

题意

有 \(n\) 个格子排成一行，一开始每个格子上涂了蓝色或红色。

Alice 和 Bob 用这些格子做游戏。Alice 先手，两人轮流操作：

Alice 操作时，选择两个相邻的格子，其中至少要有一个红色格子，然后把这两个格子涂成白色；
Bob 操作时，选择两个相邻的格子，其中至少要有一个蓝色格子，然后把这两个格子涂成白色。

注意白色的格子也可以被选中，只要满足“至少一个红/蓝色格子”的条件。当轮到一方操作，但该方无法进行操作时，另一方获胜。

如果两人都采取最优策略，谁会获胜？

\(n \le 5 \times 10^5\)。

解析

首先贪心地想，两人会采取什么策略？不妨把游戏看成一个“轮次”的游戏，红色格子是 A 的轮次，蓝色格子是 B 的轮次。显然双方都想让自己的轮次尽可能多，对方尽可能少。由于每次操作至少选择一个己方的颜色，所以每轮会至少消耗一个己方轮次。

如果是两个己方颜色，则会消耗两个己方轮次，显然不优；
如果是己方颜色和白色，则只消耗一个己方轮次；
如果是己方颜色和对方颜色，则不仅只消耗一个己方轮次，还会减少一个对方轮次，应该是比较优的策略。

换句话说，会优先选策略三；然后会选择策略二；最后，其实容易发现除非全是红色，否则不会用到策略一，因为可以替代成两次策略二。

于是只考虑策略二三。观察策略的特点，当两人都在采取策略三时，两人的轮次差是不变的，而采取策略二时：

如果两人剩余轮次数不同，则剩余轮次多的人获胜；
如果两人剩余轮次数相同，则后手获胜，或者说，取走最后一个 RB 或 BR 的一方获胜。

于是我们可以判断：

如果两种颜色的数量不同，则较多的颜色对应的玩家必胜；
如果两种颜色相同，则取走最后一个 RB 或 BR 的一方获胜。

第二种情况如何考虑？既然只需要考虑 RB 和 BR，我们可以简化字符串，简化后就是 RBRBRBR...。只是这样一段 RB 交替的串吗？也可以几个串连起来（用 | 划分串）RBR|RBRB|BRB。注意到采取策略三时，我们不可能跨串选择格子（因为这样的两个格子是同色的），于是每个串是独立的子游戏。

“独立的子游戏”？nim游戏？SG函数？尝试用 SG 函数解题。那么整个游戏的 SG 值是每个串的 SG 值的异或和。

考虑一个串的 SG 值，由于是 RB 交替的，我们发现这个串里 R 多还是 B 多其实没有影响（比如 RBR 和 BRB 其实没有区别），这样一来，一个串就可以用其长度代替了。记 \(SG(i)\) 表示长度为 \(i\) 的串的 SG 值，考虑选择 \(i, i + 1\) 两个格子，会将串分成两个长度分别为 \(i - 1, n - i - 1\) 的两个串，而这两个串又互不影响了，转移到的状态的 SG 值就是这两个串的 SG 值异或，则

\[SG(n) = \text{mex}_{1 \le i \le n - 1}\Big\{SG(i - 1)\text{ xor }SG(n - i - 1)\Big\}
\]

这样我们可以 \(O(n^2)\) 计算 \(SG(n)\)。但这样显然不够……怎么优化？不能优化？那把表打出来看看……好像是以 \(34\) 为周期？除了前 \(68\) 个，剩下的以 \(34\) 为周期，于是可以先暴力算出 \(SG(0 \sim 1000)\)，然后按周期推 \(SG(0 \sim n)\)。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

const int MAXN = 5e5 + 10;

char col[MAXN];

int sg[MAXN];

bool tmp_is_exi[1005];

void calcSg()

{

    sg[0] = 0;

    for (int n = 1; n <= 1000; ++n)

    {

        memset(tmp_is_exi, 0, sizeof tmp_is_exi);

        for (int i = 1; i < n; ++i)

        {

            tmp_is_exi[sg[i - 1] ^ sg[n - i - 1]] = true;

        }

        for (int i = 0; ; ++i)

        {

            if (!tmp_is_exi[i])

            {

                sg[n] = i;

                break;

            }

        }

    }

    for (int i = 1001; i < MAXN; ++i)

    {

        sg[i] = sg[i - 34];

    }

}

bool solveCase()

{

    int len;

    scanf("%d%s", &len, col + 1);

    int cnt_red = 0;

    for (int i = 1; i <= len; ++i)

    {

        cnt_red += col[i] == 'R';

    }

    if (cnt_red != len - cnt_red)

    {

        return cnt_red > len - cnt_red;

    }

    int las = 1, overall_sg = 0;

    for (int i = 1; i < len; ++i)

    {

        if (col[i] == col[i + 1])

        {

            overall_sg ^= sg[i - las + 1];

            las = i + 1;

        }

    }

    overall_sg ^= sg[len - las + 1];

    return overall_sg != 0;

}

int main()

{

    calcSg();

    int cnt_cas;

    scanf("%d", &cnt_cas);

    while (cnt_cas--)

    {

        printf("%s\n", solveCase() ? "Alice" : "Bob");

    }

    return 0;

}

巴特西

「postOI」Colouring Game

题意

解析

代码

最新文章

热门文章