F. Colouring Game（博弈论/sg函数）

题目 参考

题意

给定一个RB字符串序列。 Alice和Bob轮流操作， Alice可以选择两个相邻的、至少有一个R字符的字符子串，并把它们染成白色； Bob可以选择两个相邻的、至少有一个B字符的字符子串，并把它们染成白色。

最终哪方无路可走，则输了。 Alice和Bob都按最优思路去走。问最终谁是赢家。

思路

经典的博弈题，sg函数不太熟，感兴趣可以看看这篇介绍 sg函数介绍

直接套着公式就可以求解这道题了。 我们用W表示被染过的、白色的点。

对于R数量大于B数量的场景，Alice必赢。假如Bob去染RB，BR这两种状态的，则Alice也去染这种状态的；假如Bob去染WB，BW这两种状态的，则Alice也去染RW，WR这两种状态的。一直耗下去，最终由于R比B多出至少一个数量，Bob无路可走。

对于R数量小于B数量的场景，我们也可以做类似分析，此时Bob必胜。

对于R和B数量一致的场景，我们可以应用SG函数。 我们把原字符串划分为若干个、相邻字符不同的子字符串。 比如字符串RBRRBBBR，我们可以划分为RBR,RB,B,BR这几个子字符串。 则答案即为 S G ( R B R ) ⊕ S G ( R B ) ⊕ S G ( B ) ⊕ S G ( B R ) SG(RBR)\oplus SG(RB)\oplus SG(B)\oplus SG(BR) SG(RBR)⊕SG(RB)⊕SG(B)⊕SG(BR)

至于不同长度的、相邻字符不同的字符串，它们的SG怎么求，就可以套SG公式了

sg(i)=mex(sg(i)^sg(i-j-2)),0