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

T1

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

T2

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

先考虑一些特殊的状态

• ，此时无需进行游戏，已经完成目标。
• 当 时，，此时，结束当前回合就拿下了，继续投掷显然不优，所以需要一个回合。

接下来考虑 的递推。

• , ,... 求好了，考虑怎么求

决策有两种，

• 决策 1，放弃投掷：
• 决策 2，继续投掷：

这个递推的转移在 没有拓扑序，因为决策 2 等式右边依赖了 的值。

我们观察到 的值和等式左边 的值是有单调性的。

那么二分等式右边的 ，如果二分到

• 根据递推 ，依次求解
• 比较 和 的大小关系。

用后缀和优化 DP 转移，复杂度为

T3

• 我们可以观察到任意两个人的路径是不相交的，否则严格不优，因此每条边是“一方通行”的
• 考虑一棵树的情况。记 ，那么最小的搬运距离为 。
• 对于基环树的情况，我们考虑在环上任取一条边 ，枚举从 到 经过的人次 ，如果 则表示有 人从 走到了
• 断开 后，我们得到一棵树，以 为根，发现 取 到 路径上的点 值的中位数是最优的。

T4

不妨在 1 号点也放个任务 ，我们求出 两两之间的距离，记录

即从任务 , 到 ，到 ..... 到 的最短距离之和。

注意到，两人做任务一定是交替的区间，例如

• Alice 完成 1,2,3
• Bob 完成 4,5,6
• Alice 完成 7,8,
• Bob 完成 9

表示任务 被 Alice 完成了，Bob 上一个完成的任务是 ，且完成 到现在已经过去了 的时间。

我们枚举 Alice 接下来完成的任务 。直到第 个任务交给 Bob。转移分为两种。

• 如果 那么 Bob 到达 后，Alice 还没有没来，那 Bob 只能等着。
• 否则 Alice 可以在 Bob 到达 前 的时间离开

复杂度为