题解 | 2024牛客OI赛前集训营-提高组（第五场）

T1

20 pts: 对每组询问，暴力枚举所有区间，计算区间 gcd 的值即可。复杂度 $O(qn^2 \log n)$
50 pts: 对每组查询，用 ST 表求区间 gcd，枚举左端点，二分右端点即可。复杂度 $O(n \log^2n qn\log n)$
80 pts: 考虑到数据随机的性质，根据质数的密度，gcd = 1 的区间长度上界是 $O(\log n)$ 级别的。那我们可以对每个左端点 $l$ ，维护最小的右端点 $r$ ，使得 $GCD(l,r)=1$ ，然后增量更新答案，复杂度 $O((n q) \log^2 n)$
100 pts: 记录 $f(k)$ 为区间 gcd 为 k 的倍数的区间，有多少个。那么根据 $\sum \mu(k) f(k)$ 来计算答案。对每个 $k$ 我们用 set 维护极长的，所有元素都是 $k$ 的倍数的区间。复杂度为 $O((n q)\log^2n)$

考虑动态规划的做法，我们用 $f(i, j)$ 表示目标分数为 $i$ ，当前轮得分为 $j$ 的局面，最优策略需要几个回合(当前回合需要被计算在内)

先考虑一些特殊的状态

接下来考虑 $i$ 的递推。

决策有两种，

决策 1，放弃投掷： $f(i, j) = min(f(i, j), 1 f(max(i - j, 0), 0))$
决策 2，继续投掷： $f(i, j) = min(f(i, j), \frac{1}{M}(1 f(i, 0)) \frac{1}{M}\sum_{k=1}^{M-1}f(i, j k))$

这个递推的转移在 $j$ 没有拓扑序，因为决策 2 等式右边依赖了 $f(i, 0)$ 的值。

我们观察到 $f(i, 0)$ 的值和等式左边 $f(i, j)$ 的值是有单调性的。

那么二分等式右边的 $f(i,0)$ ，如果二分到 $x$

根据递推 $f(i, j) = min(\frac{1}{M} (x 1) \frac{1}{M}\sum_{k=1}^{M-1}f(i, j k), 1 f(max(i - j, 0), 0))$ ，依次求解 $f(i, i - 1), f(i, i - 2), ...., f(i, 0)$
比较 $f(i, 0)$ 和 $x$ 的大小关系。

用后缀和优化 DP 转移，复杂度为 $O(N^2log N)$

我们可以观察到任意两个人的路径是不相交的，否则严格不优，因此每条边是“一方通行”的
考虑一棵树的情况。记 $sum(u) = \sum_{v \in subtree(u)} (a_v - b_v)$ ，那么最小的搬运距离为 $\sum_u |sum(u)|$ 。
对于基环树的情况，我们考虑在环上任取一条边 $u, v$ ，枚举从 $u$ 到 $v$ 经过的人次 $x$ ，如果 $x<0$ 则表示有 $-x$ 人从 $v$ 走到了 $u$
断开 $u,v$ 后，我们得到一棵树，以 $u$ 为根，发现 $x$ 取 $v$ 到 $u$ 路径上的点 $sum$ 值的中位数是最优的。