[USACO 2015 Gold] Trapped in the Haybales

作法：

這題的關鍵是：對於 [ i , i+1 ] 來說，如果他沒有辦法逃脫，那就代表存在 x <= i < i+1 <= y ，使得 min( s[ x ] , s[ y ] ) >= p[ y ] - p[ x ] ，其中 s 和 p 分別代表那堆的大小和位置。並且如果不存在這樣的 x 和 y 的話，就一定可以逃脫。所以我們按照大小由大到小排序，一個一個加入序列中，當在 x 被加入時，可以找出「以 x 為逃不出去區間的左端點的話，右端點至多可以沿伸到哪裡」( 因為已經按照大小由大到小排序，所以目前在序列裡面的堆的大小都 >= x 的，因此在上式中的 min( s[ x ] , s[ y ] ) 就會等於 s[ x ] ) 。所以我們必須要把 x 到最遠右端點之間都標記成不可逃脫，左端點也類似。而這裡就可以用個線段樹作，最後查詢如果一個位置有被標記，那就是不可逃脫的區間。

code :

[USACO 2015 Gold] Googol

作法：

我們要解決的就是這個子問題：給定一個子樹的根，求出這棵子樹的大小。首先當然要確定其中一邊子樹的大小，那麼就先對右子樹遞回下去，求出他的大小，假設為 p ，那麼左子樹的大小只有可能是 p 或 p+1 ，所以這時候又產生了另一種子問題：如果已知這個子樹的大小是 p 或 p+1 ，求出這棵子樹的大小。以數字舉例好了，如果 p = 9 ，那麼代表他左右子樹的大小和為 8 或 9 ，也就是兩個子樹的大小可能分別是 4 , 4 或是 5 , 4 ，所以我們只要判斷左子樹的大小是 4 還是 5 即可，就可以遞回下去處理了。

另外這題還得寫個大數QQ 不太會寫所以只好亂寫了一個。

code :

[USACO 2015 Gold] Censoring

作法：

蠻明顯是AC自動機的題目。先把輸入的所有不能出現的串建成AC自動機，對原始字串匹配，如果走到一個點是禁止的字串的話，假設這個字串的長度是 L ，那就往前退 L 步，代表把這個字串拔掉之後所走到的位置。

code :

[USACO 2015 Gold] Cow Hopscotch

作法：

記 dp[ i ][ j ] 代表從左上角開始，有多少種方法可以跳到 [ i ][ j ] 這格。假設現在要算第 i 排的所有位置的答案，那麼我們可以先預處理出 sum 陣列，其中 sum[ j ] = dp 表格中 ( 1 , 1 ) 和 ( i-1 , j ) 形成的矩形內的所有數的總和，那麼 dp[ i ][ j ] 的算法就是用 sum[ j-1 ] ，扣掉「( 1 , 1 ) 和 ( i-1 , j ) 形成的矩形內，和顏色和 [ i ][ j ] 相同的格子的數的總和」。因此一個作法就是直接對每個顏色都維護一個和 sum 一樣的前綴和陣列，大小和原圖的寬度一樣。但這樣顯然記憶體會不夠。事實上只要注意到，其實有很多直行根本就沒有某個顏色，那麼這一直行對這個顏色的總和值貢獻永遠是 0 ，因此對於每個顏色，我們的陣列的大小只需要開「有幾個直行有這個顏色」就夠了，並且把所有的直行位置都記錄起來，才能知道當前這個直行會對應到現在這個顏色屬於的前綴和陣列中的哪個位子。但每次做完一整排的答案之後還必須對所有的顏色重算一次前綴和，這樣太慢了，如果改成 BIT 就可以在每次 log n 的時間內修改，並且所有顏色的格子數總和為 n*m ，這樣複雜度就可以降到 O( n*m*logn ) 了。

code :

[USACO 2015 Gold] Grass Cownoisseur

作法；

這題簡單來說要問的是，給定一張有向圖，那麼把其中一條邊反向之後可以得到的 1 所在的SCC 大小最大為多少。首先對這張圖進行 SCC 縮點，變成了一張每個點都有點權的 DAG 。如果我們把 u -> v 的邊反向，那麼這時候的路徑就會是：從 1 所在的 SCC 開始，沿著 DAG 的邊走到 v 所在的 SCC ，然後跳到 u 所在的SCC，再走回 1 所在的 SCC 。於是我們對縮完點後的 DAG 的每個點先 dp 算出「從這個點走到 1 所在的 SCC ，經過的點權總和最大為多少」，還有「從 1 所在的 SCC 走到這個點，經過的點權總和最大為多少」，就可以知道任何一條邊被反向之後所得到的 SCC 大小為多少了。

code :

[USACO 2015 Gold] Moovie Mooving

作法：

明顯是位元DP。對於一個電影的集合，求出從0開始看完這些電影所花的最大時間為何，那麼因為他可以中途離場，這也就代表所有 <= 最大時間的時間點都可以是「剛看完這些電影的時間」，轉移的時候就挑最晚的可以看的電影轉移就可以了。

code :

[USACO 2015 Gold] Cow Rectangles

作法：

因為題目要求了在包含 H 最多的矩形中要求出面積最小的那個，所以假設我們現在已經找到最佳的矩形了，那麼這個矩形的上下左右四個邊界上一定都有給定的點，否則可以再往內縮得到更小的矩形。所以我們可以枚舉所求矩形的上下邊界的座標，只考慮落在上下邊界中的所有點，那麼問題就會轉換為一維的：找出最長的線段使得上面都是 H 。而這只要預先對點集排序之後 O( n ) 掃過一次就好了。

code :

[USACO 2014 Gold] Cow Jog

作法：

考慮好幾隻被分在同一個跑道上的牛，如果把他們按照起始位置排序，那麼他們在跑的過程中完全沒有交換順序(沒有超車)，否則就會相交，也就是他們的終點位置是嚴格遞增的。所以如果考慮先把每隻牛按照起始位置排序，那麼問題就會變成要把終點位置劃分成最少個LIS，這樣就轉換為經典題了。

code :

[USACO 2014 Gold] Marathon

作法：

記 dis( i , j ) 代表第 i 個點到第 j 個點的距離，那麼略過第 x 個點的話會讓總距離減少 dis( x-1 , x ) + dis( x , x+1 ) - dis( x-1 , x+1 ) ，並且從 L 走到 R 的原始距離就是 dis( L , L+1 ) + ... + dis( R-1 , R ) ，而這些東西都擁有可以區間合併的性質，所以只要建一顆線段樹，讓他可以查詢區間的相鄰點距離和，還有這個區間中的「dis( x-1 , x ) + dis( x , x+1 ) - dis( x-1 , x+1 ) 」 的最大值即可。

code :

[USACO 2014 Gold] Guard Mark

作法：

對於一個用牛疊成的塔，我們定義他的強度為：min{ 牛的強度 - 牛的實際負重 }，如果強度 >= 0 代表這座塔能夠疊起來，那麼只要DP出每個牛集合形成的塔最大強度是多少就可以了，每次枚舉哪隻牛當最底下的，那麼因為剩下的牛就是這個集合扣掉這隻牛，所以這隻牛的負重也確定了，就可以轉移到比較小的問題。

code :

[USACO 2014 Gold] Cow Optics

作法：

考慮從起點發射出去的光線，那麼新放的鏡子一定會落在這條光線上，否則就沒辦法改變這條光的行進路線了。於是這條光線打到新放的鏡子之後會走到終點，所以反過來看的話，就可以得到從終點往某一個方向發射出去的光線也會通過新放的鏡子，因此可以得到新放的鏡子的所有位置：把起點射出的光線路徑找出來，還有從終點射出的四個方向的路徑都找出來，然後求他們有幾個交點就可以了。

但實作上還蠻麻煩的，首先把問題拆成兩個部份，第一個是找出所有的路徑上的線段，第二個則是求出所有直的和橫的的線段有幾個交點。先看第二個部份，我們把所有直的線段的上下兩端點都看成一次事件，分別會把橫座標的這個位置的值+1或-1，然後從低到高考慮橫的線段，在作一條線段之前先把所有在他之前發生的事件都加進去，那麼目前這條橫的線段上的交點數就會是這條線段覆蓋到的區間上的數字總和，所以這裡可以先離散化之後用 BIT 求出答案。

第一個部份比較麻煩，首先我們要知道從一個點開始往某一個方向進行的光線會打到哪個點，而如果打不到任何鏡子的話就必須回傳一個足夠遠的點。這個部份可以用 map<int,vector<int>> 實作，對於每個 x 座標，可以紀錄有哪些點的 x 座標是他，並且把他們按照 y 座標大小排序，就可以對他二分搜了。 y 座標也同理。比較麻煩的是，由題目給的範測可以發現，在找從終點出發的四條光線的路徑的時候，有可能會產生循環，這代表我們還必須判斷：如果目前光線所在的點和他即將到達的點上，經過了光線的起點（也就是原始題目給的終點），那麼就要把新得到的點改成光線起點，然後趕快退出。另外一點則是有可能算到兩次一模一樣的路徑，而我的解決方法是當在取的路徑的時候，如果他返回了光線的原點，那就回傳他是從哪個方向回去的，並且標記已經走過了，這樣之後就不會再走到了。

對了還要注意到一點，就是 ( 0,0 ) 不能出現在終點發出的光線中，而避免這件事的方法就只要把 ( 0,0 ) 也當作已經放好的鏡子就好了，但如果新找到的點就是 ( 0,0 ) 的話也要 break 掉，因為他並不反射任何光線。

code :

[USACO 2014 Gold] Fair Photography

作法：

令 S[ i ][ j ] 代表第 i 種品種在前 j 隻牛裡面出現了幾隻，那麼如果 ( L , R ] 是一個滿足條件的區間，若且唯若：對於所有的品種 i ，要嘛 S[ i ][ L ] = S[ i ][ R ] ，要嘛 S[ i ][ R ] - S[ i ][ L ] = k ，其中 k 為一個不受 i 影響的定值。也就是如果我們考慮把 B 個前綴和包成一個 B 元數組，第 j 個數組的第 i 項就是 S[ i ][ j ] ，那麼我們就是要在這 n+1 個 B 元組裡面找兩個數組 P 和 Q ，使得存在一個 1~B 的子集 A， 滿足當 i ∈ A 時 P[ i ] = Q[ i ] + k ， i ∉ A 時 P[ i ] = Q[ i ] 。考慮對一個從「 B 元組和一個 1~B 的子集 A」 映射到 B 元組的函數 f ( P , A ) ，其中：

f ( P , A ) [ i ] = P[ i ] ，當 i ∉ A 。
f ( P , A ) [ i ] = P[ i ] - P[ k ] ，當 i ∈ A ，其中 k 是 A 中最小的數。

那麼可以得到，若 B 元組 P 和 Q 滿足題目的條件，那麼存在一個 A 使得 f( P , A ) = f( Q , A ) 。所以這樣就可以得到一個算法：枚舉所有的 A ，還有所求區間的右端點，每次將新的 B 元組關於 A 的 f 值加入一個查找表中，並且紀錄是在哪個位置出現這個數組的，然後查詢當前右端點的前綴和形成的 B 元組關於 A 的 f  值是否有出現在查找表裡面，有的話就代表找到了一個滿足條件的區間。但這個算法的複雜度會是 O( n * 2^B ) ，會TLE掉。

還要注意到一件事，就是當我們固定區間的右端點時，考慮左端點從這個點開始往左邊跑，會有一些新的品種進到這個區間中，而已經在區間內的品種不會不見，也就是對於一個右端點的所有符合條件的區間中，可能的 A 集合只有 B 種，所以可以只枚舉這 B 種就好了。所以我們的查找表就改成紀錄數組的 f 值，再加上他是用哪個 A 集合轉換過來的。另外同理可以有，對於一個左端點，最多也只有 B 種可能的 A 集合，所以以他為左端點時只要加入 B 個東西進入查找表即可。

一開始我查找表直接用 map< vector<int>,int > 寫，結果有兩筆測資一直TLE，後來改成自己寫 hash 才過，真是麻煩QQ。

code :

[USACO 2014 Gold] Counting Friends

作法：

USACO竟然會出現可圖化的裸題=ㄦ=，總之就是枚舉每個數，看把他拔掉然後O(n)看可不可行就好了。詳細可以參考這篇。

code :

[USACO 2014 Gold] Sabotage

作法：

原題要求的東西簡單來說就是：求出兩段不相交的前綴和後綴，使得他們合起來的平均值最小。而兩段分開的很不好算，所以如果把整個數列延長一倍，變成長為 2*n 的數列，使得 a_( i+n ) = a_i，這樣等於是要求出一段包含 a_n 和 a_( n+1 ) 的數列，使得平均值最短，而且長度不能超過 n-1 （題目說至少要砍掉一個數，也就是剩下的數至少要有 n-2 個）。不難看出這個問題和以下問題非常類似：給定一個數列，求出他的平均值最大的連續子數列，並且長度必須>=某個定值。這個問題的作法是考慮前綴和，加上DP斜率優化，這裡的問題也可以用很類似的方法做。

具體來說，首先當然是先求出前綴和，設前綴和陣列為 S[ i ] ，那麼現在就變成要求出兩個數 i , j 使得 i <= n-1 < n <= j ， j - i <= n-1 ，並且點 ( i , S[ i ] ) 到點 ( j , S[ j ] ) 的斜率越小越好。考慮按照右端點由大到小做，每次加入合法的新的左端點，並且在左端點的部份維護一個凹向下的點集，還有當前的最佳點，每次詢問時如果最佳點的右邊更好就讓他往右跑，直到不會更好的時候拿他去更新答案。

code :

[USACO 2014 Gold] The Lazy Cow

作法：

題目要問的東西簡單來說就是，給定平面上的一些點，每個點有它的價值，現在可以用一個斜45度的正方形去蓋他，問蓋到的最大價值。首先一樣可以用座標變換把他變為和坐標軸平行的正方形，只要考慮 ( x , y ) -> ( x-y , x+y ) 即可，所以現在問題變回找的是一個和坐標軸平行的正方形( 並且他的邊長會變為 2*k )。考慮把所有點按照 x 坐標由小到大排序，這樣就可以用雙指標轉換為一維問題了。具體來說，我們對每個 y 坐標都記錄取他的話可以獲得多少的價值，那麼當算到第 i 個點的時候，把他的價值加到他的位置上，並且把所有過期的點( x 坐標和第 i 個點差太多的點 )的價值減掉，然後詢問現在如果使用長度為 2*k 的線段蓋下去，可以蓋到的最大價值為何。而要處理這個問題，只要注意到：每次在一個點加上一個值的時候，會影響到的所有長為 2*k 的區間是連續的，也就是如果我們改成把長 2*k 的區間都看成點，這個點的權重就是這個區間裡的價值總和，那麼每次修改就會變成修改一個區間的權重，查詢就是查詢所有數的最大值，於是就可以用線段樹做了。

code :

[USACO 2014 Gold] Airplane Boarding

作法：

先看第 n 隻牛，他在時間 0 的時候位於 x=0 ，並且在時間 S[ n ] 時走到自己位置， S[ n ] + T[ n ] 時坐下。而這就帶給了第 n-1 隻牛一個限制：必須要等到時間為 S[ n ] +T[ n ] + 1 時他才有辦法走到 S[ n ] 。所以當我們處理每隻牛的時候，假設對這隻牛的限制為 ( a_1 , b_1 ) , ... , ( a_r , b_r ) ，其中 ( a , b ) 代表至少要等到 b 秒時才可以走到 a 位置，那麼這隻牛走到目的地的時間就會是： max{ b_i + ( S - a_i ) }，其中 a_i 滿足 a_i <= S 。也就是我們會需要查詢在所有第一個座標 <= S 的限制中， b - a 最大的數是多少。所以現在可以得到這樣的算法：按照 n ~ 1 的順序處理每隻牛，一開始的限制就只有 ( 0 , 0 ) ，然後對於每個正在處理的牛 i ，掃一遍目前所有的限制，把 a 值 <= S[ i ] 的限制們的 b-a 值拿去更新最大值，算出這隻牛坐好的時間 U[ i ] ，並且這會代表第 i-1 隻牛至少要等到 U[ i ] +1 才可以走到 S[ i ] ，也就是多把 ( S[ i ] , U[ i ] +1 ) 加入限制中。但還要注意到的是，如果 ( a , b ) 滿足 a <= S[ i ] ，代表第 i 隻牛至少要到時間 b 才可以走到 a 位置，那麼這件事對第 i-1 隻牛來說就會變成：他至少要到時間 b 才可以走到 a-1 位置，因為他會被第 i 隻牛擋住，而對於那些 a > S[ i ] 的限制們則不用更新。所以我們必須要在算完 i 的答案時，對所有 a <= S[ i ] 的限制們都更新一次，這樣就得到了 O(n^2) 的演算法。

至於要如何優化成O(nlogn) ，首先要注意到：如果有兩個限制 ( a , b ) 和 ( c , d ) ，滿足 c > a 且 d-c < b-a ，那麼 ( c , d ) 這個限制就廢掉了，因為當 c <= S[ i ] 時 a 必定也 <= S[ i ] ，他永遠不會比 ( a , b ) 更好，也就是在我們維護的限制們裡，當 a 遞增時 b-a 也是遞增的，所以每次加入一個新的限制 ( a , b ) 時要再把所有廢掉的 ( c , d ) 都砍掉。雖然這個觀察還是會得到O(n^2) 算法，但是這樣就會發現可以用 treap 維護所有的限制。使用分裂合併式的 treap ，並且對每個限制都記錄他的 a 值和 b-a 值，還有這棵子樹中 b-a 的最大值，而且我們會需要區間加值的動作，所以會需要再記個 tag 值。當要詢問的時候只要把 a <= S[ i ] 的那一部分切下來問問就好了，並且在砍掉不必要的 ( c , d ) 時，可以很方便的直接從剛剛切完得到的右子樹中，直接把 b-a 值太小的節點都切掉( 因為當 a 遞增時 b-a 也遞增，所以單看 b-a 的話他也還是一個treap )，並且在「對於 a<=S[ i ] 的限制，都把 a 值減一」的操作時只要對左子樹打個標記就好了，最後再把領個更新完的子樹黏起來即可。

code :

[USACO 2014 Gold] Cow Decathlon

作法：

如果不考慮 bonus 的話，就會變成基本的位元DP，設 dp[ i ] 代表已經派牛參加的運動集合為 i ，並且如果 i 的二進制中有 j 個 1 ，那麼就是前 j 隻牛參加 i 集合的運動所獲得的最大價值。而考慮 bonus 的話，我是先預處理出「在前 i 個運動中得到 j 分的話實際上可以獲得幾分」，並且在轉移的時候多考慮進來即可。而這個陣列的預處理方法是，對於每個 i ，把他對應的 bonus 們按照門檻由小到大排序，再一個一個去更新所求的陣列。

code :

[USACO 2014 Gold] Roadblock

作法：

考慮從 1 到 n 的最短路，如果擋住的道路不在最短路上，那麼顯然不影響答案（就算其他邊邊權變大了他還是最短路），所以我們只要考慮最短路上的邊。而由題目給的數字範圍知道可以直接枚舉要擋住最短路上的哪條邊。當把一條邊的邊權改為兩倍時，如果新的最短路還有經過這條邊，那麼他一定長的跟舊的最短路一樣，這時可以知道多走的距離就是這條邊的長度。而沒有經過這條邊的話，就把他拔掉做一次最短路即可。

code :

[USACO 2014 Gold] Ski Course Rating

作法：

如果有一格 P 的答案是 D ，那麼考慮所有滿足「存在一條從 P 走到他的路徑，使得路徑上兩相鄰點的點權差不超過D」的格子，這些格子在限制差為 D 的時候是兩兩互通的，並且我們知道這些點的總數 >= T （因為 P 的答案是 D），也就代表這些點的答案都會 <= D 。因此我們可以考慮先把格子們轉換成圖，並且對兩相鄰的點之間建邊，權重是點權差，然後按照邊權從小到大一條一條加入圖中，用 disjoint set 維護，當加入某條邊後有一個連通塊的大小超過 T 的話，代表這個連通塊中的所有數的答案都會是這條邊的權重。而題目要求的是總和，所以可以只對每個 disjoint set 只維護有幾個格子是詢問的格子即可，不用維護詢問的是哪些格子，而每個連通塊的大小是顯然一定要紀錄的。

code :

[USACO 2014 Gold] Building a Ski Course

作法：

首先可以觀察到，如果邊長為 B 的正方形可以蓋出所求的圖形，那麼邊長為 B-1 的也可以蓋出來，因為邊長為 B 的正方形可以由 B-1 的蓋四次得到，所以可以二分答案。如果直接思考第一步應該要蓋在哪裡，會發現根本沒辦法決定，因為之後可能有一堆地方被新的正方形覆蓋掉了。考慮把整個過程反過來，會發現最後一次壓下去的那塊 B*B 的正方形中一定同為 S 或同為 R 。再考慮最後第二次壓下去的那塊 B*B 的正方形，他除了「最後一次壓下去的那塊正方形內部的格子」以外的格子都必須同為 S 或 R ，而和最後一次壓下去的那塊交集的部份不管是什麼都可以，反正等等就會被覆蓋掉了。所以我們就可以得到這樣的算法：從給定的圖開始，每次在圖中尋找整塊都是 S 或整塊都是 R 的 B*B 的正方形，然後把正方形的內部都標記成「此格可以當 R 也可以當 S 」，並且在之後判斷是否為整塊都是 R（S）的正方形時放寬這種格子的限制。如果做到最後全部的格子都被覆蓋了，那麼就是可以，否則就不行。在實作上，我是對每個點算出以他為正方形右下角的最大正方形邊長，如果邊長>=B，並且之前還沒有在這個位置蓋下 B*B 的正方形，那麼就把他紀錄起來，當跑完 n*m 格之後將所有剛才找到的正方形把他蓋下去，重複這個動作直到不能在做為止。這樣可以把原本O(n^2 m^2 log(n+m)) 的算法時間壓到不至於TLE。

code :