Codeforces Round #714 GCD and MST 混合题

题意

给你一个长度为$n$的数组$a$。以及一个$p$。现在用如下方式生成一张图:

  1. 对于任意$i,\ j(i<j)$之间有一条边当且仅当$gcd(a_i,a_{i+1},...,a_j)=min(a_i,a_{i+1},...,a_j)$,且这条边的边长为min(a_i,a_{i+1},...,a_j)。
  2. 对于任意的$i$,$i$到$i+1$有一条边长为$p$的边。

现在问,这张图的最小生成树的总边长是多少。


题解

显然我们会立刻想到Kruskal算法。试图寻找最小的边。

Kruskal部分

首先考虑通过GCD生成的边。

我们可以发现对于$i,\ j(i<j)$,$i\leq{k}\leq{j}$且$a_k=min(a_i,a_{i+1},...,a_j)$(也就是k就是那个最小值)的时候,有$a_k$能整除$a_i$到$a_j$之间的所有值。

于是就有,从$k$出发,向左和向右探索的最远点之间的所有点之间都有边长为$a_k$的边。

于是在$a_k<p$的时候,我们就尽可能的使用这样的边就好了。一旦$a_k\geq{p}$,我们就直接使用长度为$p$的那些边。

现在Kruskal的部分已经比较清晰了,剩下的问题就是怎么从$k$出发找到能被$a_k$整除的最远点。

改动并查集部分

首先如果我们每次都从$k$出发,依次计算GCD的话显然会是$O(n^2)$的。于是我们就想在并查集上做一些定制。

我们观察$O(n^2)$的做法会发现,其根本问题在于:对于已经连进来了的点,这个做法还会再连一次。

于是很自然的想到,每次寻找都从当前并查集的边界出发。这样就能跳过当前所在集合里的所有点。

所以,除了维护并查集的集合信息,我们还维护集合的左右边界。

线段树部分

如果每次都是从集合边界出发,那么就不可避免的要查询$k$到边界之间的GCD。于是我选择套了一个线段树上去,用于查询区间GCD。


代码

Submission #112843677 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号