USACO竞赛真题解析及培训辅导课程安排~

USACO竞赛考什么?考试内容包含什么?历年考试真题资料及培训辅导课程安排，为大家简单的分析以下，方便大家掌握USACO竞赛的详细内容，欢迎咨询网站客服了解~

2023-2024年新赛季USACO竞赛12月月赛已经落幕，12月月赛都考察哪些知识点，我们对USACO青铜、白银和黄金组别比赛进行考情分析，供同学们参考。

12月USACO竞赛青铜组解析

Candy Cane Feast

农夫约翰的奶牛很爱吃甜食，它们特别喜欢吃甘蔗糖!FJ有N头牛，每头牛都有一定的初始身高，他想喂它们M每根也有不同高度(1≤N，M≤2·10^5)。

按照它们在输入中的顺序，FJ计划将甘蔗糖一根接一根地喂给奶牛。为了给奶牛喂甘蔗糖，他会把甘蔗糖挂起来，这样甘蔗糖一开始就刚好碰到地面。然后，奶牛将按照输入的顺序一头接一头地排队，走到甘蔗糖前，每头牛都吃到自己的高度(因为它们不能再高了)。即使在奶牛吃掉糖果棒的底部后，糖果棒也会悬挂在最初设置的位置，不会下降到地面。

如果甘蔗的底部已经超过奶牛的高度，那么奶牛在轮到它的时候可能什么都不吃。轮到每头牛后，奶牛的身高会根据它们吃了多少单位的甘蔗糖而增加，农民约翰挂上下一根甘蔗糖，奶牛再次重复这个过程(第一头牛再次成为第一个开始吃下一根拐杖糖的人)。

试题解析：

这个题是个有意思的暴力问题，同学们考虑一个子问题：

一个数初始是1.每一次操作是让它乘2.要求这个数小于等于n，求最多能操作多少次

这个问题的答案比较显然是log2n次

那考虑当前的问题，考虑第一头牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22;如果牛比甘蔗高，此轮吃甘蔗结束。

所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。

时间复杂度：O(nlog2n)

知识点：暴力，时间复杂度分析

Cowntact Tracing2

农夫约翰有N排成一行的奶牛(1≤N≤3·10^5)。不幸的是，有一种疾病正在蔓延。

最初，一些奶牛开始被感染。每天晚上，受感染的奶牛都会将疾病传播给左右两侧的奶牛(如果存在的话)。一旦奶牛被感染，它就会继续被感染。

经过几个晚上，农夫约翰意识到问题已经失控，所以他对奶牛进行了测试，以确定谁生病了。找出可能开始患病的奶牛的最小数量。

试题解析：

首先我们可以根据输入计算出1的扩散时间最长是多少(时间越长需要的初始点就越少)

注意边界和中间的计算方式不同，中间扩散的结果是1.3.5....,2*n-1.而边界是1.2.3....,n$因为边界可以放在最角落开始)

计算出最长扩散时间max_time后我们就可以对每一段连续为1计算初始最少需要放几个1 : len = 2*max_time+1 (len代表连续1个数)

最终将答案相加即可

时间复杂度：O(n)

知识点：贪心，边界条件判断

Farmer John Actually Farms

农民约翰正在种植N(1≤N≤2·10^5)他的农场里种着芦笋!然而，他的一些植物有遗传差异，所以有些植物会比其他植物生长得更快。

i的初始高度

第th株是hi英寸，每天之后

第th种植物生长ai英寸。

FJ比其他植物更喜欢他的一些植物，他希望一些特定的植物比其他植物高。他给你一组不同的值t1.…，tN包含0中的所有整数至N−1

他想要我第th株植物正好有ti其他比它高植物。

找到最小天数，以便FJ的要求得到满足，或者确定这是不可能的。

试题解析

考虑根据最终的排序结果来确定有多少条件，容易发现其实只有$n-1$个有效的不等式，即第1个小于第2个，第2个小于第3个，...

根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围

最终对于所有不等式结果求出交集，如果不为空就输出最小值，否则输出-1

时间复杂度：O(n)

知识点：简单数学

12月USACO竞赛白银组解析

P1 Bovine Acrobatics

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)

知识点：贪心，排序

P2 Cycle Correspondence

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)

知识点：环，计数

P3 Target Practice

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)

知识点：思维难题

12月USACO竞赛黄金组解析

P1 Flight Routes

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N(2≤N≤750) cities labelled 1…N, and for each pair of cities (i,j) with i

A flight route from city a to city b (a

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

考情分析

从相邻位置来考虑比较简单，如果i到i+1路径为奇数，说明i到i+1有边，反之没有。

考虑任意点i和j的时候，只需要利用区间dp的思想计算出i到j除了直接到达的路径有多少条，看一下是否满足奇偶性即可。

时间复杂度:  O(n^3)

知识点：区间dp

P2 inimum Longest Trip

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10^5) towns numbered from 1 to N and M (1≤M≤4⋅10^5) one-way roads. The i-th road runs from town ai to town bi and has label li

(1≤ai,bi≤N, 1≤li≤10^9).

A trip of length k starting at town x0 is a sequence of towns x0.x1.…,xk, such that there is a road from town xi to town xi+1 for all 0≤i

For each town, Bessie wants to know the longest possible trip starting at it. For some starting towns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.

考情分析

首先题目保证给出图是DAG，那么我们要求最长路的话就可以利用拓扑排序/bfs来解决。

难点在于题目要求字典序最小，考虑如何快速比较两条出边的字典序大小

由于题目权值可以相同暴力走下去比较时间复杂度会被卡到$O(n^2)$

为了优化比较过程，我们希望能够快速得到两个最长路相同的点他们之间的字典序关系。

所以我们可以动态地对最长路相同的点的内部做一个排序，比较的时候就只需要拿出之前维护好的排序结果去做判断，判断时间复杂度就可以做到O(1)

总时间复杂度：O(nlogn)

知识点：拓扑排序，字典序

P3 Haybale Distribution

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10^5) barns, located at integer points x1.…,xN (0≤xi≤10^6) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10^6) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some ai and bi

(1≤ai,bi≤10^6), ai haybales are wasted per unit of distance left each shipment is transported, and bi haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by

Given Q (1≤Q≤2⋅10^5) independent queries each consisting of possible values of (ai,bi), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.

考情分析

观察1：查询的次数很多，可以考虑预处理，由于不需要频繁修改区间，使用前缀和即可。

观察2：题目保证数轴x1...xN上存在一个极小值点y，通过等式变形/反证法可以证明y必定为x1...xN中的一点，同时路径总和f(y)是一个两边往中间递减的单峰函数，可以使用三分法快速逼近y的最优值，三分法模板。

时间复杂度:O(Tlogn)

知识点：三分

我们给大家整理了USACO竞赛10年试题精选带源代码真题，欢迎同学们和家长咨询网站客服~

USACO竞赛培训

USACO竞赛开设班型有USACO基础班、USACO铜升银、USACO银升金、USACO金升铂金多种班型，满足不同同学们的需求，助力同学们顺利通过USACO各级别比赛。

USACO基础班：计算机编程刚入门，语言基础薄弱，无比赛经验计划申请计算机专业学生。

USACO铜升银班：至少会一门计算机编程语言(推荐C++)，算法基础较一般，有一定比赛经验。

USACO银升金班：有完善计算机编程语言基础，有入门算法经验，一定比赛经验，如NOIP，USACO银组晋级。

课程类型：精品小班 / 一对一

授课模式：线上线下同步开课，可回放不断学习。

授课语言：中英双语教学 / 纯英文授课

目前犀牛国际已在上海、北京、广州、深圳、苏州、杭州、南京、武汉、合肥、青岛、成都、无锡等多个城市开设校区，致力于为准留学生家庭提供全方位升学服务。