AC代码

https://codeforces.com/contest/1704/submission/181166130

题意:

爱丽丝和鲍勃正在玩游戏。一行有n个单元格。最初，每个单元格都是红色或蓝色。爱丽丝先走。

每个回合，Alice选择两个相邻的单元格，其中至少包含一个红色单元格，并将这两个单元格涂成白色。

然后，Bob选择至少包含一个蓝色单元格的两个相邻单元格，并将这两个单元格涂成白色。不能移动的玩家会输。

如果Alice和Bob都发挥最佳，则找到赢家。

请注意，所选单元格可以是白色的，只要其他单元格满足约束条件。

题解：

博弈 + ICG + SG函数

“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件：

1、有两名选手交替对游戏进行移动(move)，每次一步，

选手可以在合法移动集合中任选一种进行移动；

2、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，

不取决于轮到哪名选手操作；

3、如果轮到某名选手移动，且这个局面的合法的移动集合为空，则这名选手负。

两边的策略显然是先抢对方的再碰自己的。如果取完BR或者RB，只剩单个R，B，

这时如果 R和B 数量不相等,数量大者胜。

如果取完BR或者RB，只剩单个R，B，这时如果 R和B 数量相等，

则变成ICG，可以引入 SG 函数来处理。这是本题的关键。

这时先取完BR或者RB者即是赢，因为剩下的单个R，B数量相等。

把形如 RBRBRB 或者RBRBR  的子区间提取出来，

那么当前局面的 SG 值就是它们的SG 值异或和。

注意RBRBR  的SG 值，与题目原来的定义不同，我们不考虑R和B 数量是否相等，

只考虑能取得BR或者RB的数量，故与是否为爱丽丝无关。

对于单个子区间RBRBR，RBRBRB 或者BRBRBR，先手输赢只和它的长度有关。

暴力打表发现，从53开始，有一个长度34的周期。