模拟赛 13 题解

数论+最小生成树+字符串+模拟+最短路

A.GCD

不难发现 $f(i)\neq1$ 当且仅当 $i\neq p^k$，其中 $p$ 为质数。

所以可以在线性筛过程中求出 $f$，即所有 $p^k$ 的数。

B.小Ａ的同学图

发现题目和边权大小有关，不难联想到最小生成树。

把边权从小到大排序，依次加入每条边，类似 $Kruskral$。

加边的时候维护一下当前得到的不同颜色数，这个可以用bitset实现。

同时还要维护加到这条边后的答案前缀和，除了算上加完这条边的不同颜色个数，还要算上当前边与上条边边权之差再乘上上一次的 $ans$。

这是因为承受度在这两者之间的答案只能沿袭上一次的 $ans$。

这样做完，查询时直接前缀和+二分找到对应的左右端点，注意边界的情况。

考试的时候写了一个奇怪的做法：找到 $S$ 到其他点路径上最大值求最小，把他们作为分界点。

查询时把区间分成若干个颜色之间的段去跑。

后来想了想觉得是本质一样的。

C.前缀

先咕着，以后再改。

D.移动

也是最短路模型。

发现各个节点间未关闭的区间可以连边，跑最短路时用 $lower\_bound$ 找到前后可以连的区间连边就行了。

这个的实现方式有多种，可以用堆维护当前时间最小的状态，也可以直接最短路。

细节比较多，有时间再写一遍。