Problem - 234C - Codeforces 題意： 給一個序列，改變最少的數字使得存在一個邊界使得左邊都是負數，右邊都是正數。 解法： 預處理正、負數數量的前綴和，接著枚舉邊界更新答案 。 int N; vi T; void init(){ cin >> N; T = vi( N ); for( int i = 0; i < N…

Problem - 225C - Codeforces 題意： 給 N * M 的圖，每個格子表示黑白。求修改顏色至合法的最少步數。每一直列必須是同一顏色，且同一顏色不能連續低於 X 或超過 Y 列。 解法： 預處理每一列變成某一顏色的 cost。 cost[ i ][ j ] : 第 j 列的所有顏色變白…

Problem - 219C - Codeforces 題意： 給一個字串，求為使所有相鄰字母相異，需要修改最少次數的方法。 解法： dp[ i ][ j ] : 使前 i 個字母合法，最後一個字母為 'A' + j，此時的最少修改數。 dp[ i ][ j ] = min{ min{ dp[ i - 1 ][ k ] | k ≠ j }, dp[ i …

Problem - 204A - Codeforces 題意： 求 [ l, r ] 中，第一個位數等於最後一個位數的數字數量。 解法： dp[ i ][ j ][ k ][ l ] : 考慮前 i 個位數，已嚴格小於對照數，第一個位數，最後一個位數，滿足這些條件的狀態數。 注意當 k == 0 的時候若要轉移，那…

Problem - 189A - Codeforces 題意： 給繩子長度和三種可裁切的長度，一個合法的裁切是所有結果的繩子的長度都是三種可裁切的長度之一，求最多可能裁切的繩子數。 解法： dp[ i ] : 考慮長度 i 的繩子已裁切完，此時最多的繩子數。 dp[ i ] = max{ dp[ i - A…

Problem - 166E - Codeforces 題意： 在一個四角錐上，求有多少路徑可以恰好 N 步從起點返回到起點。 解法： dp[ i ][ j ] : 考慮前 i 個步，最後在 j 號點時的方法數 dp[ i ][ j ] = SIGMA{ dp[ i - 1 ][ k ] | k ≠ j } int N; void init(){ cin >> N; } vv…

Problem - 165C - Codeforces 題意： 給一個數字 K 和一個二進位數，求其有多少子字串有恰好 K 個位元是 1。 解法： 預處理前綴和，和各個前綴和出現幾次。 pS[ i ] : 前 i 個位元的前綴和 f2c[ i ] : 某個前綴和出現幾次 此時若 K == 0，答案便是 SIGMA{ ( …

Problem - 161D - Codeforces題意： 給一棵樹，求滿足距離為 K 的點對數。 解法：O( N * K ) cdis[ u ][ i ] : count of nodes v, such that v is part of the subtree of u, and is exactly i edges aways from u cdis[ u ][ i ] = SIGMA{ cdis[ v ][ i - 1…

Problem - D - Codeforces 題意： 給一個字串s，求有多少整數組 ( a, b, x, y ) 滿足 s[ a .. b ] 為回文且 s[ x .. y ] 為回文。 解法： 先O( | S | ^ 2 )預處理使得可以用常數時間判斷一個子字串是否為回文。再額外預處理前綴和 spal[ t ] 存儲前 t 個字母…