UOJ Logo EntropyIncreaser的博客

博客

BJ United Round #4 (Mirror of Haidian 2019)题解

2019-09-21 12:46:51 By EntropyIncreaser

石子移动

考虑将操作过程倒过来,最后值域在 $[l, r]$ 内的在上一步应该也是一个区间,便可得出最初的区间限制。

时间复杂度 $\Theta(n + q)$。

分数排序

$n$ 阶 Farey 数列可以直接在 stern-brocot 树上遍历:初始设置 $\frac ab = \frac 01, \frac xy = \frac 11$。那么 $(\frac ab, \frac xy)$ 这一节点的左子和右子分别为 $(\frac ab, \frac {a+x}{b+y}), (\frac{a+x}{b+y}, \frac xy)$。不难证明任何出现的一个分数的分子分母都是互质的,且这样可以遍历所有分数。

考虑如何在这个树上找到一个分数,虽然一个节点到根的距离可以是 $\Theta(n)$ 的(例如 $\frac 1n$),但是假设我们走到 $(\frac ab, \frac{a+x}{b+y})$ 叫做 $L$ 操作,否则叫做 $R$ 操作,那么一个节点对应找到它的操作序列的连续段数应该是 $\mathcal O(\log n)$ 的,因为一次 $LR$ 会使得分母倍增。我们可以倍增看操作序列一共下一组 $L$ 或者 $R$ 有多长,因此我们会进行 $\mathcal O(\log^2 n)$ 次 check 操作。

考虑如何计算一次 check: $$ \begin{eqnarray} & &\sum_{x\le n} \sum_{y\le n} \left[\frac xy \le \frac ab\right] [\gcd(x, y) = 1]\\ &= & \sum_{x\le n} \sum_{y\le n} \left[\frac xy \le \frac ab\right] \sum_{d | (x, y)} \mu(d)\\ &= & \sum_d \mu(d) \sum_{y\le \frac nd} \sum_{x\le \frac nd} \left[x \le \frac {ay}b\right] \\ &= & \sum_d \mu(d) \sum_{y = 1}^{\left\lfloor\frac nd\right\rfloor} \min\left( \left\lfloor \frac nd \right\rfloor, \left\lfloor \frac{ay}b \right\rfloor \right) \end{eqnarray} $$ 对 $\left\lfloor\frac nd\right\rfloor$ 除法分块,我们需要 $\mu(d)$ 在这些位置的前缀和,而 $\sum_{y = 1}^{\left\lfloor\frac nd\right\rfloor} \min\left( \left\lfloor \frac nd \right\rfloor, \left\lfloor \frac{ay}b \right\rfloor \right)$,这个式子在一个前缀中取得右边是较小值,这部分我们可以通过类欧几里得算法在 $\Theta(\log b)$ 时间内计算。因此我们一次 check 的时间消耗为 $\Theta(\sqrt n \log n)$。注意前缀和的处理可以使用 $\Theta(n^{\frac 23})$,但是在本题限制下 $\Theta(n)$ 也是 ok 的。

综上所述,时间复杂度为 $\Theta(n^{\frac 23}) + \Theta(\sqrt n \log^3 n)$。

彼岸蔷薇

newbiedmy 这家伙会乱搞,很有毒!

关于背景

那段歌词摘自遗忘山丘

算法一

考虑枚举所有路径,对于每个情况按照定义求出最大路径数。

显然最大路径数可以通过树形 dp 进行计算。$f(u)$ 表示考虑所有两端点均在 $u$ 的子树的路径,此时的最大答案。此时分成两类转移情况讨论,要么选择的路径均不经过 $u$,那么这一情况的最优解即 $u$ 的所有直系孩子的 $f$ 之和。否则枚举选取哪个路径,这一情况的贡献是 $1$ 加上与这条路径相邻的所有节点的 $f$ 之和。

时间复杂度 $\Theta(mn^3)$,预计得分 $32\%$。

算法二

考虑优化 dp 的效率,我们记 $g(u)$ 为 $f(u)$ 减去其所有直系孩子的 $f$,则不难发现 $g(u)$ 对于路径情况的转移就是所选路径上 $g$ 的和再加 $1$。通过一个树状数组即可维护。

时间复杂度 $\Theta((n + m\log n)n^2)$,预计得分 $40\% \sim 44\%$。

算法三

我们对于计算最大路径数有两种不同角度的观察:

  1. 显然 $g$ 的值要么为 $0$ 要么为 $1$,这表示事实上 $g$ 就是代表达到子树中最优解是否必须有一条路径穿过 $u$,这当且仅当存在一条路径经过的 $g$ 均为 $0$。
  2. 这也可以看成一个贪心,我们仅仅是按照路径的 lca 自底向上贪心,能放就放。

考虑通过这种贪心思路来计算解,我们只需在 dfs 的过程中额外维护一个 vis 数组,表示“这个节点是否上面有一个父亲已经作为某条被选择路径的 lca”。未被染色的节点显然时刻都是与根节点相连的一个连通块。我们每次选择一条路径,只需把该节点子树中与之相邻的未被染色的节点染色。检查一条路径的时候,只需检查两端点是否均未被染色。这样就可以做到线性。

时间复杂度 $\Theta((n + m)n^2)$,预计得分 $44\%$。

算法四

我们提出如下观察:假设一个节点 $u$ 满足加入路径 $(u,u)$ 能够使得最大路径数增加,则称节点 $u$ 是 ok 的。那么一条路径加入后能使最大路径数增加,当且仅当路径上的节点都是 ok 的。

之前的过程中我们对于根的选择是任意性的,接下来我们考虑以一个节点为根的时候,穿过它的路径如果能够增大最大路径数,此时显然等价于路径上的节点均未被选中,也就是在贪心过程中这条路径就可以被选。

我们考虑染色之后与根节点联通的未被染色的连通块,这应当与与 $u$ 相邻的 ok 的节点所构成的的连通块是一致的。因为我们考虑在未被染色的这个连通块内进行换根,其他子树必然没有发生结构变化所以染色情况不变,因此穿过这个连通块的所有路径均不能选,在这个情况下染色数组完全没有变化,因此这个连通块的任何一个节点都是 ok 的。

我们只需以每个点为根进行一次算法三的操作,然后对于每个连通块,对答案的贡献就是连通块大小的平方。

时间复杂度 $\Theta((n+m)n)$,预计得分 $60\%$。

算法五

我们如何快速计算一个节点是否 ok。注意到贪心选择出的每条路径的 LCA,在任何一组最大路径集合中,这些节点都必然各自被一条路径覆盖。因此我们考虑将贪心选择出的每个路径及其 LCA 作为基础,发现在 LCA 的子树中的,不经过其他 LCA 的这一连通块内部,不 ok 的节点显然是该 LCA 对应的路径的一个子段。为了注意到为了让一颗子树里的节点不被覆盖,我们可以通过更换路径使得新的不与其他路径冲突的路径,用于更新原本路径 ok 的部分。注意在此时可以牺牲上方的空间,因此这个思路必须是自顶向下更新的。

因此两类路径可以用于更换被选路径:

  1. 该路径的 LCA 是 ok 的,此时显然这一路径已经与某条路径相交,如果只与一条路径相交,则可以更新该路径。
  2. 该路径的 LCA 和某个 LCA 重合,且不与其它路径相交,此时可以更新该路径。

对于如何快速判断一条路径是否只与一条路径相交,与哪条路径相交,我们可以打一个标记分为 $0, v, -1$,表示这一节点向上被选择的 LCA 有 $0$ 个,有 $1$ 个并标记其编号,或者有 $\ge 2$ 个。这样只需通过 DFS 即可更新标记,且一个节点只会被更新 $2$ 次。

通过离线处理,我们可以做到时间复杂度 $\Theta(n + m\alpha(m,n))$,如果使用 $\Theta(n)-\Theta(1)$ LCA 技术也可以做到 $\Theta(n+m)$,预计得分 $100\%$。

评论

newbiedmy
有毒,有毒[惊恐]

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。