2023-2024年USACO计算机竞赛一月赛赛题出炉！让我们一起来了解一下吧~
USACO
USACO 2023 DECEMBER CONTEST
BRONZE（铜级）
第一题
题目描述:
农夫约翰有一项重要的任务-弄清楚为他的奶牛买什么类型的干草。
农夫约翰的 N头牛(2≤N≤10)从1到N编号,每头牛只喜欢一种干草hi(1≤ hi
≤N)。他希望所有的奶牛都喜欢同一种干草。
为了实现这一点，农民约翰可以举办小组会议。小组会议会将一段连续的编号的奶牛聚集在一起开会，他们的编号为到i到j。在小组中如果有一种干草超过一半的奶牛喜欢，那么在小组会议结束后，该小组的所有的奶牛都喜欢这种干草。如果没有这种干草，那么没有奶牛改变它们喜欢的干草。例如，在由16头奶牛组成的小组中，其中9头或更多的奶牛需要具有相同的干草偏好，才能使其余的奶牛改变偏好。
农夫约翰想知道哪种干草能被所有的奶牛喜欢。他一次只能举办一个小组会议，但他可以多次举办会议，让所有的奶牛都喜欢同一种干草。
题目解析：
对确定的目标数，显然做其他数为众数的操作不优。可证能达到目标当且仅当已经有两个目标数相邻或可以做一次以它为众数的操作（做完此操作后逐一向左右拓展即可）。
这样的操作若存在，总可通过取数更多的一半区间直到长度不超过3。所以只要判断有没有长度为3的区间以目标数为众数。
第二题
题目描述:
贝西已经掌握了变成炮弹的艺术，并沿着长度为N(1≤N≤10的5次方)的数轴从左到右弹跳，位置为1,2,.,N。她从某个整数位置S(1≤S≤N)开始向右弹跳，起始能量为1。如果贝西的能量是k，她的下一次弹跳将在距离她当前位置前方k处。从1到N的每个整数位置要么是靶子，要么是跳板。每个目标和跳板都有一个范围为0到N的整数值。一个权值为v的跳板会使贝西的能量增加v，并使她的方向反转。如果落在一个权值为v的靶子上时贝西的能量至少为v，那么它就会被打破。落在一个靶子上并不会改变贝西的能量或方向。破碎的靶子将保持破碎状态，贝西仍然可以在不改变力量或方向的情况下弹跳。
如果贝西可以弹跳无限长的时间或直到她离开数轴，她会打破多少个靶子?
如果贝西从一个她能打破的靶子开始跳跃，它就会立刻被打破。类似地，如果贝西从一个跳板开始跳跃，这个跳板的效果将在她第一次跳跃之前生效。
题目解析:
模拟，若同一个跳板两次被同一个力度跳到，可证以后会循环并不会有新的破碎。因此力量不变时最多跳一个来回，求和为 nlogn。
第三题
题目描述:
农夫约翰有N(1≤N≤2*10的5次方)块草地分布在一条直线上，其中第i块草地的细菌水平与健康草地的细菌水平相差ai(-10的15次方≤ aj≤10的15次方)，例如，如果ai=3，那么第i块草地的细菌水平低于正常水平，并且需要添加3个额外的细菌单位才能将其提高到健康的水平。
农民约翰想要确保每一片草地都被清理干净，使细菌含量达到健康水平。方便的是，他有两种牌子的农药可以喷洒在他的田地上，一种会增加细菌，另一种会去除细菌。当农民约翰喷洒两种农药时，他站在第 N块草地上(最右边的一块)，并为他的喷雾器选择功率等级L(1≤L≤N)。
喷雾器对农民约翰附近的草地影响最大，离得越远效果越小。如果农民约翰选择了添加细菌的农药，那么 L个单位的细菌将被添加到草地N中，L-1个细菌单位添加到草地N-1中，L-2个细菌单位添加到草地 N -2中，以此类推。草地1.....N-L不会接收到细菌，因为喷雾器没有设置足够的功率去喷洒它们。同样，如果农民约翰选择了除菌的农药，那么从草地N中去除L个单位的细菌，从草地N-1中去除L-1个单位的细菌，以此类推。同样的，草地1......N-L不会受到影响。
你需要找出农夫约翰必须使用喷雾器的最少次数，使得每片草地上的细菌都达到健康草地的水平。可以保证答案不超过 10的9次方。
题目解析：
考察差分 bi=ai-a(i-1)，其中a0=0和原列一一对应。操作为将b的一个后缀同时加减1。可以再差分得到每个后缀应该修改多少。
USACO
USACO 2023 DECEMBER CONTEST
SILVER（银级）
第一题
题目解析:
有q对(x,y)的输入，每对表示前1~x个数右边第一个比它们大的数必须在下标为y的位置，这
句话还有一个隐藏含义就是第x+1到第y-1个数必须比前1~x个数的最大值要小，即第y个数
比前y-1个数都要大(代码中称为前缀最大值)。用一个前缀和数组pre_max[i]表示前i个数中的
最大值，则a[y]至少为pre_max[y-1]+1。
现在从左往右遍历a[N]，分类讨论每一个a[i]的情况：
1.a[i]==0且位置i是前缀最大值，令a[i]=pre_max[y-1]+1
2.a[i]==0且不是前缀最大值，根据贪心思路令a[i]=1（字典序最小）
3.a[i]不为0，是第x+1到第y-1个数的其中一个，但是比前x个数要大，破坏了前缀最大
值的要求，此时需要把之前的某个能改的值提高为a[i]
对全部a[N]修改完毕后，再重新for循环扫描一遍看看新的a[N]有没有冲突，有冲突输出-1
注意事项：这题有T个测试，每个输出最后不能带空格
第二题
题目解析:
以房间1为根节点的树。每次traversal相当于从根出发，沿着父子关系一直走，一个traversal
的终点一定是一个叶节点，因此最小的traversal数必定为叶节点数量，可以用dfs得到，假设
这个数量是k。可以用树上DP来记录每个节点的子树拥有的叶节点数量，状态转移方程为
dp[fa]+=dp[child],则dp[1]就是整棵树拥有的叶节点数量
此时来看题目对potion的描述，每次traversal会在一个节点生成一个potion，下一次traversal
前消失，而我们只会有k个(即dp[1]个)traversal。因此实际上只需要考虑前k个potion。而由
于potion是依靠traversal获取的，因此potion和traversal,也就是叶节点，是一对一绑定的。
假设我们目前在某个节点p，从点p出发获得的potion数量不会超过点p的子树拥有的叶节
点数量。我们再用一个树上DP，potion[p]表示点p的子树拥有的potion数量，状态转移方程
为potion[fa]+=potion[child]。统计完毕后再令potion[p]=min(potion[p],dp[p])。
最终potion[1]就是本题答案。
第三题
题目描述:
题目等价于N个数除以L最多只有3个不同的余数，根据抽屉原理，任意选择4个不同的数 ，必定至少有两个数a[i]和a[j]除以L的余数相同(即模L同余)。由同余的基本性质可知abs(a[i]-a[j])必定能被L整除。
因此本题只需要从a[N]中任选4个不同的数，枚举它们的两两差值(一共有 = 6 种)，对这6个数，枚举它们的所有因子fac，进行检验（看看a[1]到a[N]除以fac是不是最多只有3个余数），符合要求则令ans+=fac。
对于0经验的学生如何备赛？
自学是一个很艰难和缓慢的过程，计算机学习中涉及到大量的软硬件问题，对于没有基础的同学来说，很容易在自学过程中放弃或者偏离正确的学习方向。
我们的课程会帮同学们打好编程基础，根据学生特点和学习需求定制课程计划，让同学循序渐进的学习，带领同学们突破题目的难点。
USACO备赛课程
*仅供参考，可灵活调整
【竞赛报名/项目咨询请加微信：mollywei007】
