有 \(n\) 个格子排成一行,一开始每个格子上涂了蓝色或红色。
Alice 和 Bob 用这些格子做游戏。Alice 先手,两人轮流操作:
注意白色的格子也可以被选中,只要满足“至少一个红/蓝色格子”的条件。当轮到一方操作,但该方无法进行操作时,另一方获胜。
如果两人都采取最优策略,谁会获胜?
\(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 值异或,则
这样我们可以 \(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; }