Home » 國際競賽 » Details

2024年USACO1月月考題目出爐！白銀組別考情分析

Category: 國際競賽, 翰林嚴選, 計算機國際競賽 Date: 2024年2月4日下午4:42

USACO計算機編程競賽的1月月賽已經完美結束啦，這次沒有晉級到自己心儀級別的同學也不要著急，接下來可以等待2月的月賽！

1月月賽白銀組考了哪些內容？今天整理了1月USACO競賽白銀組別考情分析，希望對同學們接下來的USACO競賽備考有所幫助。

USACO 2024年1月白銀組別考情分析

第1題

有q對(x,y)的輸入，每對表示前1~x個數右邊第一個比它們大的數必須在下標為y的位置，這句話還有一個隱藏含義就是第x+1到第y-1個數必須比前1~x個數的最大值要小，即第y個數比前y-1個數都要大(代碼中稱為前綴最大值)。

用一個前綴和數組pre_max[i]表示前i個數中的最大值，則a[y]至少為pre_max[y-1]+1。

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

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

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

3.a[i]不為0，是第x+1到第y-1個數的其中一個，但是比前x個數要大，破壞了前綴最大值的要求，此時需要把之前的某個能改的值提高為a[i]

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

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

第2題

以房間1為根節點的樹。每次traversal相當于從根出發，沿著父子關系一直走，一個traversal的終點一定是一個葉節點，因此最小的traversal數必定為葉節點數量，可以用dfs得到，假設這個數量是k。

可以用樹上DP來記錄每個節點的子樹擁有的葉節點數量，狀態轉移方程為dp[fa] += dp[child],則dp[1]就是整棵樹擁有的葉節點數量

此時來看題目對potion的描述，每次traversal會在一個節點生成一個potion，下一次traversal前消失，而我們只會有k個(即dp[1]個)traversal。

因此實際上只需要考慮前k個potion。而由于potion是依靠traversal獲取的，因此potion和traversal,也就是葉節點，是一對一綁定的。假設我們目前在某個節點p，從點p出發獲得的potion數量不會超過點p的子樹擁有的葉節點數量。我們再用一個樹上DP，potion[p]表示點p的子樹擁有的potion數量，狀態轉移方程為potion[fa] += potion[child]。統計完畢后再令potion[p] = min(potion[p], dp[p])。

potion[1]就是本題答案。

第3題

抽屜原理+同余性質

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

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

USACO歷年真題及參考書，掃碼領取！【翰林提供報名指導服務】USACO歷年真題及參考書