2024年USACO考题新鲜出炉！黄金组别考情分析

USACO计算机编程竞赛的1月月赛已经完美结束啦，这次题目难度比较大，不少学生在参加USACO竞赛时，对计算机语言运用还是不够熟练，那么我们一起来复盘以下2024年1月考题情况，一起来看下，文末有USACO竞赛辅导，在线咨询客服老师~

USACO 2024年1月黄金组别考情分析

第1题

考察算法：二分，观察性质

首先假设当前在x轴朝向上行走，什么时候会转向到y轴?

我们发现当且仅当当前道路距离下一条道路是奇数距离的时候会转向

于是我们可以考虑去二分转向的次数，计算出在当前转向次数下运动的距离，判断它是否小于等于题目给出的运动距离

代码实现较为复杂，需要注意细节

时间复杂度：$O((n+q)*log)

第2题

考察算法：动态规划

和银组第一题类似

定义$i$这个位置是前缀最大值当且仅当$a[i]>a[j]$ (for all $1le j

我们会发现对于某个$(a[i],h[i])$相当于要求$[a[i]+1,h[i]-1]$这一段不能是前缀最大值，$h[i]$这个位置必须是前缀最大值

最终我们将相同情况的序列合并在一起，那么就是有最多$3*Q$段的序列(每一段内部要么要求一定是前缀最大值/一定不是前缀最大值/没有要求)，求最终合法的方案数

定义$dp[i][j]$代表当前考虑到前$i$段数，选的数的最大值是$j$的方案数

假设当前这一段序列长度为$len$

当一定是前缀最大值时：

$dp[i][j]=sum_{k=1}^{j-1} dp[i-1][k]$

当一定不是前缀最大值时：

$dp[i][j]=dp[i-1][j]*j^{len}$

当没有要求时：

$dp[i][j]=dp[i-1][j]j^{len} + sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

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

第3题

考察算法：二分

注意到分给Bessie自己的数越多答案相应的会越大，但是会越容易满足题目限制

所以我们考虑去二分分给Bessie的个数$mid$

那么它们分别被加入序列的时间就是$mid, mid + (mid-1) ,... , mid+...+1$

显然我们比较希望尽量靠后的数能被加入到Bessie的序列中，所以对于每一个加入序列的时间我们可以贪心的去找到第一个大于当前时间且没有被插入到序列中的数，将它插入到序列中

这个过程可以用类似于双指针的思想来优化

最终$min(数字最大值,mid*(mid+1)/2)$就是我们的答案

2023-2024年USACO活动时间

第一次月赛：2023年12月15日-18日

第二次月赛：2024年1月26日-29日

第三次月赛：2024年2月16日-19日

美国公开赛：2024年3月15日-18日

（中国学生只能参加到公开赛）

集训营：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷兰）

IOI：2024年9月1日-8日（埃及）

报名方式：参赛者可随时在官网注册账号，注册。报名，只需在活动时间登陆完成答题即可。

官网地址：usaco.org

提交之后，官网会发送一份邮件到您邮箱，邮件中有账号密码

利用已知的账号于密码，登录USACO账号，即可开始考试