2023年12月USACO银组试题解析，附USACO课程培训辅导

1、知识点：贪心，排序

2、题意：

给定n种牛的数据，包含每种牛的重量（不重复）和数量，可以选择m组牛，每组可以选择任意种牛，需满足任两头牛重量之差>=k，求m组最多一共选择了多少头牛？ 

3、题解：

考虑从前往后贪心，首先假设每个塔最下面的数都是负无穷，然后从小到大把每一个数加入塔中。

考虑加入塔中的过程，每一次我们都把这个数加入到之前塔顶数最小的位置，如果此时不能插入，说明这个数没法继续插入了。

由于每种数有很多个，一个个插入时间复杂度会过大，考虑将每种数作为一个整体插入。在当前这种数插入在另一种数的上方的时候，要么另一种数完全覆盖，要么当前这种数被用完，所以每种数最多被考虑一次。

1、知识点：环，计数

2、题意：

给定n个谷仓，和两个k个大小的环(1-n)，每个环上相邻的两个点有边相连。现要给1-n的每个谷仓编号，问在满足两个环上相连状态，最多能有几个谷仓编号是一样的?

3、题解：

A与B最多有多少元素相同其实就是看两个环最多能有多少个位置能匹配。

匹配的定义是：环A和环B按某种顺序按位匹配后相同数字最多是多少个。

我们可以考虑让A环不动，B环循环右移，对于每一种字符计算出需要将环循环右移多少步得到，最终查询哪个步数出现次数最多即可。

注意我们还要考虑环外点最多有多少匹配：这个比较简单，我们只需要统计剩下元素里有多少种类A与B是相同的即可。

1、知识点：思维难题

2、题意：

给定一些目标靶的位置，和一串字符串表示牛的操作顺序，L代表向左移动一个位置，R代表向右移动一个位置，F代表射击当前位置。牛的初始位置是0，牛最多可以改变一个位置的操作，求最多能射击到多少个靶子？

3、题解： 

先求所有的步骤整体平移-2,-1,0,+1,+2时可以击中多少个目标。答案在change[1]-change[5]。再用hit[1-5][位置]记录每个位置被击中了多少次。

然后i从左往右一位位求i之前已经固定，i改变以后，能击中多少次；

这样求完以后只需要把第i位固定带来的影响，更新到change和hit里就可以了。

i从左往右固定过程中，如果这一位是L和R只影响位置p；

但如果这一位是F，那么固定以后，就要更新hit里的次数。因为它-2 -1 +1 +2都不可能发生了。

所以更新了两部分内容。

1. 当前位置p，如果之后的F因为-2 -1 +1 +2击中过它，现在应该i已经固定，它一定会被这一次射击击中。所以把-2 -1 +1 +2以后的p位置的hit数都清0，change对应更新。

2. 当前位置p，-2 -1 +1 +2以后的位置的hit数减少1次，如果减到0就更新change

最终就是，确定会击中的数量cnt，和change数组维护的i之后的-2 -1 +1 +2以后的4种不同击中数量，根据L->R R->L之类的变化情况相加。