CF1149E Election Promises 這個題目最難下手的地方在於：可以對相鄰的城市進行任意修改，這導致難以確定後繼狀態。 但是還是可以使用 $\operatorname{SG}$ 函數！ 下麵設 $f_u = \operatorname{mex}{f_v}$，這個可以直接拓撲排序求。 ...
CF1149E Election Promises
這個題目最難下手的地方在於：可以對相鄰的城市進行任意修改，這導致難以確定後繼狀態。
但是還是可以使用 \(\operatorname{SG}\) 函數！
下麵設 \(f_u = \operatorname{mex}\{f_v\}\)，這個可以直接拓撲排序求。
考慮這樣一個狀態：除點 \(u\) 外所有點的當前 \(h\) 均為 \(0\)，此時 \(\operatorname{SG}(x) = \omega_{f_u} \cdot h_u\)，其中 \(\omega_k\) 表示 \(k\) 階無窮大。
先手必敗當且僅當
\[S_k(x) = \bigoplus_{f_u=k}{h_u} = 0, \forall k \]這個想法有點神秘和抽象，感覺非常的不對！所以現在我們拋棄掉 \(\operatorname{SG}\) 函數，來看看上面的想法是否可行。
- 首先，失敗時所有 \(h\) 均為 \(0\)，滿足上述條件。
- 當對於任意 \(k\)，使得 \(S_k(x) = 0\) 時，任意操作，由於相鄰兩點 \(f\) 值互異，只能得到 \(S(x) > 0\) 的局面。
- 當存在 \(k\)，使得 \(S(x) > 0\) 時，找到最大的 \(k\) 使得 \(S_k(x) > 0\)，一定存在一點 \(u\)，使得 \(S_k(k) \oplus h_u < h_u\)，於是可以減少這個點的 \(h\)，而通過修改這個點的相鄰點，可以調整使得回到必敗態。
於是，我們證明瞭上面的結論，得到了一個 \(O(n+m)\) 的演算法，只需拓撲排序求出 \(f\) 即可。
