CF1704F Colouring Game 题解
Watware
·
·
题解
下称Alice为红方，Bob为蓝方。
很容易注意到，当双方颜色块数量不同的时候，少的那人一定会取胜，不妨设该方为红方。这是因为除非整个序列全部都是红色，这种情况下显然红方必胜，否则红蓝双方方一定能找到一种策略，使得每次操作本方颜色块数量只会减少一，显然这种策略对于双方来说都是最优的，而在这种策略下蓝方依然会比红方先行取完，红方必然获胜。
故排除掉双方颜色数量不同的情况，仅考虑颜色数量相同的情况：当场上存在红蓝两块相邻时，双方必然要优先选择这样的两块消除，否则己方的颜色块数量就会少于对方，从而落入必败的局面。这样不断的消除下去，在最后得到的局面下，红蓝双方的最优策略是每次消掉一个自己颜色的块，显然后手必胜。
综上所述，我们很自然地想到，将序列分割成若干个极大的双色相间段，那么这些段之间是互相独立的：双方无论如何都不会选择消掉两个相同颜色的块。
我们定义 SG_i 是一个长度为 i 的红蓝相间块的 SG 值，当其为 0 时，先手必败，否则先手必胜，那么它的递推式子如下：
SG_0=SG_1=0
SG_n=Mex_{i=1}^{n-1}{SG_{i-1}\oplus SG_{n-i-1}}
故对于双方颜色块数量相同的初始局面，我们只要得到了$SG$ 函数的值，将原序列划分为极大的双色相间段，并且将这些相间段的长度的 $SG$ 值异或起来，如果等于 $0$，Bob获胜，否则Alice获胜；对于双方颜色块数量不相同的初始局面，颜色块少的那方必胜。
注意到暴力求 $SG$ 是 $O(n^2)$ 的，不可接受，但这个序列有长为 $34$ 的循环节，仅在几个较小的值有例外，故我们可以较快求出 $SG$ 值~
```cpp
#include <bits/stdc++.h>
using namespace std;
const int M = 5010, N = 501000;
int t, n, ans, tp;
char s[N];
int tb[34] = {4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5,
5, 9, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7};
int tsg(int x)
{
switch (x)
{
case 0 : return 0;
case 1 : return 0;
case 15 : return 0;
case 17 : return 2;
case 18 : return 2;
case 32 : return 2;
case 35 : return 0;
case 52 : return 2;
default : return tb[x % 34];
}
}
int main()
{
scanf("%d", &t);
for (int o = 0; o < t; o++)
{
scanf("%d %s", &n, s), ans = 0, tp = 0;
for (int i = 0; i < n; i++) tp += (s[i] == 'R');
if (tp < n - tp) printf("Bob\n");
else if (tp > n - tp) printf("Alice\n");
else
{
for (int i = 0, j; i < n; i = j)
{
j = i + 1;
while (j < n && s[j] != s[j - 1]) j++;
ans ^= tsg(j - i);
}
printf(ans ? "Alice\n" : "Bob\n");
}
}
return 0;
}
```