2023-2024年USACO竞赛第三场月赛金组试题解析已出！

解析：

算法：最短路

考虑对每一个点直接去求其余所有点到它的最短路，我们发现时间复杂度是$O(nmlogm)$的,会超时

由于题目只关心距离$x$点$R$以内的点是否有$k$个，所以我们可以转化成求距离$x$点距离最近的$k$个点的距离分别是多少

回忆最短路算法，对于多源最短路算法，我们会初始的时候将所有源点都加入到优先队列中

对于这一题其实同理，我们可以将所有源点都加入优先队列，不同的是，我们不仅要记录到一个点的最短路，我们也要记录是从谁到它形成的最短路

这样子看似我们的可行状态是有$n^2$个的，但是注意到题目对于每个点只需要求距离最近的$k$个，且$dijskra$算法优先处理的就是距离最近的点对，所以对于每一个点当它出现的到达它的点超过$k$个的时候我们就可以不再去做，于是这样子可以保证可行状态只会有$O(nk)$个

时间复杂度：$O(nklogm)$

解析：

算法：数据结构，分治

首先题目由于数组是一个环，所以我们可以通过迁移把最小值放在最后一位（后续会解释它的用处）

考虑数组的次大值（假设下标为$x$)，这时候假设它左边包括自己有$l$个元素，右边到$n-1$为止有$r$个元素

我们考虑在移动$i$次后有多少值会变为次小值，我们发现答案等于原序列里有多少长度为$i+1$的区间包含次小值且不包含最小值

我们考虑以$x$为左端点的区间有哪些包含次小值且不包含最小值的, 我们发现从$[1,r-1]$长度都是可行的

考虑$x-1$: $[2,r]$可行

同理$x-i$: $[i+1,r+i-1]$可行

于是我们可以对于$[1,r-1], \ [2,r], \ ... ,[l,l+r-2]$这些范围内的数都加上次小值

由于直接加效率会比较低，所以这个地方我们可以利用二阶差分来优化（只需要修改4个位置）

最终只需要考虑当前区间的最小值产生的贡献并将区间分治去做（这就是一开始将最小值移到最后的目的，为了避免考虑环带来的影响）

求区间最小值可以利用RMQ做到$O(1)$或者线段树做到$O(logn)$

时间复杂度: $O(nlogn)$

解析：

算法：贪心，set

这个题放在金组内比较简单

首先我们可以计算出对于任意两个位置它们之间碰撞需要花费的时间（分初始方向分类讨论）

```c++

double cal(int x,int y){

if (x%2==1){

double tt=1.0*(a[y]-a[x])/(c[x]+c[y]);

int k=ceil(tt)-1;

double u=tt-floor(tt);

if (u<1e-8) u=1;

return k*2+u;

} else {

double tt=1.0*(a[y]-a[x])/(c[x]+c[y]);

int k=ceil(tt);

double u=tt-floor(tt);

if (u<1e-8) u=1;

return k*2-1+u;

}

}

```

其次我们发现每一次碰撞一定是由相邻两个位置产生的

于是我们可以开一个set来维护当前相邻两个点的碰撞时间，每一次选出碰撞时间最早的两个点，将他们从set内删除，并加入新的相邻两个点的碰撞时间, 直到做到set为空为止

时间复杂度: $O(nlogn)$