ToB企服应用市场:ToB评测及商务社交产业平台

标题: CF1149E Election Promises [打印本页]

作者: 老婆出轨 时间: 2023-3-6 14:24
标题: 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}\) 函数，来看看上面的想法是否可行。

首先，失败时所有 \(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\) 即可。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)