0%

CF1286F 题解 - Harry the Potter

题目链接题目翻译

考虑二操作(看成无向边)不会有环,否则可以转化成等数量的一操作

一操作也不会有和它连通的二操作,原因同上

那么每有一个连通块只用二操作就可以达成,我们的总操作次数就可以少一次,我们要尽量多地使用二操作

那么问题就来了,如何判断一个集合 $s$ 可以被二操作达成呢

如果把二操作改成两边都减 $x$,那么就等价于深度为奇数的点的权值和减深度为偶数的点权值和为零

那么显然是一边为 $x$ 一边为 $x+1$,所以只要这个权值差为 $|s|-1,|s|-3,…,-|s|+1$ 就可以修正得回来

注意树的形态是我们决定的,所以只要深度为奇偶的点集都不为空就可以了。总的来说是

显然奇偶性只和 $s$ 有关,我们关注中间那个条件就可以了

显然写个折半搜索即可,对于 $s$ 的复杂度是 $\sqrt 2^{|s|}$,于是就做到了 $O((\sqrt 2+1)^n)$ 的奇怪复杂度

考虑对可行的 $s$,令 $F_s=1$,然后做独立集子集卷积,如果 $F^p$ 有任何一位不为 0 那么就意味着可以分出 $p$ 个集合。二分 $p$。复杂度 $O(2^nn^2\log n)$

但是其实这题是可以 $3^n$ 草过去的,你可能会很惊讶,$n=20$ 怎么可能被 $3^n$ 草,但事实就是这样,小编也很惊讶