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