省選博弈專題

1. Games on DAG

   發(fā)現(xiàn) \(n \le 15\)，結(jié)合一些東西容易想到枚舉子集。

   容斥一下等價(jià)于求 \(sg_1 = sg_2\) 的個(gè)數(shù)，想到按照 \(sg\) 分層圖。

   發(fā)現(xiàn)如果正著做，對(duì)于當(dāng)前層的每個(gè)點(diǎn)都需要之前的層來(lái)連邊，也就是說(shuō)要維護(hù)之前每層的點(diǎn)集，顯然不可做。

   考慮倒著做，發(fā)現(xiàn)其只需要當(dāng)前這層對(duì)每個(gè)之后層的點(diǎn)連邊即可，不區(qū)分具體層數(shù)，十分可做。

   于是我們形式化的描述一下限制，設(shè)當(dāng)前將要處理集合 \(S\)，之前已經(jīng)處理集合 \(T\)，\(K \cup T = S \land K \cap T = \varnothing\)，即 \(K\) 是這層新增節(jié)點(diǎn)。

   對(duì)于 \(u \in S\)

   \(u \in T\) 則 \(u\) 對(duì) \(K\) 內(nèi)的點(diǎn)任意連邊或不連。

   \(u \in K\) 則 \(u\) 對(duì) \(T\) 內(nèi)的點(diǎn)至少連 \(1\) 條邊。

   處理一下 \(u\) 到集合 \(X\) 的連邊數(shù)即可 \(\mathcal{O}(3 ^ n n)\)。

2. Black and White Tree

   這個(gè)是水了。

   容易發(fā)現(xiàn)先手一定能牽制后手，即先手每次選一個(gè)點(diǎn)使得起所有兒子都是葉子，如果這個(gè)點(diǎn)不只有一個(gè)兒子，則先手必勝，并且一定不劣。

   于是模擬一圈圈剝?nèi)~子即可，其本質(zhì)上是一棵樹的完美匹配，有個(gè)還算有點(diǎn)意思的結(jié)論是其等價(jià)于沒有一個(gè)點(diǎn)有奇數(shù)個(gè)兒子。

3. Candy Piles

   首先先降序排序，畫出網(wǎng)格圖可以發(fā)現(xiàn)其等價(jià)于每次消行或消列，等價(jià)于從左下出發(fā)每次向上或向右走一個(gè)。

   打個(gè)表容易發(fā)現(xiàn)其副對(duì)角線上的所有 \(sg\) 值相等，證明也不太難，簡(jiǎn)單分討即可。

   注意判一下可能會(huì)在終點(diǎn)處有相等，即可以從右轉(zhuǎn)移。

4. Decrementing

   你先發(fā)現(xiàn)一個(gè) \(1\)，如果有 \(1\) 則所有 \(gcd\) 都是 \(1\)，于是問(wèn)題就是統(tǒng)計(jì)偶數(shù)個(gè)數(shù)（因?yàn)橐Ｒ粋€(gè)）。

   一下所有奇數(shù)均不包括 \(1\)。

   首先顯然的是因?yàn)楸ＷC任意時(shí)刻 \(\gcd = 1\) 所以不可能全是偶數(shù)。

   若有奇數(shù)個(gè)偶數(shù)，此時(shí)先手只要保持即可勝利，即將一個(gè)偶數(shù)變成奇數(shù)，這樣后手時(shí)至少有兩個(gè)奇數(shù)，無(wú)論如何選都無(wú)法改變奇偶性。

   若有偶數(shù)個(gè)偶數(shù)，此時(shí)先手只有一個(gè)翻盤的機(jī)會(huì)，若有唯一一個(gè)奇數(shù)，則可以將這個(gè)減成偶數(shù)在除 \(gcd\)，然后吧決策讓給后手。

   最多遞歸 \(log\) 層，復(fù)雜度 \(n \log ^ 2 n\)

5. Rearranging

   首先先考慮青木如何做，考慮每個(gè)數(shù)最早能放到哪，發(fā)現(xiàn)任意兩個(gè)不互質(zhì)的數(shù)不會(huì)交換，于是建圖，將 \(u\) 于在它后面且不和他互質(zhì)的數(shù)連單向邊，最后就是跑最大拓?fù)湫颉?/p>

   考慮高木的操作，可以看成是對(duì)每個(gè)連通塊定向成 DAG。

   比較顯然的貪心定向就是 dfs 每次選最小的點(diǎn)。

6. 取石子游戲

   再次被背刺。

   考慮 \(dp_{l,r}\) 表示 \(l, r\) 是否先手必勝。

   發(fā)現(xiàn)沒法轉(zhuǎn)移，考慮加一維， \(L_{l,r,v}, R_{l,r,v}\) 表示在左、右加一個(gè)數(shù) \(x\) 是否先手必勝。

   發(fā)現(xiàn)狀態(tài)太大了，考慮鍵值互換，發(fā)現(xiàn)對(duì)于任意一邊其最多有一個(gè)值先手必?cái)。紤]若有兩個(gè)可以將大的那個(gè)經(jīng)過(guò)一步轉(zhuǎn)移到小的，顯然矛盾。

   然后就是逆天分討轉(zhuǎn)移，我懶得寫了，建議參考其他題解。

7、8 看鮮花