Problem - 448C - Codeforces題意： 給不一定同高度的塔一排。油漆可以橫著刷也可以豎著刷，但橫著刷一次的時候，是不能跨過空的欄位。求最少要刷幾次才能刷好所有塔。數據範圍： 塔數 1 ≤ N ≤ 1e5 塔高度 1 ≤ H[ i ] ≤ 1e9解法： 遞迴考慮，最少塗刷次數可…

Problem - 519D - Codeforces題意： 給 26 個英文字母各自的花費，接著一個字串。求有多少子字串，滿足頭尾字母相同，且扣去頭尾字母後的花費總和為 0。數據範圍： 花費 -1e5 ≤ cost[ i ] ≤ 1e5 字串長度 1 ≤ | seq | ≤ 1e5解法： 先預處理前綴花費和，並做…

Problem - 276D - Codeforces題意： 給 L, R，求任一對 A, B，滿足 L ≤ A ≤ B ≤ R，可得的最大 A XOR B。數據範圍： 1 ≤ L ≤ R ≤ 1e18解法： 先將 L，R 轉換為二進制，若長度有差則補零在前頭。接著在這上面做動態規劃( 數位統計 )。 dp[ i ][ j ][ k ][ l ]…

Problem - 337D - Codeforces題意： 給一棵樹，和若干個指定節點，和 D。求有多少節點，滿足至最遠的指定節點的距離不大於 D。數據範圍： 指定節點數 M，樹大小 N，1 ≤ M ≤ N ≤ 1e5 0 ≤ D 解法： 以 0 為有根樹進行 DP dpd[ i ] : i 號節點與向下最遠的指定…

Problem - 120F - Codeforces題意： 給若干顆樹，現在連最少的邊使之連通，求連通後最大直徑。數據範圍： 樹數量 1 ≤ N ≤ 100 樹大小 2 ≤ s[ i ] ≤ 100解法： 求直徑總和即可。直徑的找法是，先對一任意一個點，找到其最遠點。該點至它的最遠點的距離即是直…

Problem - A - Codeforces題意： 給有序的名字表。求最長的字串長度，字串須能拆解成名字表裡的字，且順序須依照表中的順序，且連接的兩個字串，前面字串字尾需與後面字串字頭相同。最後的字串必須滿足字頭與字尾相等。數據範圍： 字串數 1 ≤ N ≤ 5e5 字串長…

Problem - C - Codeforces題意： 在一個桌子上，有 N 個武士兩兩相鄰等弧距坐著。每個武士都有心情好壞，求是否有一種武士的組合，滿足所有武士心情都好，且相鄰連接後是一個正多邊形( 同角同長度 )。數據範圍： 武士人數 3 ≤ N ≤ 1e5解法： 顯然要檢查的只…

Problem - 573B - Codeforces題意： 有若干個不一定相同高度的塔連續排成一排。每次操作會把滿足「上下左右其中一格子是空的」的所有單位為一的塊刪除。求幾次操作後才能將所有塔刪除。數據範圍： 塔數 1 ≤ N ≤ 1e5 塔高度 1 ≤ H[ i ] ≤ 1e9解法： 考慮一個…

Problem - 478D - Codeforces題意： 給兩種顏色方塊分別的數量，疊一座塔。塔的每一層顏色都必須相同，且頂層塊數為 1，每一層都必須比上面一層多恰一個方塊。求疊高度最高的塔的方案數。數據範圍： r: 紅方塊數量, g: 綠方塊數量, 0 ≤ r, g ≤ 2e5, 1 ≤ r + …

Problem - C - Codeforces題意： 給 A, B 陣列，求一組序列 { i1, i2, .. } 滿足 SIGMA{ A[ i ] } / SIGMA{ B[ i ] } = K。在此前提下，求 SIGMA{ A[ i ] } 的最大值。若無解則輸出 -1。數據範圍： 陣列大小 1 ≤ N ≤ 100 比例 1 ≤ K ≤ 10 陣列元素大小 1 ≤ A…

Problem - 461B - Codeforces題意： 給一顆樹，和每個節點是黑是白。求樹的分割組合數，滿足分割後的所有組合都恰有一個黒点，求其余数。數據範圍： 節點數 2 ≤ N ≤ 1e5解法： 樹形動態規劃寫起來真蛋疼。。。 將 0 作為根，轉換為有根樹上的問題。 dp[ i ][…

Problem - C - Codeforces題意： 給一個無向圖，保證任兩點之間至多存在一個路徑。接著若干比詢問，第一種詢問求某個點所在的連通塊裡的最遠距離( 直徑 )，第二種詢問須將兩個點所在的連通塊用最優方法，將一條邊兩端點分別連上兩連通塊中各一個點，使連接後…

Problem - E - Codeforces題意： 給一張帶權有向圖。求最長路徑長度，路徑滿足邊權嚴格遞增。數據範圍： 節點 2 ≤ N ≤ 3e5 邊數 1 ≤ M ≤ min( N * ( N - 1 ) / 2, 3e5 ) 邊權 1 ≤ W[ i ] ≤ 1e5 保證無自環，無重邊。解法： 先考慮將邊權小至大排序。此時發現…