AC代碼

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

題意:

愛麗絲和鮑勃正在玩游戲。一行有n個(gè)單元格。最初，每個(gè)單元格都是紅色或藍(lán)色。愛麗絲先走。

每個(gè)回合，Alice選擇兩個(gè)相鄰的單元格，其中至少包含一個(gè)紅色單元格，并將這兩個(gè)單元格涂成白色。

然后，Bob選擇至少包含一個(gè)藍(lán)色單元格的兩個(gè)相鄰單元格，并將這兩個(gè)單元格涂成白色。不能移動(dòng)的玩家會(huì)輸。

如果Alice和Bob都發(fā)揮最佳，則找到贏家。

請(qǐng)注意，所選單元格可以是白色的，只要其他單元格滿足約束條件。

題解：

博弈 + ICG + SG函數(shù)

“Impartial Combinatorial Games”（以下簡(jiǎn)稱ICG）。滿足以下條件：

1、有兩名選手交替對(duì)游戲進(jìn)行移動(dòng)(move)，每次一步，

選手可以在合法移動(dòng)集合中任選一種進(jìn)行移動(dòng)；

2、對(duì)于游戲的任何一種可能的局面，合法的移動(dòng)集合只取決于這個(gè)局面本身，

不取決于輪到哪名選手操作；

3、如果輪到某名選手移動(dòng)，且這個(gè)局面的合法的移動(dòng)集合為空，則這名選手負(fù)。

?

兩邊的策略顯然是先搶對(duì)方的再碰自己的。如果取完BR或者RB，只剩單個(gè)R，B，

這時(shí)如果 R和B 數(shù)量不相等,數(shù)量大者勝。

如果取完BR或者RB，只剩單個(gè)R，B，這時(shí)如果 R和B 數(shù)量相等，

則變成ICG，可以引入 SG 函數(shù)來處理。這是本題的關(guān)鍵。

這時(shí)先取完BR或者RB者即是贏，因?yàn)槭Ｏ碌膯蝹€(gè)R，B數(shù)量相等。

把形如 RBRBRB 或者RBRBR? 的子區(qū)間提取出來，

那么當(dāng)前局面的 SG 值就是它們的SG 值異或和。

注意RBRBR? 的SG 值，與題目原來的定義不同，我們不考慮R和B 數(shù)量是否相等，

只考慮能取得BR或者RB的數(shù)量，故與是否為愛麗絲無關(guān)。

對(duì)于單個(gè)子區(qū)間RBRBR，RBRBRB 或者BRBRBR，先手輸贏只和它的長(zhǎng)度有關(guān)。

暴力打表發(fā)現(xiàn)，從53開始，有一個(gè)長(zhǎng)度34的周期。