CF1149E Election Promises

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}\) 函数,来看看上面的想法是否可行。

  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\) 即可。

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