1月USACO計算機競賽'金牌'解題分析！附備考資料領(lǐng)??！

01

Au1:

算法：二分，觀察性質(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ù)，計算出在當(dāng)前轉(zhuǎn)向次數(shù)下運動的距離，判斷它是否小于等于題目給出的運動距離

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

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

Au2:

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

和銀組第一題類似

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

我們會發(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)$

Au3:

算法：二分

注意到分給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)$

02