2024年2月（第三场）USACO计算机竞赛金牌题解

金牌题解来咯，因文章篇幅有限，将金牌的三道题解分享给大家。

USACO 2024年2月金牌第一题

P1:Bessla motors

解析：

算法：最短路考虑对每一个点直接去求其余所有点到它的最短路，我们发现时间复杂度是$O(nmlogm)$的,会超时由于题目只关心距离$x$点$R$以内的点是否有$k$个，所以我们可以转化成求距离$x$点距离最近的$k$个点的距离分别是多少回忆最短路算法，对于多源最短路算法，我们会初始的时候将所有源点都加入到优先队列中对于这一题其实同理，我们可以将所有源点都加入优先队列，不同的是，我们不仅要记录到一个点的最短路，我们也要记录是从谁到它形成的最短路这样子看似我们的可行状态是有$n^2$个的，但是注意到题目对于每个点只需要求距离最近的$k$个，且$dijskra$算法优先处理的就是距离最近的点对，所以对于每一个点当它出现的到达它的点超过$k$个的时候我们就可以不再去做，于是这样子可以保证可行状态只会有$O(nk)$个时间复杂度：$O(nklogm)$

USACO 2024年2月金牌第二题

P2: Milk Exchange

解析：

算法：数据结构，分治首先题目由于数组是一个环，所以我们可以通过迁移把最小值放在最后一位（后续会解释它的用处）考虑数组的次大值（假设下标为$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)$

USACO 2024年2月金牌第三题

P3: Quantum Moochanics

解析：

算法：贪心，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)$

为什么参加USACO计算机竞赛:

1. 挑战性：USACO计算机竞赛是一项世界级的竞赛，提供了挑战性的问题，涵盖了广泛的计算机科学概念，包括算法、数据结构和编程技能。

2. 学习机会：通过解决USACO的问题，你可以学到很多关于算法和编程的知识，提高自己的技能水平。这对于计算机科学和编程领域的学习都是非常有帮助的。

3. 竞赛经验：参加USACO计算机竞赛可以为你积累竞赛经验，这在未来参加其他竞赛或者申请计算机相关的学校和工作时会有所帮助。

4. 社区支持：USACO计算机竞赛有一个庞大的社区，你可以和其他竞赛选手交流经验、分享解决问题的方法，这对于提高自己的技能也是非常有益的。