2024年USACO競賽1月月賽白銀組和黃金組考情分析~

1題

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

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

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

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

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

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

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

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

2題

以房間1為根節(jié)點(diǎn)的樹。每次traversal相當(dāng)于從根出發(fā)，沿著父子關(guān)系一直走，一個traversal的終點(diǎn)一定是一個葉節(jié)點(diǎn)，因此最小的traversal數(shù)必定為葉節(jié)點(diǎn)數(shù)量，可以用dfs得到，假設(shè)這個數(shù)量是k。

可以用樹上DP來記錄每個節(jié)點(diǎn)的子樹擁有的葉節(jié)點(diǎn)數(shù)量，狀態(tài)轉(zhuǎn)移方程為dp[fa] += dp[child],則dp[1]就是整棵樹擁有的葉節(jié)點(diǎn)數(shù)量

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

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

potion[1]就是本題答案。

3題

抽屜原理+同余性質(zhì)

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

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

1題

考察算法：二分，觀察性質(zhì)

首先假設(shè)當(dāng)前在x軸朝向上行走，什么時候會轉(zhuǎn)向到y(tǒng)軸?

我們發(fā)現(xiàn)當(dāng)且僅當(dāng)當(dāng)前道路距離下一條道路是奇數(shù)距離的時候會轉(zhuǎn)向

于是我們可以考慮去二分轉(zhuǎn)向的次數(shù)，計(jì)算出在當(dāng)前轉(zhuǎn)向次數(shù)下運(yùn)動的距離，判斷它是否小于等于題目給出的運(yùn)動距離

代碼實(shí)現(xiàn)較為復(fù)雜，需要注意細(xì)節(jié)

時間復(fù)雜度: $O((n+q)*log)

2題

考察算法：動態(tài)規(guī)劃

和銀組第一題類似

定義$i$這個位置是前綴最大值當(dāng)且僅當(dāng)$a[i]>a[j]$ (for all $1\le j

我們會發(fā)現(xiàn)對于某個$(a[i],h[i])$相當(dāng)于要求$[a[i]+1,h[i]-1]$這一段不能是前綴最大值，$h[i]$這個位置必須是前綴最大值

最終我們將相同情況的序列合并在一起，那么就是有最多$3*Q$段的序列(每一段內(nèi)部要么要求一定是前綴最大值/一定不是前綴最大值/沒有要求)，求最終合法的方案數(shù)

定義$dp[i][j]$代表當(dāng)前考慮到前$i$段數(shù)，選的數(shù)的最大值是$j$的方案數(shù)

假設(shè)當(dāng)前這一段序列長度為$len$

當(dāng)一定是前綴最大值時:

$dp[i][j]=\sum_{k=1}^{j-1} dp[i-1][k]$

當(dāng)一定不是前綴最大值時:

$dp[i][j]=dp[i-1][j]*j^{len}$

當(dāng)沒有要求時：

$dp[i][j]=dp[i-1][j]j^{len} + \sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

時間復(fù)雜度: $O(qclog)$

3題

考察算法：二分

注意到分給Bessie自己的數(shù)越多答案相應(yīng)的會越大，但是會越容易滿足題目限制

所以我們考慮去二分 分給Bessie的個數(shù)$mid$

那么它們分別被加入序列的時間就是$mid, mid + (mid-1) ,... , mid+...+1$

顯然我們比較希望盡量靠后的數(shù)能被加入到Bessie的序列中，所以對于每一個加入序列的時間我們可以貪心的去找到第一個大于當(dāng)前時間且沒有被插入到序列中的數(shù)，將它插入到序列中

這個過程可以用類似于雙指針的思想來優(yōu)化

最終$min(數(shù)字最大值,mid*(mid+1)/2)$就是我們的答案

時間復(fù)雜度: $O(n*log)$