6.23 模拟赛

A 圆圈游戏

一道优秀的扫描线题。

我们考虑没有相交和包含,提示我们可以通过包含的关系建立出一棵树,一个点的儿子就是它极大的包含的圆。

如果能够建立出这个树,那么我们可以在树上做一个非常 trival 的 $dp$ 解决问题。转移就是枚举选不选这个点。

我们考虑怎么建立这个树。考虑从左往右进行扫描,到达一个圆的左端点的时候就加入这个圆,到达右端点的时候删掉他。我们考虑在删掉一个圆的时候找出它的父亲。

如果这个圆右端点向上引一条切线,考虑讨论一下这个切线碰到的第一段弧。如果这段弧是一个上圆弧,显然我们找到了它的父亲,就是这个上圆弧对应的圆。如果碰到了一个下圆弧,那么这个点一定和碰到的下圆弧这个圆是兄弟关系,也就是它们的父亲相同。因为画一下会发现,此时不可能存在一个圆单独包含这个圆或者碰到的那个圆,如果存在,碰到的就不会是那个圆了。

那么还有一个问题,怎么维护这些圆呢?不难发现,随着扫描线的移动,圆之间的相对关系一定不会改变。因此直接把这些圆弧拖进一个 set 中维护即可。

代码实现上有一个需要注意的地方,插入和删除圆弧的时候一定要用当前的 $x$ 对应的 $y$ 来比较,直接比较最左端点或者最优端点的 $y$ 显然是不对的。

复杂度 $O(n\log n)$ 。

B 划分序列

结论题。我场上打表打出了最小值关于 $k$ 的单峰关系,却没看出这个结论。。。

我们先二分一个最大段的最小值,于是问题就变成了能否选择恰好 $k$ 个段使得每个段的和都小于等于 $mid$ 。如果打一个表会发现,最后答案关于 $k$ 是一个单峰函数,也就是说,如果确定了 $mid$ 的值,合法的 $k$ 一定是一段区间。(场上没看出这两个条件等价感觉非常亏)

于是剩下的部分就非常简单了,我们考虑求出最小的合法的 $k$ 和最大的合法的 $k$ 。也就是求出此时最少选择的段数和最多选择的段数,转移非常显然,就是

这个问题只需要对前缀和离散化一下就变成了后缀最大最小值查询,一个 BIT 即可搞定。

C 生成树求和

这个题我是做过一个几乎一样的题的,场上数组开小了 TAT

有一种并不需要单位根但是仍然可以通过的做法,虽然比单位根多一个 $n$ ,但是 $O(n^4\log v)$ 是非常稳的。

显然这个题可以逐位考虑。然后我们对于每条 $0$ 边,认为它边权是 $1$ ,对于每条 $1$ 边,认为边权是 $x$ ,$2$ 边边权是 $x^2$ 。然后我们考虑用矩阵树定理求出所有生成树的和,不难发现求出来的东西是一个关于 $x$ 的多项式,这个多项式的 $x^i$ 系数就是加起来等于 $i$ 的生成树个数。

但是显然直接对这个东西做高斯消元很不行。但是最终多项式系数不超过 $2n$ (就是这个东西,我把数组开到 $n$ 于是炸了),所以可以插值一下,求出 $i = 1\dots 2n$ 的时候 $f(i)$ 的值,这里每个值都可以一次矩阵树定理计算。最后直接拉格朗日插值即可。

复杂度是 $O(n^4 \log n)$ 。

这个做法显然不如用单位根优秀,但是它可以求出在固定选择 $i$ 条 $1$ 边和 $j$ 条 $2$ 边时的答案。

再写一下单位根的做法。由于 $10^9 + 7$ 为模数的时候是不存在三次单位根的,我们可以扩域,把每个数写成 $a + b\omega_3$ 的形式。由于 $\omega_3^2 = -\omega_3$ ,每条边的边权就是 $1$ ,$\omega_3$ ,$-\omega_3$ 。然后直接对这个东西做矩阵树定理即可。求逆元的时候用共轭复数推一下就有了。

复杂度是 $O(n^3\log n)$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/07/02/623-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog