模拟赛 7 题解 | AlanSP's Blog

数学+边双+树上倍增+二分+dp+贪心

我们发现 $d(x)$ 是奇数当且仅当 $x$ 是完全平方数。

当 $i*j=x^2$ 的时候， $i=p^2*t,j=q^2*t$ 。

那么我们考虑固定一个 $t$ ，计算 $p$ 和 $q$ 的数量。

不难发现 $p^2*t\leqslant n,q^2*t\leqslant m$ ，那么 $p\leqslant\sqrt \frac n i$ ， $q\leqslant\sqrt \frac m i$ 。

所以我们以 $q$ 的奇偶定符号， $|p|$ 作为值就好， $O(n)$ 的扫一遍。

首先使最小移动速度最大，我们想到二分。

我们可以发现一个性质：最终的速度一定使这 $n+1$ 个点两两之间到达速度之一，证明类比货币系统。

这样只需要把他们之间的速度算出来，排序二分就行。

check的时候采取 $O(n^2)$ dp，枚举上一个出现的点，如果速度在lim范围内就可以转移 $1$ 。

至于答案的输出方式，只要维护分子和分母分别是多少，最后约分开平方即可。

我们知道，处在同一个边双联通分量里面的点之间一定是有两条路径的。

那么我们考虑按 $v-bcc$ 缩点，那么原图便形成了一棵树。

每次链接树上的两个点，那么这两个点间路径上的连通块都可以满足条件。

考虑新增的点对数，即为 $(\sum c_i)^2-\sum c_i^2$ 。

树上倍增维护路径和和平方和即可。

由于是在环上，我们先破环成链，并拆成 $2n$ 条线段。

参考国旗计划这个题，我们可以预处理出每条线段向后跳 $2^i$ 步不选相交的线段能到哪里。

那么我们可以考虑强制选第 $i$ 条线段，那么这条线段的最远长度是 $L_i+m$ 。

每次只要从高到低扫一遍，直到第一个跳到的线段小于这个长度即可。