12月USACO竞赛晋级赛白银组别考情分析|附USACO竞赛冲刺培训

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have N (1≤N≤2⋅10**5) distinct weights. In particular, for each i∈[1,N], ai of his cows have a weight of wi (1≤ai≤10**9,1≤wi≤109).

His most popular stunt involves the cows forming balanced towers. A tower is a sequence of cows where each cow is stacked on top of the next. A tower is balanced if every cow with a cow directly above it has weight at least K (1≤K≤10**9) greater than the weight of the cow directly above it. Any cow can be part of at most one balanced tower.

If FJ wants to create at most M (1≤M≤10**9) balanced towers of cows, at most how many cows can be part of some tower?

考情解析

考虑从前往后贪心，首先假设每个塔最下面的数都是负无穷，然后从小到大把每一个数加入塔中。考虑加入塔中的过程，每一次我们都把这个数加入到之前塔顶数最小的位置，如果此时不能插入，说明这个数没法继续插入了。由于每种数有很多个，一个个插入时间复杂度会过大，考虑将每种数作为一个整体插入。在当前这种数插入在另一种数的上方的时候，要么另一种数完全覆盖，要么当前这种数被用完，所以每种数最多被考虑一次。

时间复杂度：O(nlogn)

知识点：贪心，排序

Farmer John has N barns(3 <= N <= 5.10**5), of which K(3 <= K <= N) distinct pairs of barns are connected.

First, Annabelle assigns each barn a distinct integer label in the range[1, N], and observes that the barns with labels a1...ak are connected in a cycle, in that order. That is, barns ai and a(i+1) are connected for all 1 <= i < K, and barns ak and a1are also connected. All ai are distinct.Next, Bessie also assigns each barn a distinct integer label in the range[1, N] and observes that the barns with labels b1,...bk are connected in a cycle, in that order. All bi distinct.

Some (possibly none or all) barns are assigned the same label by Annabelle and Bessie. Compute the maximum possible number of barns that are assigned the same label by Annabelle and Bessie.

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

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

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

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

时间复杂度：O(n)

知识点：环，计数

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤10**5) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10**5) commands, each one of L, F, or R:

● L: Bessie moves one unit to the left.

● R: Bessie moves one unit to the right.

● F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

解析：

先求所有的步骤整体平移-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之类的变化情况相加。

时间复杂度: O(n)

知识点：思维难题