朝田诗乃 的博客

朝田诗乃 的博客

NOIP热身赛第二套题解

posted on 2018-10-22 16:16:47 | under 未分类 |

T1

可以发现每次推动球时,是将每个球的位置 $-1$ ,然后把最左边的球放到 $P-1$ 处。

记个 $-1$ 次数,再用set维护就好了。

T2

$f(i, a, b, c)$ 表示考虑前 $i$ 个,换进了 $a$ 个,换出了 $b$ 个,当前的位置是 $c(0/1/2)$ 的答案。其中 $0$ 是在选择的区间之前, $1$ 是在选择的区间之中, $2$ 是之后。每次 $O(1)$ 讨论一下当前位置的数的情况。

T3

方法一

考虑一个叶子节点到根的路径上的点的颜色,那么一定是前面一段的颜色与叶子节点的颜色相同,然后剩下一段的颜色均为灰色。那么每次修改就先减去原来路径上的颜色然后再加上修改后路径上的颜色,每个颜色的个数可以直接二分求出两种颜色的相交处即可。

一个节点为黑色或白色当且仅当以它为根的子树中的所有叶子节点颜色相同。那么可以求出一个DFS序,然后直接用线段树来维护,叶子节点颜色。

总复杂度: $O(n*logn^2)$ 。

方法二

求两种颜色的相交处,可以是求最近的一个灰色的节点,那么一定是这个叶子节点与另一种颜色节点的深度最深的LCA。这个必然是和它在DFS序最相近的两个点,可以用set维护每种颜色的叶子节点的DFS序值,直接查询然后倍增求LCA即可。

总复杂度: $O(n*logn)$ 。