2023-24USACO計算機競賽第一次月考題目出爐！

2023-2024年USACO計算機競賽第一場月賽賽題出爐！讓我們(men) 一起來了解一下吧~

USACO 2023 DECEMBER CONTEST

BRONZE（銅級）

第一題糖果盛宴

題目描述:

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

按照它們(men) 在輸入中的順序，FJ計劃將甘蔗糖一根接一根地喂給奶牛。為(wei) 了給奶牛喂甘蔗糖，他會(hui) 把甘蔗糖掛起來，這樣甘蔗糖一開始就剛好碰到地麵。然後，奶牛將按照輸入的順序一頭接一頭地排隊，走到甘蔗糖前，每頭牛都吃到自己的高度（因為(wei) 它們(men) 不能再高了）。即使在奶牛吃掉糖果棒的底部後，糖果棒也會(hui) 懸掛在最初設置的位置，不會(hui) 下降到地麵。

如果甘蔗的底部已經超過奶牛的高度，那麽(me) 奶牛在輪到它的時候可能什麽(me) 都不吃。輪到每頭牛後，奶牛的身高會(hui) 根據它們(men) 吃了多少單位的甘蔗糖而增加，農(nong) 民約翰掛上下一根甘蔗糖，奶牛再次重複這個(ge) 過程（第一頭牛再次成為(wei) 第一個(ge) 開始吃下一根拐杖糖的人）。

第二題感染奶牛追蹤

題目描述:

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

最初，一些奶牛開始被感染。每天晚上，受感染的奶牛都會(hui) 將疾病傳(chuan) 播給左右兩(liang) 側(ce) 的奶牛（如果存在的話）。一旦奶牛被感染，它就會(hui) 繼續被感染。

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

第三題Farmer John Actually Farms

題目描述:

農(nong) 民約翰正在種植N（1≤N≤2·10^5)他的農(nong) 場裏種著蘆筍！然而，他的一些植物有遺傳(chuan) 差異，所以有些植物會(hui) 比其他植物生長得更快。i的初始高度

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

第th種植物生長ai英寸。

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

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

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

USACO 2023 DECEMBER CONTEST

SILVER（銀級）

第一題Bovine Acrobatics

題目描述:

農(nong) 場主約翰決(jue) 定讓他的奶牛表演一些雜技！首先，約翰稱了一下他的奶牛，發現它們(men) 有 N（1≤N≤2⋅10*5）個(ge) 不同的重量。特別是，對於(yu) 每個(ge) i∈[1,N]，他的牛中有 ai 重量為(wei) wi（1≤ai≤109,1≤wi≤109）。

他最受歡迎的絕技是讓奶牛組成平衡塔。塔是一連串的奶牛，每頭奶牛都疊在下一頭奶牛的上麵。如果每頭牛與(yu) 正上方的牛的重量至少比正上方牛的重量大 K（1≤K≤109），那麽(me) 這個(ge) 塔就是平衡的。任何一頭牛最多隻能成為(wei) 一個(ge) 平衡塔的一部分。

如果 FJ 想創建最多 M 個(ge) （1≤M≤109）平衡的牛塔，那麽(me) 最多有多少頭牛可以成為(wei) 某個(ge) 牛塔的一部分？

第二題Cycle Correspondence

題目描述:

農(nong) 場主約翰有 N 個(ge) 穀倉(cang) （3 <= N <= 5.105），其中有 K（3 <= K <= N）對不同的穀倉(cang) 相連。

首先，安娜貝爾給每個(ge) 穀倉(cang) 分配一個(ge) 範圍為(wei) [1，N]的不同整數標簽，並觀察到標簽為(wei) a1...ak 的穀倉(cang) 依次循環連接。也就是說，在所有 1 <= i < K 的情況下，穀倉(cang) ai 和 a(i+1) 是相連的，穀倉(cang) ak 和 a1 也是相連的。接下來，貝西還為(wei) 每個(ge) 穀倉(cang) 分配了一個(ge) 範圍為(wei) [1，N]的不同整數標簽，並觀察到標簽為(wei) b1，...bk 的穀倉(cang) 依次連接成一個(ge) 循環。所有 bi 都是不同的。

安娜貝爾和貝西給某些（可能沒有或全部）穀倉(cang) 分配了相同的標簽。計算被安娜貝爾和貝西賦予相同標簽的穀倉(cang) 的最大可能數目。

第三題Target Practice

題目描述:

貝西是一個(ge) 機器人，也叫牛伯格。它在一條數字線上，試圖射中一係列位於(yu) 不同位置的 T（1≤T≤105）目標。貝西從(cong) 位置 0 開始，執行一串 C（1≤C≤105）指令，每個(ge) 指令都是 L、F 或 R：

L: 貝西向左移動一個(ge) 單位。

R：貝西向右移動一個(ge) 單位。

F: 貝西開火。如果貝西當前位置有目標，則該目標會(hui) 被擊中並摧毀，且無法再次擊中。

如果允許在貝西開始執行命令之前將字符串中的一個(ge) 命令改為(wei) 另一個(ge) 命令，那麽(me) 貝西最多可以擊中多少個(ge) 目標？

USACO 2023 DECEMBER CONTEST

GOLD（金級）

第一題飛行路線

題意:

給定n個(ge) 機場，編號1-n，約定隻有小的數字到大的數字有航班，而且兩(liang) 點之間最多隻有一趟航班。告知每兩(liang) 個(ge) 機場之間總航班數量的奇偶性（奇數個(ge) 航班用1表示，偶數個(ge) 用0表示），計算兩(liang) 點之間有直達航班的數量。

第二題Cycle Correspondence

題意:

給定一個(ge) n個(ge) 點m條邊的有向無環圖（DAG)，計算從(cong) 每個(ge) 點出發最長的鏈的長度和總長度。如果有多個(ge) 路徑長度都最大，取路徑上邊長序列字典序最小的鏈。

第三題Target Practice

題意:

有n個(ge) 穀倉(cang) ，給定每個(ge) 穀倉(cang) 的位置，現要把所有穀倉(cang) 的草都運送到一個(ge) 穀倉(cang) y。運送草的代價(jia) 是y左邊的穀倉(cang) x的代價(jia) 是a*(y-x), y右邊的穀倉(cang) x的代價(jia) 是b*(x-y)。給q次查詢，每次輸入a和b的值，求最小的運輸總代價(jia) 。

USACO什麽(me) 學生能參加？

USACO競賽適合對計算機編程感興(xing) 趣的學生或者要申請計算機專(zhuan) 業(ye) 的學生，適合任意年級的中學生參加。

（小學生也可以參加；即使是高三學生，也可以參加12月的比賽）

官方網站：https://www.usaco.org/

你是否適合參加USACO競賽？

1、興(xing) 趣是最重要的

從(cong) USACO的初階到高階賽，需要進行反複、大量的訓練。需要確認自己是否對每周5-8小時的算法訓練能夠持續保持興(xing) 趣和熱情。

2.數學基礎非常必要

在編程的世界中，有時候思維比代碼本身更為(wei) 重要。

雖然數學和編程有本質上的區別，但它們(men) 之間存在著緊密的聯係：數學幫助我們(men) 按步驟完成計算，而編程幫助我們(men) 實現每個(ge) 計算步驟。

編程的基礎是建立在數學之上的。例如，樹、圖、堆等數據結構以及貪心算法、動態規劃等算法都需要應用數學思維和方法。

學好編程需要打好數學基礎，包括：

計數能力：在for循環中經常用到，類似小學數學的知識。

數字的加減乘除：每種編程語言都內(nei) 置支持，不需要手動計算。

餘(yu) 數和模運算：偶爾會(hui) 用到。

集合運算：交集、並集、差集，編程中用到的不多。

布爾運算：AND、OR等邏輯運算。

各種進製：二進製、十進製、十六進製等。

USACO不同級別難度如何？

USACO競賽根據編程技能水平劃分為(wei) 四個(ge) 級別：銅級、銀級、金級和鉑金級。

新注冊(ce) 的選手從(cong) 銅級開始，需要在規定的時間內(nei) 完成三道題目，每個(ge) 級別的題目均為(wei) 三道，如果通過則可以晉級到更高級別。

青銅級別：

首次參加USACO競賽的學生都屬於(yu) 青銅級別，隻要注冊(ce) USACO賬號即為(wei) 銅級。

難度等級：適用於(yu) 剛學會(hui) 編程的學生，需要掌握基本的排序和二進製搜索等概念，但沒有算法方麵的培訓。在這個(ge) 級別，學生需要能夠解釋一個(ge) 編程問題，並能夠用基本的算法和邏輯將自己的想法轉化為(wei) 代碼。

白銀級別：

通過銅級比賽的選手可以參加白銀級別。

難度等級：它涉及到遞歸搜索、貪心算法等基本的問題求解技術，還需要了解基礎的數據結構，並會(hui) 考察效率問題。從(cong) 白銀級別開始，選手需要尋找更好的算法來確保程序在規定時間內(nei) 運行完畢。

黃金級別：

通過白銀級比賽的選手可以參加黃金級別。

難度等級：需要具備一定的算法基礎，理解一些抽象的方法，例如最短路徑、動態規劃等，並對數據結構有較深的了解。

白金級別：

通過黃金級比賽的選手可以參加白金級別。

難度等級：需要具備較高的編程基礎，對算法有深入了解，能解決(jue) 複雜問題、開放問題。題目複合多種算法，還會(hui) 涉及高難度輔助算法，不但思維難度大，編碼工作量也在加大。