2021.10.19模拟赛

Frozen into icy rocks, that’s how it starts

2021.10.19 模拟赛

A. 最小和

set里插入前缀和，找到它的前驱后继保存答案，值相同取标号最小的

B. 小奇回地球

二分加值跑最短路就行，需要注意到不了终点的点对答案无影响，即使存在负环

所以从终点开始 BFS 找出来能到终点的点，在上面跑最短路

C. Alice’s Trouble

析和树板子题

D. 爱与和平

实际上就是找到 $\gcd(d,\dfrac{x}{d})=1$ 的部分做 dp ，是一个转二叉树的过程，用 $O(n)-O(1)$ $\gcd$ 就可以做到 $O(n\log n)$

但是卡常跑不过去

出题人的做法是预处理质因子集合，枚举子集转移，复杂度 $O(n\log n + \sum 2^{\omega(n)})$ 能跑过去，离谱