USACO競賽真題解析及培訓(xùn)輔導(dǎo)課程安排~

USACO競賽考什么?考試內(nèi)容包含什么?歷年考試真題資料及培訓(xùn)輔導(dǎo)課程安排，為大家簡單的分析以下，方便大家掌握USACO競賽的詳細(xì)內(nèi)容，歡迎咨詢網(wǎng)站客服了解~

2023-2024年新賽季USACO競賽12月月賽已經(jīng)落幕，12月月賽都考察哪些知識點(diǎn)，我們對USACO青銅、白銀和黃金組別比賽進(jìn)行考情分析，供同學(xué)們參考。

12月USACO競賽青銅組解析

Candy Cane Feast

農(nóng)夫約翰的奶牛很愛吃甜食，它們特別喜歡吃甘蔗糖!FJ有N頭牛，每頭牛都有一定的初始身高，他想喂它們M每根也有不同高度(1≤N，M≤2·10^5)。

按照它們在輸入中的順序，F(xiàn)J計(jì)劃將甘蔗糖一根接一根地喂給奶牛。為了給奶牛喂甘蔗糖，他會(huì)把甘蔗糖掛起來，這樣甘蔗糖一開始就剛好碰到地面。然后，奶牛將按照輸入的順序一頭接一頭地排隊(duì)，走到甘蔗糖前，每頭牛都吃到自己的高度(因?yàn)樗鼈儾荒茉俑吡?。即使在奶牛吃掉糖果棒的底部后，糖果棒也會(huì)懸掛在最初設(shè)置的位置，不會(huì)下降到地面。

如果甘蔗的底部已經(jīng)超過奶牛的高度，那么奶牛在輪到它的時(shí)候可能什么都不吃。輪到每頭牛后，奶牛的身高會(huì)根據(jù)它們吃了多少單位的甘蔗糖而增加，農(nóng)民約翰掛上下一根甘蔗糖，奶牛再次重復(fù)這個(gè)過程(第一頭牛再次成為第一個(gè)開始吃下一根拐杖糖的人)。

試題解析：

這個(gè)題是個(gè)有意思的暴力問題，同學(xué)們考慮一個(gè)子問題：

一個(gè)數(shù)初始是1.每一次操作是讓它乘2.要求這個(gè)數(shù)小于等于n，求最多能操作多少次

這個(gè)問題的答案比較顯然是log2n次

那考慮當(dāng)前的問題，考慮第一頭牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22;如果牛比甘蔗高，此輪吃甘蔗結(jié)束。

所以這一題直接暴力模擬做到甘蔗被吃完復(fù)雜度就是對的。

時(shí)間復(fù)雜度：O(nlog2n)

知識點(diǎn)：暴力，時(shí)間復(fù)雜度分析

Cowntact Tracing2

農(nóng)夫約翰有N排成一行的奶牛(1≤N≤3·10^5)。不幸的是，有一種疾病正在蔓延。

最初，一些奶牛開始被感染。每天晚上，受感染的奶牛都會(huì)將疾病傳播給左右兩側(cè)的奶牛(如果存在的話)。一旦奶牛被感染，它就會(huì)繼續(xù)被感染。

經(jīng)過幾個(gè)晚上，農(nóng)夫約翰意識到問題已經(jīng)失控，所以他對奶牛進(jìn)行了測試，以確定誰生病了。找出可能開始患病的奶牛的最小數(shù)量。

試題解析：

首先我們可以根據(jù)輸入計(jì)算出1的擴(kuò)散時(shí)間最長是多少(時(shí)間越長需要的初始點(diǎn)就越少)

注意邊界和中間的計(jì)算方式不同，中間擴(kuò)散的結(jié)果是1.3.5....,2*n-1.而邊界是1.2.3....,n$因?yàn)檫吔缈梢苑旁谧罱锹溟_始)

計(jì)算出最長擴(kuò)散時(shí)間max_time后我們就可以對每一段連續(xù)為1計(jì)算初始最少需要放幾個(gè)1 : len = 2*max_time+1 (len代表連續(xù)1個(gè)數(shù))

最終將答案相加即可

時(shí)間復(fù)雜度：O(n)

知識點(diǎn)：貪心，邊界條件判斷

Farmer John Actually Farms

農(nóng)民約翰正在種植N(1≤N≤2·10^5)他的農(nóng)場里種著蘆筍!然而，他的一些植物有遺傳差異，所以有些植物會(huì)比其他植物生長得更快。

i的初始高度

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

第th種植物生長ai英寸。

FJ比其他植物更喜歡他的一些植物，他希望一些特定的植物比其他植物高。他給你一組不同的值t1.…，tN包含0中的所有整數(shù)至N−1

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

找到最小天數(shù)，以便FJ的要求得到滿足，或者確定這是不可能的。

試題解析

考慮根據(jù)最終的排序結(jié)果來確定有多少條件，容易發(fā)現(xiàn)其實(shí)只有$n-1$個(gè)有效的不等式，即第1個(gè)小于第2個(gè)，第2個(gè)小于第3個(gè)，...

根據(jù)不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t對應(yīng)的范圍

最終對于所有不等式結(jié)果求出交集，如果不為空就輸出最小值，否則輸出-1

時(shí)間復(fù)雜度：O(n)

知識點(diǎn)：簡單數(shù)學(xué)

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?

考情解析

考慮從前往后貪心，首先假設(shè)每個(gè)塔最下面的數(shù)都是負(fù)無窮，然后從小到大把每一個(gè)數(shù)加入塔中。考慮加入塔中的過程，每一次我們都把這個(gè)數(shù)加入到之前塔頂數(shù)最小的位置，如果此時(shí)不能插入，說明這個(gè)數(shù)沒法繼續(xù)插入了。由于每種數(shù)有很多個(gè)，一個(gè)個(gè)插入時(shí)間復(fù)雜度會(huì)過大，考慮將每種數(shù)作為一個(gè)整體插入。在當(dāng)前這種數(shù)插入在另一種數(shù)的上方的時(shí)候，要么另一種數(shù)完全覆蓋，要么當(dāng)前這種數(shù)被用完，所以每種數(shù)最多被考慮一次。

時(shí)間復(fù)雜度：O(nlogn)

知識點(diǎn)：貪心，排序

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最多有多少元素相同其實(shí)就是看兩個(gè)環(huán)最多能有多少個(gè)位置能匹配。

匹配的定義是：環(huán)A和環(huán)B按某種順序按位匹配后相同數(shù)字最多是多少個(gè)。

我們可以考慮讓A環(huán)不動(dòng)，B環(huán)循環(huán)右移，對于每一種字符計(jì)算出需要將環(huán)循環(huán)右移多少步得到，最終查詢哪個(gè)步數(shù)出現(xiàn)次數(shù)最多即可。

注意我們還要考慮環(huán)外點(diǎn)最多有多少匹配：這個(gè)比較簡單，我們只需要統(tǒng)計(jì)剩下元素里有多少種類A與B是相同的即可。

時(shí)間復(fù)雜度：O(n)

知識點(diǎn)：環(huán)，計(jì)數(shù)

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時(shí)可以擊中多少個(gè)目標(biāo)。答案在change[1]-change[5]。再用hit[1-5][位置]記錄每個(gè)位置被擊中了多少次。

然后i從左往右一位位求i之前已經(jīng)固定，i改變以后，能擊中多少次;

這樣求完以后只需要把第i位固定帶來的影響，更新到change和hit里就可以了。

i從左往右固定過程中，如果這一位是L和R只影響位置p;

但如果這一位是F，那么固定以后，就要更新hit里的次數(shù)。因?yàn)樗?2 -1 +1 +2都不可能發(fā)生了。

所以更新了兩部分內(nèi)容。

1. 當(dāng)前位置p，如果之后的F因?yàn)?2 -1 +1 +2擊中過它，現(xiàn)在應(yīng)該i已經(jīng)固定，它一定會(huì)被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0.change對應(yīng)更新。

2. 當(dāng)前位置p，-2 -1 +1 +2以后的位置的hit數(shù)減少1次，如果減到0就更新change

最終就是，確定會(huì)擊中的數(shù)量cnt，和change數(shù)組維護(hù)的i之后的-2 -1 +1 +2以后的4種不同擊中數(shù)量，根據(jù)L->R R->L之類的變化情況相加。

時(shí)間復(fù)雜度: O(n)

知識點(diǎ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路徑為奇數(shù)，說明i到i+1有邊，反之沒有。

考慮任意點(diǎn)i和j的時(shí)候，只需要利用區(qū)間dp的思想計(jì)算出i到j(luò)除了直接到達(dá)的路徑有多少條，看一下是否滿足奇偶性即可。

時(shí)間復(fù)雜度:  O(n^3)

知識點(diǎn)：區(qū)間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，那么我們要求最長路的話就可以利用拓?fù)渑判?bfs來解決。

難點(diǎn)在于題目要求字典序最小，考慮如何快速比較兩條出邊的字典序大小

由于題目權(quán)值可以相同暴力走下去比較時(shí)間復(fù)雜度會(huì)被卡到$O(n^2)$

為了優(yōu)化比較過程，我們希望能夠快速得到兩個(gè)最長路相同的點(diǎn)他們之間的字典序關(guān)系。

所以我們可以動(dòng)態(tài)地對最長路相同的點(diǎn)的內(nèi)部做一個(gè)排序，比較的時(shí)候就只需要拿出之前維護(hù)好的排序結(jié)果去做判斷，判斷時(shí)間復(fù)雜度就可以做到O(1)

總時(shí)間復(fù)雜度：O(nlogn)

知識點(diǎn)：拓?fù)渑判?，字典?/p>

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：查詢的次數(shù)很多，可以考慮預(yù)處理，由于不需要頻繁修改區(qū)間，使用前綴和即可。

觀察2：題目保證數(shù)軸x1...xN上存在一個(gè)極小值點(diǎn)y，通過等式變形/反證法可以證明y必定為x1...xN中的一點(diǎn)，同時(shí)路徑總和f(y)是一個(gè)兩邊往中間遞減的單峰函數(shù)，可以使用三分法快速逼近y的最優(yōu)值，三分法模板。

時(shí)間復(fù)雜度:O(Tlogn)

知識點(diǎn)：三分

我們給大家整理了USACO競賽10年試題精選帶源代碼真題，歡迎同學(xué)們和家長咨詢網(wǎng)站客服~

USACO競賽培訓(xùn)

USACO競賽開設(shè)班型有USACO基礎(chǔ)班、USACO銅升銀、USACO銀升金、USACO金升鉑金多種班型，滿足不同同學(xué)們的需求，助力同學(xué)們順利通過USACO各級別比賽。

USACO基礎(chǔ)班：計(jì)算機(jī)編程剛?cè)腴T，語言基礎(chǔ)薄弱，無比賽經(jīng)驗(yàn)計(jì)劃申請計(jì)算機(jī)專業(yè)學(xué)生。

USACO銅升銀班：至少會(huì)一門計(jì)算機(jī)編程語言(推薦C++)，算法基礎(chǔ)較一般，有一定比賽經(jīng)驗(yàn)。

USACO銀升金班：有完善計(jì)算機(jī)編程語言基礎(chǔ)，有入門算法經(jīng)驗(yàn)，一定比賽經(jīng)驗(yàn)，如NOIP，USACO銀組晉級。

課程類型：精品小班 / 一對一

授課模式：線上線下同步開課，可回放不斷學(xué)習(xí)。

授課語言：中英雙語教學(xué) / 純英文授課

目前犀牛國際已在上海、北京、廣州、深圳、蘇州、杭州、南京、武漢、合肥、青島、成都、無錫等多個(gè)城市開設(shè)校區(qū)，致力于為準(zhǔn)留學(xué)生家庭提供全方位升學(xué)服務(wù)。