【题解】口胡计划 SDOI2015

BZOJ 3990 [SDOI2015]排序

对于大小不同的段来说,它们之间相互不影响
那么考虑从小到大枚举段的交换

由于大小不同的段无法相互影响,换句话说,如果当前段的划分交换后无法使得其相对顺序调整完成,那么以后就再也没有办法调整了

所以直接 $DFS$ 即可
对于每个合法的序列,共有 $opt!$ 种贡献(可交换顺序)

BZOJ 3991 [SDOI2015]寻宝游戏

搞出欧拉序,最短距离就是按照欧拉序排序后相邻两点距离和

BZOJ 3992 [SDOI2015]序列统计

发现两者的积在模意义下的取值不太好做
考虑用原根将其转化为幂之和的形式
然后 $NTT$ 优化多项式快速幂即可

BZOJ 3993 [SDOI2015]星际战争

二分 $+$ 浮点数最大流,扩大 100000 倍转化为整数比较方便

BZOJ 3994 [SDOI2015]约数个数和

$$ d(nm)=\sum_{i|n}\sum_{j|m}[gcd(i,j)=1]\\ $$

考虑每一位质因数的取值即可

最后可得:

$$ S(n)=\sum_{i=1}^nd(i)\\ \sum_{t=1}^{n}\mu(t)S(\frac{n}{t})S(\frac{m}{t}) $$

补充:

$$ d(n)=\prod_{i=1}^{n}(a_i+1)\\ \sigma(n)=\prod_{i=1}^{n}\frac{p_i^{a_i+1}-1}{p_i-1} $$

还有神奇的杜教筛可以求 $\mu$ 的前缀和以及预处理+数论分块求 $d$ 的前缀和分别优化到 $O(n^{\frac{2}{3}})$

BZOJ 2186 [SDOI2015]道路修建

线段树,考虑两个块合并状态的种类数,仔细处理

Comments

添加新评论