[CF 536D] Tavas in Kansas

作法：

首先先處理出給定的兩個點到其他所有點的距離。再來把到第一個點的距離們和到第二個點的距離們分別離散化，假設總共有 n 種到第一個點的距離， m 種到第二個點的距離，那麼考慮一張 n * m 的方格表（左上角是 ( 1 , 1 ) ，右下角是 ( n , m )），如果在原本的圖中有一個點到給定的兩個點的距離分別是 x1 和 y1 （已經離散化過了，所以 1 <= x1 <= n 且 1 <= y1 <= m），那麼就把這個方格表的 ( x,y ) 位置的價值加上這個點的點權。那麼這個遊戲就可以等價成：先手首先選一個 y0 ，把 y 座標 <= y0 的格子都取走，然後換後手選一個 x0 ，把 x 座標 <= x0 的格子都取走，一直重複這個動作直到格子被取完為止，取的點權和比較多的人就贏了。

但這裡我們還少考慮到了一個東西，就是題目有要求每次必須要至少選到原圖中的一個點，不過我們先思考不考慮那件事的情形。那麼這時就顯然是一個 DP ，記 dp1[ i ][ j ] 代表盤面剩下 ( i , j ) ~ (  n , m ) ，且此時輪到先手時先手可以獲得幾分， dp2[ i ][ j ] 則是此時輪到後手時後手可以獲得幾分，並且記 ( i , j ) ~ ( n , m ) 的分數總和為 S，那麼 dp1[ i ][ j ] 就會等於 S - min{ dp2[ i ][ k ] } , k = j+1 , ... , m+1 （註：當 k = m+1 時代表此時盤面為空）。同理 dp2[ i ][ j ] 的轉移式也類似，而這樣的轉移可以藉由維護好 min{ dp2[ i ][ k ] } 的方法來把複雜度降為 O( nm) 。具體來說，考慮按照從第 n 列做到第1列，同列時從第 m 行作到一行的順序計算每個 DP 值，那麼在算 dp1[ i ][ j ] 的時候，我們需要的值是 min{ dp2[ i ][ j+1 ] , ... , dp2[ i ][ m+1 ] } ， 因此只要紀錄一個值 miy ，代表我們需要的值，並且在算完 dp2[ i ][ j ]的時候拿他去更新 miy 就好了，並且在我們計算到下一列的時候把 miy 的值清掉，就可以繼續用了。同理在算 dp2[ i ][ j ] 的時候，需要的會是 min{ dp1[ i+1 ][ j ] , ... , dp1[ n ][ j ] } ，但這時由於我們計算的順序不是直的，所以不能像剛才一樣只用一個值來維護，必須用一個陣列，也就是每次在算 dp2[ i ][ j ] 需要的值會是 mix[ j ]，並且在算完 dp1[ i ][ j ] 之後把 mix[ j ] 用 dp1[ i ][ j ] 取 min ，維護好他的值。

上面成功解決了弱化版的問題，接下來要把題目原始的條件考慮進來。首先如果當前的狀態是 ( i , j ) ，並且輪到先手，設先手在這一局吃掉的矩形是 ( i , j ) ~ ( n , y0 ) ，那麼為了要讓這一步是合法的，就必須要有這個矩形裡面有至少一個原始圖中的點。但不能直接用這塊矩形的價值總和是否為 0 來判斷，因為題目裡也有提醒點權有可能是 0 ，因此還必須在另外處理一個 val 陣列，其中 val[ i ][ j ] 在 ( i , j ) 有對應到原圖中的一個點時其值為 1 ，否則為 0 ，並且處理出他的二維前綴和陣列，那麼就可以 O( 1 ) 知道這一步合不合法了。再來則是轉移的部份必須要更改，首先看 dp1[ i ][ j ] 的部份，在之前的情況是他可以轉移到 ( i , j+1 ) , ... , ( i , m ) ，但在這裡則不行，因為如果 ( i , j ) 到 ( n , y0 ) 的 val 總和是 0 的話，就會沒辦法轉移到 ( i , y0+1 ) ，但一個簡單的觀察是，如果 ( i , j ) 可以轉移到 ( i , y0 ) ，那麼就可以轉移到 ( i , y1 ) ，其中 y1 >= y0 ，因此我們可以用類似雙指標的方法，多紀錄一個 id 值，代表當前的 miy 的值等於 min{ dp2[ i ][ id+1 ] , dp2[ i ][ id+2 ] , ... , dp2[ i ][ m+1 ] } ，其中 id 代表的意義是「讓 ( i , j ) , ( n , id ) 形成的矩形內的 val 值總和不為 0 的最小值」，那麼就可以維護好 miy 值了。而在算 dp2[ i ][ j ] 的部份就幾乎一樣了，差別只有在和剛剛一樣的 mix 值會變成一個陣列，還有 id 值也會而已了。最後算出的 dp1[ 1 ][ 1 ] 就是先手能夠獲得的分數了。

code :

[CF 521E] Cycling City

作法：

首先當然是把每個連通塊分開看，如果其中一塊有解就是有解，因此以下假定圖連通。如果這張圖裡面沒有環的話，那顯然就沒有解。如果有環的話，那麼就代表如果存在環上的兩個點 A 和 B，使得 A 可以經過一連串不在環上的點走到 B 的話，A 和 B 之間就存在三條路徑。因此可以得到：存在滿足題目要求的三條路徑若且唯若這張圖不是仙人掌圖( cactus graph )。之前我就有遇過有向圖版本的仙人掌問題( TIOJ 1484 ) ( 題解 )，作法是考慮 DFS 樹，那麼這裡應該也差不多。

因此一樣考慮DFS樹，如果樹上沒有回邊，那就代表原圖裡沒有圈，此時不可能有解。反之我們會找到一條回邊，假設為 B -> A 好了，那麼就可以把樹上的從 A 到 B 的這段路徑上的所有邊都標記為「被 A 和 B 所有」了，因為如果之後又找到了另一條回邊 D -> C ，其中樹上的從 C 走到 D 的路徑會和從 A 走到 B 的路徑有交集，那麼這樣就可以產生三條不相交的路徑了（可以自己畫畫看）。因此當我們在之後找到一條回邊 D->C ， 並準備要把所有 C 到 D 之間的邊都標記為「被 C 和 D 所有」的時候，發現有一條邊早就被標記成 「被 A 和 B」所有的時候，就代表找到一個解了。因此剩下的工作就是把解印出來，首先確定三條路徑的起點和終點，討論一下各種情形可以得到起點其實會是 B 和 D 的LCA，而終點則是 A 和 C 中深度比較深的那一個，確認起點和終點之後，剩下只需要一個能夠獲得「從 X 走到 Y 的路徑上依序經過的點們」的函式就可以了，並且因為每次我們需要的路徑都會長的像「自己走到某個自己的祖先」或是「自己走到某個自己的子孫」，因此這個函式就可以用「一直沿著父親往上跳」的方法實作。

另外我覺得官方解的作法比我的簡潔很多，可以參考看看，或是參考dreamoon的題解XD。

code :

[CF 521D] Shop

作法：

首先不難證明，對於同一個技能來說，如果三種操作都作用在他身上了，那麼順序一定會是第1種 -> 第2種 -> 第3種。並且第1種只會進行一次。再來因為我們要讓總乘積越大越好，也就是個別技能的成長倍數越大越好，所以可以先把所有數分開來看，最後再合併起來。首先考慮如果對於一個數字，有三種操作可以選擇，那麼第3種一定是最後執行，並且選的時候會按照乘的倍數由高到低一個一個選。至於第1種和第2種操作，假設當前數字為 x ，第1種操作可以把 x 設為 b ( 這裡假定 b > x ，否則就完全不用理這個操作了 )，而第2種操作則是有很多個，分別是把 x 加上 b_1 , ... , b_k ，並且可以假設這些數已經由大到小排好了，因為不管怎麼樣，取加的數比較多的會比較好。再來我們要決定在選取這些操作的時候，第1種操作應該要被放在哪個時間點來選( 也就是當我們能夠在這個數字上花的操作次數越來越多時，一般來說我們會依次取 b_1 , b_2 , ... ，但當能夠對這個數操作 k+1 次時，一定是把那兩種操作都取掉了，因此中間一定有一個瞬間是取完 b_i 之後取了第1種操作 )。令 y = b - x ，事實上我們可以把這個第1種操作看成「第2種操作的加上 y 」，因為當一選取到第1種操作時，一定是在執行所有加的操作之前就先執行他了，也就是執行他的時候 x 的值還沒被改過，因此他就可以被等價成「第2種操作的加上 y」 。這邊比較容易搞混的是，雖然這個第1種操作的「優先度」比較低（也就是當我們只能在這個數上花少少的次數的時候，還輪不到他被取到），但當一決定取他的時候，就會把他放到所有操作的最前面來執行，所以才能斷定他就等價於「第2種操作的加上 y 」。

因此現在我們把第1種操作都改為第2種操作了，這時候的想法也跟剛才類似，因為當我們取到 b_i 的時候，代表 b_1 ~ b_( i-1 ) 都已經被取到了，因此此時產生的數的值一定會是 x + b_1 + ... + b_( i-1 ) ，那麼再取 b_i 就會讓值變為 x + b_1 + ... + b_i ，因此這個操作的作用是已知的，也就是他讓這個數成長的倍率也是已知的，那麼也就可以把他等價成第3種操作了。因此現在全部都只剩第3種操作了，那麼就可以直接按照倍率由大到小排序然後 greedy 了。（注意到在把第2種操作轉換為第3種時，每次多加了一個 b_i 的時候，其實這個數的成長倍率是遞減的，因為這個數越來越大，但加的數越來越小。因此在 greedy 的時候不會發生「 b_i 被取到的時候，b_1 ~ b_( i-1 ) 還有沒被取到的」的情況。）

code :

[CF 475E] Strongly Connected City 2

作法：

首先可以想到，如果整張圖裡面有一個可以走遍所有點的圈的話，那麼只要把邊定向成繞一圈的，就可以達到最大值 n^2 了。因此由這件事可以想到，考慮這張圖的邊雙連通分量，那麼可以先把每個邊雙連通分量內部都先弄成一個強連通分量，把他們都先整個縮起來，這樣就可以得到一棵帶權的樹，所以之後只要處理樹的情況就可以了。

接下來我猜測了一件事，但我證不太出來他為什麼是對的，就是在最佳解中，如果沿著任意一條樹上的路徑走的話，路上經過的邊的方向至多只會改變一次，或是說不存在點列 A_1 , A_2 , ... , A_k ，滿足 A_1 -> A_2 ， A_( k-1 ) -> A_k ，且 A_( i+1 ) -> A_i ，其中 2 <= i <= k - 2 （X -> Y 代表有一條有向邊從 X 連向 Y）。而由這件事就可以推到用來解決這個問題的關鍵性質；存在一個點 X ，使得對於其他的所有點 Y ，X 到 Y 路徑上的所有邊要嘛全部指向 X ，要嘛全部指向 Y （證明補在最後面）。因此考慮枚舉每個點當作 X ，記他的子樹們為 T_1 ~ T_k ，還有其大小分別為 S_1 ~ S_k ，那麼不管 T_i  內部的所有邊是全部都指向 X 的還是全部都指 X 的反方向的，他內部的「可以從 A 走到 B 的 ( A , B ) 點對數」都是固定的了，因此可以先算出來。還有要加上 X 可以走到其他所有的點。最後要決定的東西是形如 A 在 T_i 裡，B 在 T_j 裡( i != j )，且 A 可以走到 B 的 ( A , B ) 點對數，也就是我們要決定每個 T_i 的類型。不妨設 T_1 ~ T_r 都是指向 X 的，而 T_( r+1 ) ~ T_k 都是指向 X 的反向的，那麼在這個部份所得到的點對數就會是 ( S_1 + ... + S_r ) * ( S_( r+1 ) + ... + S_k ) ，因為他們的和是固定的，而我們希望他們乘起來的值越大越好，所以我們必須要把 S_1 ~ S_k 分成總和最接近的兩堆，而這就是經典的可以用 DP 解的問題了。

最後補上我猜測的那個性質和另外一個性質的等價證明。首先從右推到左是顯然的，所以只需處理從左推到右的情形，也就是接下來要證明「一條路徑上至多改變一次方向」可以推到「存在一個點 X 滿足那件事」。隨便取一個點 P，如果他已經滿足 X 的條件的話那就證完了，因此我們可以假設存在兩個點 A 和 B ，使得 P 走到 A 的路上的邊都是指向 A 的，且 B -> A （反過來的話不影響證明）。此時如果有另一個點 C 使得 C->A ，那麼 C 所在的不包含 A 的那一整個子樹裡的邊的方向就都確定了，全部都會是指往 C 的方向，否則就會違反先前假設的性質。再考慮其他由 A 指出去的邊，如果這時候找不到另一個點 D ，使得 A 走到 D 的路徑上全部都是指向 D 的邊，但存在另一個點 E 使得 E->D ，那麼取 A 為 X 就證完了。否則新找到的 D 和 E 的地位就等同於剛才的 A 和 B ，因此可以一直重複這樣的過程下去。但這個過程不可能進行無限次，否則整棵樹的大小為無限大，矛盾。因此總有一天會停下來，也就是我們一定找的到滿足那個條件的 X 。

對了，官方解裡面是直接寫了那個我等價之後的性質，然後說很多人都猜這件事是對的，也沒證明為什麼，就只有說這是一個 magic XDDD

code :

[CF 534F] Simplified Nonogram

作法：

一開始看到題目的範圍大概就知道是某種很暴力的爆搜題，而 n<=5 大概是要用來狀態壓縮的。考慮用切一半的方法處理，把盤面切成左右兩半，但這樣就會沒辦法知道左右兩半的每一列分別要有幾陀黑格，所以必須再多加一些條件。假設現在切成的是第 1 ~ mid 行和第 mid+1 ~ m 行，那麼如果我們確定了第 mid 行和第 mid+1 行的每一格的顏色，就可以知道在每一列中，左邊的黑色陀數加上右邊的黑色陀數的值了。而因為兩邊的寬度都不超過m/2，所以他內部的陀數不會超過 m/4 ，所以可以每種情況都枚舉一次，這樣會花至多 2^n * 6^(m/4) 的時間來跑遍每一種情形。所以接下來的問題就變成了必需要快速的獲得這個切割後的小問題的答案：對於一個 n * k 的矩形( k <= m/2 ) ，給定第 k 行中那 n 格的顏色，還有每行每列的黑格陀數，問是否有辦法達成。如果有辦法則輸出一組解。

這個小問題就可以用DP來解了，設 dp[ i ][ j ] 代表第 1 ~ i 行都滿足行的陀數限制，那麼狀態 j 有沒有辦法被達到，其中 j 裡面把好幾個東西壓在一起：目前的這 n 列分別有幾陀黑格，加上第 i 行的黑白狀態。因為黑格陀數不會超過 5 ，所以可以用六進制把前面壓起來，再把他乘 32 加上黑白狀態，這樣總共會有 10 * 6^5 * 32 種狀態，記憶體是夠的。而轉移算是顯然的，只是有點繁複，六進制那邊要小心處理就是了。但題目還要求輸出解，所以只記錄一個狀態可不可行是不夠的，而這只要多記錄 dp[ i ][ j ] 是從 dp[ i-1 ] 的哪一個狀態轉移過來的，就可以一路逆推回去了。另外一個小細節是，當在轉移的時候似乎要枚舉 2^n 種情況，但實際上滿足「這行的陀數為給定的值」的行的黑白狀態不會太多，例如當 n=5 時就最多只有 15 個，因此一個狀態實際上只會轉移到 <= 15 個狀態，可以先把每行的符合要求的數字先預處理出來。

code :

[HOJ 368] 矩型計數

這題我的作法幾乎跟官方解一樣，可以先看看官方解的第38頁到第60頁，雖然是日文的，不過單看圖的話其實就很好理解了。

作法：

考慮分治法，把所有點切成左右兩半，對於矩形的兩端點都落在同一區塊內的矩形只要遞迴下去處理就可以了，所以這裡只需要考慮左端點在左半部，右端點在右半部的矩形們。首先觀察到，假設 ( x1 , y1 ) 和 ( x2 , y2 ) 是分別是一個合法矩形的左下角和右上角，且一個在左半部一個在右半部，並且假設中央線（也就是把點集切成左右兩半部的那條鉛直線）的 x 座標為 x0 ，那麼這就代表左下角為 ( x1 , y1 ) ，右上角為 ( x0 , y2 ) 的矩形內沒有其他點，因此我們可以反過來想，假設 Y 是最小的數，滿足以 ( x1 , y1 ) , ( x0 , Y )  為左下、右上角的矩形中有其他的點，那麼在計算以 ( x1 , y1 ) 為左下角的合法矩形個數時，就只要考慮右半部中 y 座標介於 y1 ~ Y 的點就可以了。並且不難發現 Y 的值的計算方法，只要找「在左半部且在 ( x1 , y1 ) 右上方的點之中 y 座標的最小值」就可以了，而這就可以簡單的按照 x 座標由大到小作，用 set 的 lower_bound 就可以找到每個在左半部的點的 Y 值了。

至於 ( x2 , y2 )，類似的推導過程可以得到這次是反過來找「在右半部且在 ( x2 , y2 ) 左下方的點之中 y 座標的最大值」，假設他為 Y2 好了，那麼這次得到的區間就會是 Y2 ~ y2 。而這也可以用 set 輕鬆解決。

所以現在我們在左右兩邊都得到了一些線段，並且由這些線段的定義可以知道，如果左邊有一條線段 [ a , b ] ，右邊有一條線段 [ c , d ] ，那麼 a < c < b < d 若且唯若產生這兩條線段的點形成一個合法矩形的左下角和右上角，因此問題轉化為如何求滿足這個條件的線段組的數量。解決這個問題的想法是，對於每一條左邊的線段，都去計算這條線段和多少條右邊的線段可以滿足條件。假設這條線段為 [ a , b ] ，那麼考慮右邊線段中所有上端點 > b 的線段們，如果把他們的下端點的 y 座標都標記起來，那麼所求就會等於 [ a , b ] 之間的被標記起來的 y 座標個數，由這件事就可以得到這個算法：先離散化所有的線段端點，把左右的線段分別按照上端點高度排序，按照上端點由高到低來處理左邊的線段，每次遇到一個線段的時候，假設他為 [ a , b ] ，那麼就把右邊所有上端點 > b 的線段，把他的下端點的值 + 1 ，然後查詢 [ a , b ] 之間的和，而這就用個BIT來做就可以了。

code :

[CF 533F] Encoding

作法：

考慮一個這兩個字串可以成功匹配的位置，當我們只看 S 中的特定一個字母時，假設是 X 好了，那麼在所有 X 出現的位置裡，對應到 T 中一定全部都視同一個字母，假設他為 Y 好了，那麼這同時也代表 Y 在 T 中出現的位置恰好就是對應的 X 在 S 中出現的位置。因此我們可以反過來作：枚舉字母 X 和字母 Y ，看看 T 可以被擺在 S 的哪個地方，使得所有的 T 中的 Y 所對應到的 S 上的字母都是 X ，並且不會有少對應的情況（也就是在被 T 蓋住的這個區間內的 S 中的所有 X 恰好和出現在 T 中的所有 Y 對應到），再來一樣考慮可以成功匹配的位置，假設為 p 好了（也就是把 T 的第一個字母放在 S 的第 p 個字母時可以成功匹配），那麼所有在 S 中這個區間內的所有字母都一定會配對到另一個字母，因此我們對每個位置都紀錄「把 T 放在這裡時有幾個字母成功匹配了」，具體來說是：當我們發現 S 中的 X 和 T 中的 Y 會在把 T 放在 q 位置的時候成功匹配的話，就把 q 位置的成功匹配值加上「 T 中 Y 的個數」，那麼就會得到匹配成功的 p 位置的成功匹配值一定會等於 T 的長度。因此首先可以把一些不可能是答案的位置篩掉。再來要確認的是，把 T 放在 S 的那個位置時，他們之間的字母的對應關係是否和題目要求的相同，而這只要在前面處理「 T 中的 Y 和 S 中的 X 在哪些位置匹配」時，再對所有找到的位置紀錄「此時 X 會被對應到 Y」，就可以確認這樣的對應關係是否為題目要求的了。

最後，在處理「 T 中的 Y 和 S 中的 X 在哪些位置匹配」的時候，一種方法是當確定 X 和 Y 時，把 S 中所有的 X 都視為 1 ，其他則視為0，而 T 中則是所有的 Y 都視為 1 ，其他視為0，把兩個字串拿去做 KMP ，這樣單次的時間會是 O( |S| + |T| ) 。或是另一種方法是：把所有 X 出現在 S 中的位置都丟進一個 vector 裡面， Y 出現在 T 中的位置丟進另一個 vector 裡面，然後把兩個 vector 分別差分，再拿去匹配第二個序列出現在第一個序列的哪裡。這樣的複雜度會是 O( S中X的個數 + T中Y的個數 ) 。如果仔細算一下會發現前者的總複雜度會是 26 * 26 *( |S| + |T| )，後者則是 26 *( |S| + |T| )。兩種方法都會過，我寫的是第2種方法，他比第1種難寫很多QQ ，是之後我看詳解才知道有第1種作法的。

code :

[CF 533E] Correcting Mistakes

作法：

假設原字串為 X ，並且遺漏掉的兩個位子分別是 X[ a ] 和 X[ b ] ，其中 a < b ，那麼可以得到：S[ i ] = T[ i ] ，對於所有的 i < a 或 i >= b ，並且對於 a ~ b 之間的區間，會變成兩個字串位移一個，也就是如果設 S 是漏掉 X[ a ] 的字串， T 是漏掉 X[ b ] 的字串，那麼 S[ i ] = T[ i + 1 ] ，其中 a <= i < b - 1 。因此只要先找到兩個字串從左邊開始比對的第一個不一樣的點，還有從右邊開始比對的第一個不一樣的點，把中間的部份切下來，看把 S 往左移一格或往右移一格會不會和 T 一模一樣就好了。

這題我在賽中 hack 到了3個人，用的測資是： 3 aba bab ，答案是 2 ，不少人都以為如果兩個字串不一樣的位置太多，那麼答案一定 <= 1 。

code :

[CF 533B] Work Group

作法：

蠻基本的樹上的DP題，記 dp[ x ][ 0 ] 代表以 x 為根的子樹中，選偶數個人並且滿足條件的最大價值，dp[ x ][ 1 ] 則是選奇數個人( 不管 x 本身是否有選 )，那麼在算 dp[ x ]的時候，首先算出不取 x 的話，在他的子樹中取奇數或偶數個人，並且滿足條件的最大價值，然後再拿「取 x 並且在他的子樹中取偶數個人」的價值去更新取奇數個人的價值就可以了。

code :

[CF 526F] Pudding Monsters

作法：

首先把問題轉換為一維問題，記 a_i 代表落在第 i 行的東西是落在第幾列的，那麼我們要找的東西其實就是滿足以下條件的 ( i , j ) ：如果 a_i ~ a_j 的最小值為 m ，最大值為 M ，那麼 m ~ M 之間的所有數字都出現在 a_i ~ a_j 中，而這其實也等價於 M - m = j - i ，這件事是個很好的充要條件，之後都會用到他。利用分治法，設現在要算所有被 [ L , R ] 包含的符合條件的區間有幾個，令 mid = ( L + R ) / 2 ，那麼對於 [ L  mid ] 和 [ mid+1 , R ] ，遞迴下去處理就好了，所以現在只要處理左界 <= mid 且右界 > mid 的區間就好了。而如果 [ l , r ] 是一個橫跨 mid , mid+1 的區間，那麼這個區間內的最大和最小值就可以用 [ l , mid ] 和 [ mid+1 , r ] 組合出來，因此我們先算出以下這些陣列： lmin , lmax , rmin , rmax ，其中 lmin[ x ] = min { a[ x ] , ... , a[ mid ] } ，其餘類似。並且把目標的區間分成四種：( 以下簡稱 [ L , mid ] 為左邊，[ mid+1 , R ] 為右邊 )

1. [ l , r ] 中的最大值和最小值均落在左邊
2. [ l , r ] 中的最大值和最小值均落在右邊
3. [ l , r ] 中的最大值落在左邊，最小值落在右邊
4. [ l , r ] 中的最大值落在右邊，最小值落在左邊

我們只要會處理 1. 和 3. 就可以了，因為 2. 和 4. 只是他們左右反過來而已。首先處理 1. ，枚舉目標區間的左端點，那麼由 lmin 和 lmax 就可以知道目標區間的最大和最小值，那麼由前面講過的性質可以得到目標區間的長度了，也就是右端點也確定了，所以就可以再根據 rmin 和 rmax 來確認這個區間是不是合法的了。再來是第3種情況，一樣考慮枚舉左端點，設當前左端點為 x ，那麼這時候右端點 r 就必須滿足 rmin[ r ] < lmin[ x ] ，還有 rmax[ r ] < lmax[ x ] ，並且注意到 rmin 是個遞減的陣列，rmax 則是遞增的，因此第一個限制條件告訴我們 r 必須要夠大，他的 rmin 才可以夠小，而第二個限制條件告訴我們 r 必須要夠小，讓他的 rmax 不至於超過 lmax[ x ] ，因此所有可行的右端點們會形成一個區間。再來我們要知道這個區間裡有幾個可行的右端點。記 lmax[ x ] = M ，還有對於任意一個在可行區間內的 r ，記 rmin[ r ] = m ，那麼也就是現在有很多個候選的 ( r , m ) ，而我們需要的是 M - m = r - x 的 ( r , m ) ，也就是 r + m = M + x 的 ( r , m ) ，因此可以用一個 map 維護所有在可行區間中的 r 的 r + m 值，就可以直接查詢有幾個數會等於 M + x 了。

code :

[CF 526E] Transmitting Levels

作法：

對於每個點，我們可以預處理出「從他開始往後取，最多可以取到哪個數」，也就是對 i 來說，設 j 是最小的滿足 a[ i ] + ... + a[ j ] > B 的數 （ j 如果跑超過 n 了就從 1 繼續跑，因為他是環在一起的），對每個 i 都算出這樣的 j ，把他叫作 nex[ j ]。首先可以得到：一定有一個切點存在於 i , i+1 之間，或 ... 或 j-1, j 之間，否則如果這些地方都沒有切點的話，代表 i ~ j 都在同一塊，就矛盾了。因此可以想到第一個算法：隨便選一個 i ，那麼就枚舉剛剛那些可能的切點，因為只要確定了一個切點，就可以把問題轉成一維問題了。因為只要一直沿著 nex 陣列往後跳，跳到第一個超出去的時候就會得到答案了。但這樣複雜度會爛掉，而這只要加上一個優化就可以了：考慮 nex[ i ] 和 i 的距離（也就是 i 走幾步才會走到 nex[ i ]），那麼只要挑讓這個距離最小的 i 就可以了，因為如果這個距離為 d 的話，那麼枚舉的時候只會枚舉 d 次，而每次枚舉的時候，因為跳的長度都會 >= d ，所以跳 O(n / d) 次就會回來了，因此複雜度就會是好的 O( d ) * O( n / d ) = O( n ) 。

code :

[HOJ 403] 史萊姆突變計畫

作法：

對於第 i 種的史萊姆，他突變之後會固定變成另外一種的史萊姆，假設叫作 p[ i ] 好了，那麼考慮一張 n 個點的圖，對於每個 i 都往 p[ i ] 連一條有向邊，那麼這張圖就會變成水母圖。而對屬的部份也可以建一張圖。所以當給定一個起點的屬的時候，考慮沿著 p 一直跳，那麼他有一天一定會跳到重複的點，這時候就會一直重複下去，這樣的圖形就長的像一條鍊接上一個環。而給定起點的種的時候就沿著 y 座標的排列一直跳，也會跳到重複的點。所以現在就得到了兩個圖，一個是 x 得意個是，這時候就可以分成好幾種情況討論，首先是如果詢問的屬（或種）沒辦法被跳到，那麼就一定不可能。另一種可能是目標點的 x 值落在 x 的圖的鍊上，那麼我們就知道跳幾次會跳到終點了，所以就可以直接判斷了。同理當目標點的 y 值落在 y 的圖的鍊上也可以直接確認。而如果兩個都在環上的話，因為走到環上任意一點的可能步數會形如 a * x + b ，其中 x = 0 , 1 , ... ， a 為環的大小。而另一個環也是這樣，因此就會變成要解 a * x + b = c * y + d 了，其中 x 和 y 是未知數，且都 >= 0 ，而這就可以用擴展歐基里得算法做了。

code :

[HOJ 402] 扶養權分配問題

作法：

首先把每個蘿莉隨便丟給其中一個人，那麼現在會得到每個人有某個特定個數的蘿莉，並且如果一個蘿莉可以被分給 A 和 B ，那麼當我們把蘿莉分給另外一個人的時候，會同時改變 A 和 B 擁有的蘿莉數的奇偶性，所以這樣就可以等價成另一個問題：有一張圖，每個點有一個權重（1或是0），並且對於每一條邊，都可以同時對兩端點 xor 1 ，而目標是要讓權值為 1 的點越少越好。而在最後改完權值之後，如果某個 A 還是奇點，那麼就多加一個蘿莉，把他分給 A 就好了。而對於等價後的問題，首先對每個連通塊分開看，對於每個連通塊，首先可以觀察出改完權值之後可以讓奇點數量 <= 1 ，因為如果還有兩個奇點，那麼隨便找一條連接他們的路徑，把路徑上的所有邊的兩端點都 xor 1 ，就可以把兩個奇點消掉了。而構造其實不難，只要隨便找一個這個連通塊的生成樹，從底下開始把所有的奇點都對他和他的祖先 xor，這樣奇點就可以全部往上丟了。並且因為奇點的個數奇偶性不會變，所以原本如果有奇數個奇點，最後就會剩一個奇點在根。最後要注意到，如果一個蘿莉分給的兩個人是同一個人，那就不要在新的圖中建這條邊了，因為他沒有「交換」的動作，而他也只有一種分法，所以就不理他就好了。


code :

[HOJ 401] 完美小矩陣

作法：

原題等價於要找一個矩陣 A ，使得 A*A = k * I ，對兩邊取 det 可得 det(A)^2 = k^n ，所以 k^n 是完全平方數，所以可以得到：當 n 是奇數且 k 不是完全平方數的時候原題無解。而當 k 是完全平方數的時候顯然有解，只要選 sqrt( k ) * I 就可以了，所以問題剩下 n 是偶數且 k 不是完全平方數的情形。當 n = 2 時，設 A = [ a b ] [ c d ] ，直接算出 A^2 然後令他等於 k * I ，就可以得到一個簡單的構造：a = 1 , b = 1 , c = k - 1 , d = -1 。再來我是想到 n = 4 的時候可以構造讓左下角的 2*2 和右上角的 2*2 全部都是 0 ，然後左上角和右下角的就分別放 2*2 的構造，然後我就以為這樣只有構出 2 ^ x ，結果過好久才發現其實偶數都構出來了，因為只要把 2*2 的構造填滿整個主對角線，其他都放 0 就可以了。

code :

[HOJ 400] LOI

作法：

首先枚舉國手線的分數，還有哪些人落在國手線上，這時候就有一個這件事情發生的機率了，把他叫作 p 好了。再來對於落在線以外的人們，他們不是高於線就是低於線，並且高於線的人頂多只有 3 個。於是再對剩下的人枚舉有哪些人是高於線的，那麼這時候的機率就會變成： p * 那些人高於線的機率乘積 * 其他人低於線的機率乘積 ，那麼就可以把這個機率加到「高於線的那些人」的答案中。至於那些在線上的人，他們會抽籤爭奪 4 - num 個位置，其中 num 是高於線的人的數量，因此他們的機率必須還要再乘以 ( 4 - num ) / 線上人數，並且把他加到他們的答案中。在枚舉高於線的人的時候我是用DFS來做，然後因為時限看起來有點緊，所以我還先預處理「對於一個 i ，他的 bit 的位置分別是哪些」。而這題的另外一個重點就是機率的部份，我是先預處理出在 i 分中拿到 j 分的機率，並且在枚舉哪些人高於線哪些人低於線時，會必須要知道一個人高於某個分數或是低於某個分數的機率是多少，所以還必須要處理出機率的前綴和，也就是在 i 分中拿到 <= j 分的機率。而之後在詢問機率的時候，有可能會出現「詢問一個人在 i 分中拿到某個負數分」的機率是多少，所以如果直接查詢機率陣列會爛掉，所以另外用一個函式來寫這個東西，還有「在 i 分中拿到 x ~ y 分的機率」也會需要用函式寫，因為有可能 x 衝到負的，或是 y 衝的太大之類的，都會讓查表直接悲劇掉。

code :

[CF 525E] Anya and Cubes

作法：

蠻顯然是切一半的題目。對兩半都枚舉「要拿哪些方塊，其中哪些要加驚嘆號」，把左半部的「加了 i 個驚嘆號後可以得到的所有數」都丟進一個 map 裡面，這樣在當枚舉到右半部的一個子集時，假設這個數為 s ，並且用了 t 個驚嘆號，那麼就可以把「左半部用了 <= k - t 個驚嘆號且湊出總和為 sum - s 的方法數」加到答案中。而因為能加上驚嘆號的數不能太大，算一下可以知道頂多會用到 18 ! ，因此在枚舉哪個子集要當階乘子集的時候只要考慮那些 <= 18 的數就可以了。

但這樣傳上去會 TLE ，因為在右半部找到新的一個數時，會用 for 迴圈跑第 0 ~ k - t 個 map 一次，這樣就導致 TLE 了，解決方法是把這個部份改成用 BIT 來寫，並且要注意到 BIT 必須使用 1 - base 就可以了。

======================================================

後來發現，其實可以不用改成BIT，只要在分配的時候把左邊分 n/2 + 1 個就可以了，因為慢的部份主要是右半部，所以當 n 是奇數的時候，分給左邊比右邊還多就可以加速很多了。

code :

[CF 529A] And Yet Another Bracket Sequence

作法：

首先可以知道只要加上幾個左括號，或是幾個右括號就可以了。並且可以注意到，當我們已經確定要把哪個位置的括號轉到第一個時，如果要加的是左括號，那麼一定是全部加在最前面最好，而如果要加的是右括號，則是全部加在序列的結尾最好。因此對於兩個不同的位置，只要看從他們誰開始的循環表示比較小，就代表誰比較適合當開頭。所以只要先處理出後綴數組，然後算出有哪些位置拿來當起點是不可行的（會讓右括號個數>左括號個數）就可以了。

code :

[CF 529C] Rooks and Rectangles

作法：

首先可以推出一個矩形被保護住的充要條件：每個直行都有一個車，或是每個橫排都有一個車，因此我們可以直的做一次橫的做一次，判斷「這個矩形中是否每個直排都有車」，然後把所有的 x , y 座標交換再作一次就可以了。當在處理第 i 個詢問時，假設他的上下邊界分別為 y2 , y1 ，左右邊界為 x1 , x2 ，那麼當我們只有考慮所有 y 座標 <= y2 的車時，我們只要知道「在橫座標 x1 ~ x2 中，每個橫座標中位置最上面的車的 x 座標的最小值」，然後看他有沒有 >= y1 ，就可以知道這個矩形是否滿足條件了。因此只要按照詢問矩形的 y2 從小到大排序，維護一個可以求區間最小值的線段樹，每次把 y 座標 <= 當前詢問的 y2 座標的車都加進資料結構中，然後查詢最小值就可以了。

code :

[CF 529B] Group Photo 2

作法：

如果相片的高度確定了，那麼就會有一些人必須要橫著擺，有一些人不一定需要橫著擺。因此考慮枚舉相片的高度，這樣變成要讓相片寬度最小。設當前高度為 h ，如果有一個人的長寬都 > h ，那麼這張相片就不可能拍出了。而對於高度 > h 的人就必須把他擺橫的，至於高度和寬度都 <= h 的人，假設他高 x 寬 y，先考慮把他直著擺，那麼之後把他橫著擺時就可以減少 x - y 的高度，因此如果在「必須要橫著擺的人」橫著放後，還有剩一些空間可以多幾個人橫著放，就按照「這個人橫著放後可以減少的寬度」由大到小排序，取最大的前幾個就可以了。

code :

[CF 529E] The Art of Dealing with ATM

作法：

因為如果只用一種鈔票的話，只有10^5種可能，所以先把這些可能都紀錄起來，對每個金錢都紀錄「最少要花幾張鈔票，才能只用一種鈔票付完」。對於每次詢問就只要枚舉10^5裡面的一種可能，再看看剩下的錢數是否也可以用一種鈔票付出來即可。

code :

[CF 528C] Data Center Drama

作法：

首先可以觀察到，在最終的圖裡面每個點的度都會是偶數，因為必須要兩兩捆在一起，所以第一步可以先把所有的奇點都和令一個奇點連一條邊，讓他變成偶點。接下來我們考慮一個邊的序列：從任意一條邊開始，假設他兩端點為 x , y ，然後跳到和這條邊捆在一起的，且有一個端點也是 x 的邊，假設為 x , z ，再跳到和這條邊捆在一起的，且有一個端點是 z 的邊，這樣一直跳下去。因為每條邊都有兩條邊和他捆在一起，所以這個過程會一直進行下去，直到回到原本的 x , y 。觀察在這個序列中邊的方向，因為捆在一起的邊必須要同向，所以可以得到回到 x , y 之後總共的邊數會是偶數，否則會得到 xy 的方向不等於 xy 的方向，矛盾。也就是這樣得到了一個圖中的偶圈。並且反過來也是可以的，也就是當我們找到一個偶圈，那麼就可以沿路把邊的方向定好，讓他滿足條件。所以這又得到了圖中的邊的數量是偶數條，因此如果只有奇數條邊，那麼就還必須要再加一條邊，並且還是滿足每個點的度都是偶數，而這只需隨便對一個點加上一條連到自己的邊就可以了。而題目給的圖又是連通的，這就代表存在一條尤拉迴路，那麼就直接找出這條尤拉迴路，然後把邊的方向都定好就可以了。

code :

[CF 528B] Clique Problem

作法：

這題的關鍵是注意到，如果有 x < y < z ，滿足 x 和 y 連邊，且 y 和 z 連邊，那麼 x 就和 z 連邊，證明並不難。因此我們只要找一個最長的子序列，使得相鄰的兩個點都有連邊就可以了。而這顯然可以DP，設 dp[ i ] 代表以 i 結尾的最長相鄰兩點有連邊的最長子序列的長度，那麼可以用 dp[ j ] 轉移 dp[ i ] 的條件就是 w[ i ] + w[ j ] <= p[ i ] - p[ j ] ，移項得 p[ i ] - w[ i ] >= w[ j ] + p[ j ] ，因此對於每個 j ，紀錄一個二元組 ( dp[ j ] , w[ j ] + p[ j ] ) ，並且可以知道，如果一個數的 dp 值比較小，但 w + p 的值比較大，那麼他就廢掉了，因此可以維護一個兩個座標都是遞增的二元組的 set ，查詢時對他查詢比 p[ i ] - w[ i ] 小的最大 w[ j ] + p[ j ] 值，他的 dp 值 +1 就是這個數的 dp 值。

code :

[CF 522C] Chicken or Fish?

作法：

以下把不確定拿了哪樣的人稱做「隨便」。首先可以發現，只有第一個難過的人有意義（記這個時間點為 T），代表在這之前已經有其中一種被拿完了，而後面難過的人我們都可以假設他一開始選的是已經被拿完的那樣。所以在第一個難過的人之後的人拿到的菜裡面，一定都是在 T 時還沒被拿完的菜，也就是「在 T 時被拿完的菜」的候選人只有「從 T 開始一直到結束都沒有人拿到他」的菜，並且還必須滿足 T 時累積的隨便的個數要>=他當時剩下的個數。因此對於一道菜，我們想判斷他有沒有可能最後被拿完，第一種可能就是他在第一個人難過前就已經被拿完了，另外一種可能則是在有人難過之後。前者已經討論過了，而如果是後者的話，累積到最後一刻的隨便的數量必須要先全部丟給「 T 時被拿完的那道菜」，剩下的再去拿當前這道，如果可以拿完就代表可以。

code :

[CF 522D] Closest Equals

作法：

如果有兩個相同的數，他們中間還有相同的數，那這兩個數一定不會是最佳解。所以對每個數，我們只要考慮他右邊 & 左邊離他最近且和他相同的數就可以了。這樣把所有線段都找出來之後，問題就變成：給定一些線段，每次詢問一個區間裡面包含的線段最小長度為何。考慮將所有詢問按照右端點排序，在作到一個右端點時，把所有右端點小於等於這個點的線段都加入資料結構中，並查詢答案。而只要用線段樹維護左端點為這個點的答案是多少即可，每次加入一條新的線段就會等價於對一個區間的數都和某個數取 min 。

code :

[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 :

[USACO 2014 Gold] Cow Curling

作法：

將給定的點的前 n 個為黑點，後 n 個為白點。那麼其實某個黑點被其中3個白點形成的三角形覆蓋住，若且唯若這個黑點落在白點的凸包內。所以我們只要統計有幾個黑點落在白點形成的凸包內即可，而被覆蓋的白點數量同理可以算出。考慮凸包內的任意一點 O ，我們可以把整個凸多邊形平移，讓 O 平移到原點，然後算出凸包上每個頂點的極角，讓他們按照極角小到大排序。假設當前詢問的點是 P ，那麼我們就可以用極角二分搜出 OP 和這個凸包的哪條邊相交，所以只要求出 OP 和那條邊的交點，並判斷 P 是否落在 O 和這個交點形成的線段內部，就可以知道 P 是否在這個凸多邊形內了。

另外，當凸包退化成一直線的時候要另外考慮，因為此時在求線段交點的地方會爛掉。

code :

[USACO 2013 Gold] The Bessie Shuffle

作法：

這題的關鍵就是發現到，原題的操作其實就等價於：從最頂層的 m 個數開始，每次對這 m 個數做一次排列，然後把當前窗口往下移一格。也就等價於做的排列操作是 p[ i ] - 1 ，其中 p 代表原始的排列。發現這件事之後就不難想到會用到倍增法了。但原題要問的是最後落在第 x 個位置的卡片是誰，首先把他改成從上面數下來第 n+1-x 張（以後就改把這個數叫 x ），並且考慮把整個排列的操作反過來，也就是如果設 q 是 p 的反函數，那麼我們現在要求的東西就會變成「從下到上進行 q 排列並把視窗往上滑動」之後， x 會落到哪個位置。所以我們要倍增的排列其實會是 q[ i ] - 1 。並且注意到，如果 x 在經過了 k 次轉換之後變成 0 了，那麼這時候 x 的位置就確定了（之後的排列不會再動到他），或是當這個視窗跑到最頂端，無法再進行排列的時候， x 的位置也確定了。所以在倍增求答案的時候，首先要求出第一次會影響的 x 的位置的排列是在哪個視窗，並且得到 x 關於這個視窗的相對位置（從下面數上來第幾個），叫他 now 好了，所以接下來，就是對 now 進行倍增的排列。而倍增的過程中我們只要紀錄兩個數字 num 和 k ，前者代表現在還能再做幾次排列操作，後者代表已經做幾次操作了，那麼由第一次操作的位置和 k ，還有最後 now 到達的位置，就可以算出 x 最後的位置了。

和這題類似的還有 CodeForces 484-C Strange Sorting，一樣是作進行某個排列之後滑動視窗的操作。

code :

[USACO 2013 Gold] Optimal Milking

作法：

因為題目要問的答案有可以區間合併的性質，也就是可以用 [ x , y ] 和 [ y+1 , z ] 的答案算出 [ x , z ] 的答案，所以可以用線段樹。對每個線段樹的節點 [ L , R ] ，紀錄 4 個數，分別代表是否取 a[ L ] 和是否取 a[ R ] 的時候所獲得的最大值。每次查詢時就是回答根節點的答案，而修改就和一般線段樹一樣。

code :

[USACO 2013 Gold] Vacation Planning

作法：

記題目給定的那 k 個點為黑點。首先預處理出每個黑點到其他 n 個點的最短路長，那麼當在求 x ~ y 的最短路時，如果 x 本身就是黑點，那就直接查表即可。而如果不是的話，考慮所有從 x 連出去的邊，由題目給的條件可知連到的點都是黑點，而黑點個數又不會超過 k 個，所以我們可以直接枚舉 x 要走到哪個黑點，再去查那個黑點走到 y 的最短距離，對所有的可能取 min 即可。

code :

[USACO 2013 Gold] No Change

作法：

首先看到 K<=16 應該可以馬上想到狀態壓縮DP。假設我們記 dp[ i ][ j ] 代表目前有有的錢幣集合為 i ，那麼買完 j ~ n 的物品最多可以剩多少錢。那麼轉移就會是枚舉每個目前可用的錢幣，並且枚舉要用這個錢幣付 j 到哪個物品的錢。但其實付到哪個物品可以不用枚舉，因為付越多當然是越好的，也就是我們只需要預處理出一個陣列 ri[ i ][ j ] ，代表「用第 i 種錢幣可以付第 j ~ ri[ i ][ j ] - 1 個物品的錢」，這顯然用雙指標在O(KN) 的時間內完成。但我們的DP陣列還是太大了，記憶體不夠。但其實只要注意到，因為我們要的只有 dp[ (1<<k)-1 ][ 1 ] 的值，而轉移的時候都會沿著 ri 陣列跳，所以其實 dp 陣列的第二維不會用到很多，也就是我們可以在第二維改成用 map 紀錄就好了。

感覺這個解蠻唬爛的，不過還好沒有TLE。( 其實用這個方法的時候，如果不先預處理好 ri 陣列，而是每次需要的時候再對前綴和陣列二分搜，就會TLE掉了QQ )

code :

[USACO 2013 Gold] Line of Sight

作法：

如果兩個點可以互相看見，那麼就代表存在圓上的一個點，過他作出的切線會把那兩個點和 ( 0,0 ) 分在不同側。所以對於每個點 X ，假設他對圓作切線的兩個切點為 P , Q ，那麼把 PQ 這段弧記錄下來，然後看這 n 條弧裡面有幾對弧重合就是我們要的答案了。紀錄一段弧可以用起始和終止的角度來記錄，假設他們按照左端點排序之後變成了 p_1 ~ p_n ，而如果直接對得到的這些弧的角度區間算出「有幾對區間有重合」的話會漏掉一些東西，因為這是在圓上，所以反而有可能 p_n 和 p_1 有重合。解決方法是把 p_1 ~ p_n 全部都加上循環的週期 2*PI ，放在 p_(n+1) ~ p_(2n) 裡，對 p_1 ~ p_(2n) 求左區間是 p_1 ~ p_n 的答案即可。這樣會對主要是因為一個區間的長度 < 2*PI ，還有 p_1 ~ p_n 中任兩個區間的起始點差不會超過 2*PI ，所以不會重複算到或漏算。

code :

[USACO 2013 Gold] Empty Stalls

我的作法蠻奇怪的，不過感覺上複雜度一樣是O(n) (?) ，官方解比我的好多了。

作法：

首先對每個位置，統計出有幾隻牛的目標是這個位置，接下來依序處理每個位置的牛。而對每個點 x ，都記錄一個數 ri[ x ] 代表 [ x+1 , ri[ x ] ) 這個區間裡的位置都被占領了，那麼在一隻牛尋找自己的位置的時候，就可以不用每格都掃過去，直接沿著 ri[ x ] 跳就好了，並且在放完目標是同一個位置的牛們之後，將沿路經過的位置的 ri 值都設成最後一個放牛的位置的 ri 值。

code :

[POI 18 Stage 3] Meteors

作法：

這題是整體二分的經典題。具體作法是：我們使用BIT作區間加減值和單點查詢的操作，這樣可以在 O( A_i * logm ) 的時間中求出一個人目錢賺到的錢有多少。並且我們遞回處理的問題是：對於 [ L , R ] ，已知有一個 vector 裡面放的人們的答案都落在 [ L , R ] 裡面，求出這些人的確切答案。當 L = R 的時候當然 vector 裡面的人們的答案都是 L ，而如果不是的話，令 mid = ( L + R ) / 2 ，這時後把 BIT 調整到已經進行的操作只有第 1 ~ mid 個，然後把這時候已經達到目標的人丟進一個 vector ，因為他們的答案區間就會是 [ L , mid ] ，而還沒達到目標的就丟進另一個，他們的答案區間會是 [ mid+1 , R ] ，遞回下去處理即可。

另外，要記得開 unsigned long long =ㄦ= 真是太陰險了。
感覺我沒講的很清楚，還是看看 code 吧，應該蠻好懂的。

code :

#include<bits/stdc++.h>
#define LL unsigned long long
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=300000+10 ;
 
LL bit[maxn] ;
void add(int l,int r,LL val)
{
    r++ ;
    while(l<maxn) bit[l]+=val , l+=lowbit(l) ;
    while(r<maxn) bit[r]-=val , r+=lowbit(r) ;
}
 
LL query(int x)
{
    LL ret=0LL ;
    while(x) ret+=bit[x] , x-=lowbit(x) ;
    return ret ;
}
 
LL query(const vector<int> &v)
{
    LL ret=0LL ;
    for(int i=0;i<v.size();i++) ret+=query(v[i]) ;
    return ret ;
}
 
struct P{ int l,r ; LL val; }q[maxn] ;
int n,m,nowq=0 ;
void adjust(int newq)
{
    while(nowq < newq)
    {
        int x=++nowq ;
        if(q[x].l <= q[x].r) add(q[x].l,q[x].r,q[x].val) ;
        else add(q[x].l,m,q[x].val) , add(1,q[x].r,q[x].val) ;
    }
    while(nowq > newq)
    {
        int x=nowq-- ;
        if(q[x].l <= q[x].r) add(q[x].l,q[x].r,-q[x].val) ;
        else add(q[x].l,m,-q[x].val) , add(1,q[x].r,-q[x].val) ;
    }
}
 
vector<int> peo[maxn],G[4*maxn] ;
int gid ;
int ans[maxn] ;
LL goal[maxn] ;
 
void solve(const vector<int> &v,int l,int r)
{
    if(l==r)
    {
        for(int i=0;i<v.size();i++)
            ans[v[i]]=l ;
        return ;
    }
 
    if(v.empty()) return ;
    int mid=(l+r)/2 ;
    adjust(mid) ;
    for(int i=0;i<v.size();i++)
    {
        if( query(peo[v[i]]) >= goal[v[i]] )
            G[gid].push_back(v[i]) ;
        else G[gid+1].push_back(v[i]) ;
    }
    int tmp=gid ; gid+=2 ;
    solve(G[tmp],l,mid) ;
    solve(G[tmp+1],mid+1,r) ;
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=m;i++)
    {
        int x ; scanf("%d",&x) ;
        peo[x].push_back(i) ;
    }
    for(int i=1;i<=n;i++) scanf("%llu",&goal[i]) ;
    int Q ; scanf("%d",&Q) ;
    for(int i=1;i<=Q;i++) scanf("%d%d%llu",&q[i].l,&q[i].r,&q[i].val) ;
    for(int i=1;i<=n;i++) G[0].push_back(i) ; gid=1 ;
    solve(G[0],1,Q+1) ;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==Q+1) printf("NIE\n") ;
        else printf("%d\n",ans[i]) ;
    }
}
 

[HOJ 155][USACO 2011 Gold] 線段相交

作法：

把線段們都看成點，並且如果兩條線段不能同時取就在那兩個點之間連邊，那麼就會得到一張二部圖( 直的和橫的 )，問題就變成要求這個二部圖的最大獨立集大小。而對於一個圖的獨立集，考慮他的補集，這個集合就會滿足「對於圖中的所有邊，他的兩端點裡至少有一個點會落在這個集合中」，也就是一個 vertex cover 。而有個有名的定理告訴我們二部圖的最小點覆蓋數會等於最大匹配數，所以就直接求最大匹配數即可。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=250+5 ;
 
struct seg{int x1,y1,x2,y2;}a[maxn],b[maxn];
bool inter(const seg &p,const seg &q)
{
    return p.y1<=q.y1 && p.y2>=q.y1 && q.x1<=p.x1 && q.x2>=p.x2 ;
}
 
bool adj[maxn][maxn] ;
bool visy[maxn] ;
int n,m,my[maxn] ;
 
bool dfs(int x)
{
    for(int i=0;i<m;i++) if(adj[x][i] && !visy[i])
    {
        visy[i]=1 ;
        if(my[i]==-1 || dfs(my[i]))
        {
            my[i]=x ;
            return 1 ;
        }
    }
    return 0 ;
}
 
main()
{
    int k ; scanf("%d",&k) ;
    while(k--)
    {
        seg s ;
        scanf("%d%d%d%d",&s.x1,&s.y1,&s.x2,&s.y2) ;
        if(s.x1>s.x2) swap(s.x1,s.x2) ;
        if(s.y1>s.y2) swap(s.y1,s.y2) ;
        if(s.x1 == s.x2) a[n++]=s ;
        else b[m++]=s ;
    }
 
    if(!n || !m) { printf("%d\n", n ? n : m) ; return 0 ; }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        adj[i][j]=inter(a[i],b[j]) ;
 
    memset(my,-1,sizeof(my)) ;
    int ans=0 ;
    for(int i=0;i<n;i++)
    {
        memset(visy,0,sizeof(visy)) ;
        if(dfs(i)) ans++ ;
    }
    printf("%d\n",m+n-ans) ;
}
 

[POI 18 Stage 3] Sticks

作法：

如果三角形的三邊長裡面，最大的數確定了，那麼剩下的兩個數必定越大越好。所以只要考慮枚舉每一個數當最大的數，然後找出其他顏色裡小於等於這個數的最大數，對於取出來的數字最大的前兩種顏色拿去和目前枚舉到的這個最大邊檢驗即可。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=50+10 ;
 
int get(int x,const vector<int> &v)
{
    int id=upper_bound(v.begin(),v.end(),x)-v.begin()-1 ;
    return id==-1 ? -1 : v[id] ;
}
 
vector<int> v[maxn] ;
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int m ; scanf("%d",&m) ;
        while(m--)
        {
            int x ; scanf("%d",&x) ;
            v[i].push_back(x) ;
        }
        sort(v[i].begin(),v[i].end()) ;
    }
    for(int i=1;i<=n;i++) for(int j=0;j<v[i].size();j++)
    {
        int x=v[i][j] , m1=-1 , m2=-1 , id1 , id2 ;
        for(int i2=1;i2<=n;i2++) if(i2!=i)
        {
            int tmp=get(x,v[i2]) ;
            if(tmp>=m1) m2=m1 , m1=tmp , id2=id1 , id1=i2 ;
            else if(tmp>=m2) m2=tmp , id2=i2 ;
        }
        if(m1+m2>x)
        {
            printf("%d %d %d %d %d %d\n",i,x,id1,m1,id2,m2) ;
            return 0 ;
        }
    }
    printf("NIE\n") ;
}
 

[HOJ 158][POI 18 Stage 2] Strongbox

這題我之前在HOJ上就AC過了( 作法在這裡 )，但一樣的 code 丟到 main 上 TLE 了，應該是 main 的主機跑太慢了，所以只好弄個另解=ㄦ=

作法：

參考了這篇的 code 。
由我之前打的那篇可知， d 整除 a_k 和 n ，並且不整除 a_1 ~ a_( k-1 ) 。也就是 d 整除 gcd ( a_k , n ) ，所以我們可以先把 a_k 改成 gcd( a_k , n ) ，不會影響答案。再來則是 d 不整除 a_1 ~ a_( k-1 ) 的條件，如果 a_i 有個質因數 p ，他不整除 a_k ，那麼 d 不整除 a_i 若且唯若 d 不整除 a_i / p ，也就是我們可以把每個 a_i 裡面和 a_k 不相干的部分都砍掉，也就是把 a_i 全部改成 gcd( a_i , a_k ) ，這樣也不會影響答案。

這時候問題就轉化為：現在有一個集合 S ，裡面包含了 a_k 的因數，但不包含 a_1 ~ a_( k-1 ) 的因數，求裡面最小的數 ( 也就是 d )是多少。這裡先介紹兩種找一個數的所有因數的方法，等等兩種都會用到。

假設現在要找 n 的所有因數，第一種就是直接從 1 枚舉到 sqrt( n ) ，如果 n 整除 i 那麼 i 和 n/i 都是 n 的因數，並且這樣不會遺漏。另外一種則是先求出 n 的標準分解式，假設為 p_1 ^ a_1 * p_2 ^ a_2 * ... * p_r ^ a_r ，那麼 n 的所有因數就型如 p_1 ^ b_1 * p_2 ^ b_2 * ... * p_r ^ b_r ，其中 0 <= b_i <= a_i ，所以我們可以對陣列 a_1 ~ a_r 作DFS，枚舉 p_i 要取幾個，就可以得到所有的因數。

回到原題，首先考慮這樣的一個算法：找出 a_1 ~ a_( k-1 ) 每個數的所有因數，把他們都丟進一個 set 裡，最後用第一種方法枚舉 a_k 的因數。但這樣在一開始就太慢了，因為在找出 a_1 ~ a_( k-1 ) 每個數的所有因數時會算到很多重複的數。不過我們知道 a_1 ~ a_( k-1 ) 全部都會是 a_k 的因數 ( 剛剛取過 gcd 了 )，也就是 a_1 ~ a_( k-1 ) 每個數字的樣子都是確定的( 質因數組成確定，但質因數的次方不確定 )，所以我們可以直接對 a_k 套用第二種找因數的方法，當找到了一個 a_k 的因數 u ，並且 u 出現在 a_1 ~ a_( k-1 ) 裡時，我們就知道 u 的每個質因數的次方是多少了，這時候就可以再用另外一個 dfs 找出所有 u 的因數並把它標記刪除了。但這樣還是有很多數被重複算到了，而這裡只需注意到，當 x 被刪除時，代表他的因數也全部都被刪除了，所以當第二次收到「刪除 x 」的指令時就可以不理他了，而這可以用一個 set 來維護，裡面存哪些數字已經被刪掉了。這樣就可以保證每個數頂多被刪除一次。最後再使用第一種找因數的方法，枚舉 a_k 的因數，如果遇到一個因數還沒被刪除，就把它拿去更新答案即可。


code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=250000+10 ;
 
LL getll()
{
    char c=getchar() ;
    while(c<'0'||c>'9') c=getchar() ;
    LL x=0 ;
    while(1)
    {
        x=x*10+c-'0' ;
        c=getchar() ;
        if(c<'0'||c>'9') return x ;
    }
}
 
LL a[maxn] ;
set<LL> st,del ;
 
int cnt=0,num[maxn],num2[maxn] ;
LL p[maxn] ;
 
void DEL(int x,LL now)
{
    if(x==cnt) { del.insert(now) ; return ; }
    if(del.find(now)!=del.end()) return ;
    DEL(x+1,now) ;
    for(int i=1;i<=num2[x];i++)
    {
        now/=p[x] ;
        DEL(x+1,now) ;
    }
}
 
void dfs(int x,LL now)
{
    if(x==cnt)
    {
        if(st.find(now)!=st.end()) DEL(0,now) ;
        return ;
    }
    if(del.find(now)!=del.end()) return ;
    dfs(x+1,now) ;
    for(int i=1;i<=num[x];i++)
    {
        now/=p[x] ; num2[x]-- ;
        dfs(x+1,now) ;
    }
    num2[x]=num[x] ;
}
 
main()
{
    LL n ; int m ;
    scanf("%lld%d",&n,&m) ;
    for(int i=1;i<=m;i++) a[i]=getll() ;
 
    a[m]=__gcd(a[m],n) ;
    for(int i=1;i<m;i++) st.insert(__gcd(a[i],a[m])) ;
 
    int sq=(int)sqrtl(a[m]+0.5) ;
    LL tmp=a[m] ;
    for(int i=2;i<=sq && i<tmp;i++) if(tmp%i==0)
    {
        p[cnt]=i ; num[cnt]=0 ;
        while(tmp%i==0) num[cnt]++ , tmp/=i ;
        num2[cnt]=num[cnt] ;
        cnt++ ;
    }
    if(tmp!=1) p[cnt]=tmp , num[cnt]=num2[cnt]=1 , cnt++ ;
 
    dfs(0,a[m]) ;
 
    LL ans=0LL ;
    for(int i=1;i<=sq;i++) if(a[m]%i==0)
    {
        if(del.find(i)==del.end()) ans=max(ans,n/i) ;
        if(del.find(a[m]/i)==del.end()) ans=max(ans,n/(a[m]/i)) ;
    }
    printf("%lld\n",ans) ;
}
 

[POI 18 Stage 2] Tree Rotations

作法：

對於一個非葉節點，把這個節點的兩個子樹交換的話，會讓逆序數對改變的其實只有「兩個子樹內的形成的逆序數對」數量，也就是「滿足 x 屬於 T1， y 屬於 T2 ，並且 x > y 的二元組 ( x , y )」 數量( 記為 M )，其中 T1 和 T2 代表個節點的兩個子樹。而這兩個子樹形成的總數對數量是 size( T1 ) * size( T2 )  ( 記為 N )，所以這個節點的答案就會是兩個子節點的答案再加上 min ( M , N-M ) 。而在計算 M 的數量的時候，我們需要一個可以查詢一個數在某陀集合裡面大於幾個數的資料結構，所以會用到 treap 。並且我們還需要合併兩個 treap ，用啟發式合併即可。

因為 treap 懶得自己寫，於是借用了這裡的模板XD。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=200000+10 ;
 
typedef int type;
struct node{
 node *l,*r;
 int fix,size;
 type data;
 node(){
  l=r=NULL;
  fix=rand();
  size=1;
 }
 int lsize(){return l?l->size:0;}
 int rsize(){return r?r->size:0;}
};
struct treap{
 node *root;
 treap(){
  root=NULL;
 }
 int size()
 {
     return root ? root->size : 0 ;
 }
 inline void left_rotate(node *&a){
  node *b=a->r;
  a->r=b->l;
  b->l=a;
  a=b;
  b=a->l;
  b->size=b->lsize()+b->rsize()+1;
  a->size=a->lsize()+a->rsize()+1;
 }
 inline void right_rotate(node *&a){
  node *b=a->l;
  a->l=b->r;
  b->r=a;
  a=b;
  b=a->r;
  b->size=b->lsize()+b->rsize()+1;
  a->size=a->lsize()+a->rsize()+1;
 }
 void insert(node *&p,type data){
  if(!p){
   p=new node;
   p->data=data;
  }else{
   p->size++;
   if(data<p->data){
    insert(p->l,data);
    if(p->l->fix<p->fix)right_rotate(p);
   }else if(data>p->data){
    insert(p->r,data);
    if(p->r->fix<p->fix)left_rotate(p);
   }
  }
 }
 inline void insert(type data){
  insert(root,data);
 }
 int rank(node *p,type data,int cur){
     if(!p) return cur ;
  if(data==p->data)return p->lsize()+cur+1;
  else if(data<p->data)return rank(p->l,data,cur);
  else return rank(p->r,data,cur+p->lsize()+1);
 }
 inline int rank(type data){
  return rank(root,data,0);
 }
};
 
struct RET{ int id ; LL val ; };
treap s[maxn] ;
int scnt=0 ;
 
int tmp[maxn],tcnt ;
void dfs(node *u)
{
    if(!u) return ;
    dfs(u->l) ;
    tmp[tcnt++]=u->data ;
    dfs(u->r) ;
}
 
RET solve()
{
    int z ; scanf("%d",&z) ;
    if(z) { s[scnt++].insert(z) ; return (RET){scnt-1,0} ; }
    RET r1=solve() ;
    RET r2=solve() ;
    int x=r1.id , y=r2.id ;
    RET ret ; ret.val=r1.val + r2.val ;
 
    if(s[x].size() < s[y].size()) swap(x,y) ;
    int i=0 ;
    LL cnt=0LL , tot=((LL)s[x].size())*((LL)s[y].size()) ;
    tcnt=0 ; dfs(s[y].root) ;
    for(int i=0;i<tcnt;i++) cnt+=s[x].rank(tmp[i]) ;
    ret.val+=min(cnt,tot-cnt) ;
 
    for(int i=0;i<tcnt;i++) s[x].insert(tmp[i]) ;
    ret.id=x ;
    return ret ;
}
 
main()
{
    srand(time(NULL)) ;
    int n ; scanf("%d",&n) ;
    RET ans=solve() ;
    printf("%lld\n",ans.val) ;
}