2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 16:45] nikkukun add E |
2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260 [2020/08/14 16:59] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 108: | 行 108: | ||
| **转移 2**：准备转移到儿子节点 $v$ 上：这里不能像上面一样 $O(\textit{siz}_u)$ 更新，否则总的更新复杂度 $O(\sum _{u=1}^n \textit{siz}_u^2)$ 是不对的。考虑删掉 $\mathrm{SG}(v)$ 对 $\mathrm{SG}(u)$ 的影响，发现只有删掉后 $\mathrm{SG}(v)$ 的出现次数为 $0$，且 $\mathrm{SG}(v) < \mathrm{SG}(u)$ 时，$u$ 的 SG 函数值才会变成 $\mathrm{SG}(v)$，否则不变。这样做就是 $O(1)$ 的。 | **转移 2**：准备转移到儿子节点 $v$ 上：这里不能像上面一样 $O(\textit{siz}_u)$ 更新，否则总的更新复杂度 $O(\sum _{u=1}^n \textit{siz}_u^2)$ 是不对的。考虑删掉 $\mathrm{SG}(v)$ 对 $\mathrm{SG}(u)$ 的影响，发现只有删掉后 $\mathrm{SG}(v)$ 的出现次数为 $0$，且 $\mathrm{SG}(v) < \mathrm{SG}(u)$ 时，$u$ 的 SG 函数值才会变成 $\mathrm{SG}(v)$，否则不变。这样做就是 $O(1)$ 的。 | ||
| - | 综上，计算出所有点为起点时对应的 SG 函数值是 $O(n)$ 的。为了输出方案，还需要知道每个点为根时相邻节点是 SG 函数值。可以归纳地证明，为了让 SG 函数为 $i$，至少需要 $2^i$ 个节点，因此所有节点的 SG 函数值不超过 $\log_2 n \leq 17$，额外记录一下这 $O(\log n)$ 个信息即可。 | + | 综上，计算出所有点为起点时对应的 SG 函数值是 $O(n)$ 的。为了输出方案，还需要知道每个点为根时相邻节点的 SG 函数值。可以归纳地证明，为了让 SG 函数为 $i$，至少需要 $2^i$ 个节点，因此所有节点的 SG 函数值不超过 $\log_2 n \leq 17$，额外记录一下这 $O(\log n)$ 个信息即可。 |
| 总时间复杂度 $O(n \log n)$。 | 总时间复杂度 $O(n \log n)$。 | ||
2020-2021/teams/i_dont_know_png/nikkukun/yukicoder-contest-260.1597394713.txt.gz · 最后更改: 2020/08/14 16:45 由 nikkukun
