USACO銀組試題解析，不同年級USACO備考規(guī)劃介紹！

有q對(x,y)的輸入，每對表示前1~x個數(shù)右邊第一個比它們大的數(shù)必須在下標為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

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

以房間1為根節(jié)點的樹。每次traversal相當于從根出發(fā)，沿著父子關(guān)系一直走，一個traversal

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

這個數(shù)量是k?？梢杂脴渖螪P來記錄每個節(jié)點的子樹擁有的葉節(jié)點數(shù)量，狀態(tài)轉(zhuǎn)移方程為

dp[fa]+=dp[child],則dp[1]就是整棵樹擁有的葉節(jié)點數(shù)量

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

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

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

假設我們目前在某個節(jié)點p，從點p出發(fā)獲得的potion數(shù)量不會超過點p的子樹擁有的葉節(jié)

點數(shù)量。我們再用一個樹上DP，potion[p]表示點p的子樹擁有的potion數(shù)量，狀態(tài)轉(zhuǎn)移方程

為potion[fa]+=potion[child]。統(tǒng)計完畢后再令potion[p]=min(potion[p],dp[p])。

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

抽屜原理+同余性質(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，進行檢驗（看看a[1]到a[N]除以fac是不

是最多只有3個余數(shù)），符合要求則令ans+=fac。