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\) 阶无穷大。

先手必败当且仅当

这个想法有点神秘和抽象，感觉非常的不对！所以现在我们抛弃掉 \(\operatorname{SG}\) 函数，来看看上面的想法是否可行。

1. 首先，失败时所有 \(h\) 均为 \(0\)，满足上述条件。
2. 当对于任意 \(k\)，使得 \(S_k(x) = 0\) 时，任意操作，由于相邻两点 \(f\) 值互异，只能得到 \(S(x) > 0\) 的局面。
3. 当存在 \(k\)，使得 \(S(x) > 0\) 时，找到最大的 \(k\) 使得 \(S_k(x) > 0\)，一定存在一点 \(u\)，使得 \(S_k(k) \oplus h_u < h_u\)，于是可以减少这个点的 \(h\)，而通过修改这个点的相邻点，可以调整使得回到必败态。

于是，我们证明了上面的结论，得到了一个 \(O(n+m)\) 的算法，只需拓扑排序求出 \(f\) 即可。

热门相关：无量真仙   家庭重塑   第一神算：纨绔大小姐   明月照大江   大神你人设崩了