2024年1月usaco競賽銅組&銀組真題題目+分析

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

USACO

USACO 2023 DECEMBER CONTEST

BRONZE（銅級）

第一題

題目描述:

農(nong) 夫約翰有一項重要的任務-弄清楚為(wei) 他的奶牛買(mai) 什麽(me) 類型的幹草。

農(nong) 夫約翰的 N頭牛(2≤N≤10)從(cong) 1到N編號,每頭牛隻喜歡一種幹草hi(1≤ hi

≤N)。他希望所有的奶牛都喜歡同一種幹草。

為(wei) 了實現這一點，農(nong) 民約翰可以舉(ju) 辦小組會(hui) 議。小組會(hui) 議會(hui) 將一段連續的編號的奶牛聚集在一起開會(hui) ，他們(men) 的編號為(wei) 到i到j。在小組中如果有一種幹草超過一半的奶牛喜歡，那麽(me) 在小組會(hui) 議結束後，該小組的所有的奶牛都喜歡這種幹草。如果沒有這種幹草，那麽(me) 沒有奶牛改變它們(men) 喜歡的幹草。例如，在由16頭奶牛組成的小組中，其中9頭或更多的奶牛需要具有相同的幹草偏好，才能使其餘(yu) 的奶牛改變偏好。

農(nong) 夫約翰想知道哪種幹草能被所有的奶牛喜歡。他一次隻能舉(ju) 辦一個(ge) 小組會(hui) 議，但他可以多次舉(ju) 辦會(hui) 議，讓所有的奶牛都喜歡同一種幹草。

題目解析：

對確定的目標數，顯然做其他數為(wei) 眾(zhong) 數的操作不優(you) 。可證能達到目標當且僅(jin) 當已經有兩(liang) 個(ge) 目標數相鄰或可以做一次以它為(wei) 眾(zhong) 數的操作（做完此操作後逐一向左右拓展即可）。

這樣的操作若存在，總可通過取數更多的一半區間直到長度不超過3。所以隻要判斷有沒有長度為(wei) 3的區間以目標數為(wei) 眾(zhong) 數。

 

 

第二題

題目描述:

貝西已經掌握了變成炮彈的藝術，並沿著長度為(wei) N(1≤N≤10的5次方)的數軸從(cong) 左到右彈跳，位置為(wei) 1,2,.,N。她從(cong) 某個(ge) 整數位置S(1≤S≤N)開始向右彈跳，起始能量為(wei) 1。如果貝西的能量是k，她的下一次彈跳將在距離她當前位置前方k處。從(cong) 1到N的每個(ge) 整數位置要麽(me) 是靶子，要麽(me) 是跳板。每個(ge) 目標和跳板都有一個(ge) 範圍為(wei) 0到N的整數值。一個(ge) 權值為(wei) v的跳板會(hui) 使貝西的能量增加v，並使她的方向反轉。如果落在一個(ge) 權值為(wei) v的靶子上時貝西的能量至少為(wei) v，那麽(me) 它就會(hui) 被打破。落在一個(ge) 靶子上並不會(hui) 改變貝西的能量或方向。破碎的靶子將保持破碎狀態，貝西仍然可以在不改變力量或方向的情況下彈跳。

如果貝西可以彈跳無限長的時間或直到她離開數軸，她會(hui) 打破多少個(ge) 靶子?

如果貝西從(cong) 一個(ge) 她能打破的靶子開始跳躍，它就會(hui) 立刻被打破。類似地，如果貝西從(cong) 一個(ge) 跳板開始跳躍，這個(ge) 跳板的效果將在她第一次跳躍之前生效。

題目解析:

模擬，若同一個(ge) 跳板兩(liang) 次被同一個(ge) 力度跳到，可證以後會(hui) 循環並不會(hui) 有新的破碎。因此力量不變時最多跳一個(ge) 來回，求和為(wei) nlogn。

 

 

第三題

題目描述:

農(nong) 夫約翰有N(1≤N≤2*10的5次方)塊草地分布在一條直線上，其中第i塊草地的細菌水平與(yu) 健康草地的細菌水平相差ai(-10的15次方≤ aj≤10的15次方)，例如，如果ai=3，那麽(me) 第i塊草地的細菌水平低於(yu) 正常水平，並且需要添加3個(ge) 額外的細菌單位才能將其提高到健康的水平。

農(nong) 民約翰想要確保每一片草地都被清理幹淨，使細菌含量達到健康水平。方便的是，他有兩(liang) 種牌子的農(nong) 藥可以噴灑在他的田地上，一種會(hui) 增加細菌，另一種會(hui) 去除細菌。當農(nong) 民約翰噴灑兩(liang) 種農(nong) 藥時，他站在第 N塊草地上(最右邊的一塊)，並為(wei) 他的噴霧器選擇功率等級L(1≤L≤N)。

噴霧器對農(nong) 民約翰附近的草地影響最大，離得越遠效果越小。如果農(nong) 民約翰選擇了添加細菌的農(nong) 藥，那麽(me) L個(ge) 單位的細菌將被添加到草地N中，L-1個(ge) 細菌單位添加到草地N-1中，L-2個(ge) 細菌單位添加到草地 N -2中，以此類推。草地1.....N-L不會(hui) 接收到細菌，因為(wei) 噴霧器沒有設置足夠的功率去噴灑它們(men) 。同樣，如果農(nong) 民約翰選擇了除菌的農(nong) 藥，那麽(me) 從(cong) 草地N中去除L個(ge) 單位的細菌，從(cong) 草地N-1中去除L-1個(ge) 單位的細菌，以此類推。同樣的，草地1......N-L不會(hui) 受到影響。

你需要找出農(nong) 夫約翰必須使用噴霧器的最少次數，使得每片草地上的細菌都達到健康草地的水平。可以保證答案不超過 10的9次方。

題目解析：

考察差分 bi=ai-a(i-1)，其中a0=0和原列一一對應。操作為(wei) 將b的一個(ge) 後綴同時加減1。可以再差分得到每個(ge) 後綴應該修改多少。

USACO

USACO 2023 DECEMBER CONTEST

SILVER（銀級）

第一題

 

題目解析:

有q對(x,y)的輸入，每對表示前1~x個(ge) 數右邊第一個(ge) 比它們(men) 大的數必須在下標為(wei) y的位置，這

句話還有一個(ge) 隱藏含義(yi) 就是第x+1到第y-1個(ge) 數必須比前1~x個(ge) 數的最大值要小，即第y個(ge) 數

比前y-1個(ge) 數都要大(代碼中稱為(wei) 前綴最大值)。用一個(ge) 前綴和數組pre_max[i]表示前i個(ge) 數中的

最大值，則a[y]至少為(wei) pre_max[y-1]+1。

現在從(cong) 左往右遍曆a[N]，分類討論每一個(ge) a[i]的情況：

1.a[i]==0且位置i是前綴最大值，令a[i]=pre_max[y-1]+1

2.a[i]==0且不是前綴最大值，根據貪心思路令a[i]=1（字典序最小）

3.a[i]不為(wei) 0，是第x+1到第y-1個(ge) 數的其中一個(ge) ，但是比前x個(ge) 數要大，破壞了前綴最大

值的要求，此時需要把之前的某個(ge) 能改的值提高為(wei) a[i]

對全部a[N]修改完畢後，再重新for循環掃描一遍看看新的a[N]有沒有衝(chong) 突，有衝(chong) 突輸出-1

注意事項：這題有T個(ge) 測試，每個(ge) 輸出最後不能帶空格

 

 

第二題

題目解析:

以房間1為(wei) 根節點的樹。每次traversal相當於(yu) 從(cong) 根出發，沿著父子關(guan) 係一直走，一個(ge) traversal

的終點一定是一個(ge) 葉節點，因此最小的traversal數必定為(wei) 葉節點數量，可以用dfs得到，假設

這個(ge) 數量是k。可以用樹上DP來記錄每個(ge) 節點的子樹擁有的葉節點數量，狀態轉移方程為(wei)

dp[fa]+=dp[child],則dp[1]就是整棵樹擁有的葉節點數量

此時來看題目對potion的描述，每次traversal會(hui) 在一個(ge) 節點生成一個(ge) potion，下一次traversal

前消失，而我們(men) 隻會(hui) 有k個(ge) (即dp[1]個(ge) )traversal。因此實際上隻需要考慮前k個(ge) potion。而由

於(yu) potion是依靠traversal獲取的，因此potion和traversal,也就是葉節點，是一對一綁定的。

假設我們(men) 目前在某個(ge) 節點p，從(cong) 點p出發獲得的potion數量不會(hui) 超過點p的子樹擁有的葉節

點數量。我們(men) 再用一個(ge) 樹上DP，potion[p]表示點p的子樹擁有的potion數量，狀態轉移方程

為(wei) potion[fa]+=potion[child]。統計完畢後再令potion[p]=min(potion[p],dp[p])。

最終potion[1]就是本題答案。

第三題

題目描述:

題目等價(jia) 於(yu) N個(ge) 數除以L最多隻有3個(ge) 不同的餘(yu) 數，根據抽屜原理，任意選擇4個(ge) 不同的數 ，必定至少有兩(liang) 個(ge) 數a[i]和a[j]除以L的餘(yu) 數相同(即模L同餘(yu) )。由同餘(yu) 的基本性質可知abs(a[i]-a[j])必定能被L整除。

因此本題隻需要從(cong) a[N]中任選4個(ge) 不同的數，枚舉(ju) 它們(men) 的兩(liang) 兩(liang) 差值(一共有 = 6 種)，對這6個(ge) 數，枚舉(ju) 它們(men) 的所有因子fac，進行檢驗（看看a[1]到a[N]除以fac是不是最多隻有3個(ge) 餘(yu) 數），符合要求則令ans+=fac。

對於(yu) 0經驗的學生如何備賽？

自學是一個(ge) 很艱難和緩慢的過程，計算機學習(xi) 中涉及到大量的軟硬件問題，對於(yu) 沒有基礎的同學來說，很容易在自學過程中放棄或者偏離正確的學習(xi) 方向。

我們(men) 的課程會(hui) 幫同學們(men) 打好編程基礎，根據學生特點和學習(xi) 需求定製課程計劃，讓同學循序漸進的學習(xi) ，帶領同學們(men) 突破題目的難點。

USACO備賽課程

*僅(jin) 供參考，可靈活調整