Problem - 607B - Codeforces 非常神奇的一道題 題意： 給一個數列，每一次操作將一連續區間的回文刪除，刪除某區間後其左右會連接。求最少刪除數，使整個數列被刪除。 解法： dp[ i ][ j ] : 刪除原序列的 [ i, j ] 區間元素需要的最少操作數。 dp[ i ][ j …

Problem - 5C - Codeforces 題意： 給括弧序列，求連續區間之最長的合法匹配長度，和其數量。 解法： 對於每個閉括弧，預處理和其配對的開括弧位置，並藉以更新對應的最遠合法左界。如果當前這個閉括弧能配對，那麼最遠合法的左界就是其對應的開括弧左邊一個…

Problem - 567C - Codeforces 題意： 給一個數列和 K，求有多少三個元素構成的有序遞增等比子序列，其比為 K。 解法： 預處理，使可以查詢每個值存在於哪些位置，且這些位置是排序好的。接著枚舉中間的數字，左右邊的數字將會隨之確定，因此將答案增加指定數…

Problem - 550C - Codeforces 題意： 給一個大數，求任意刪除數字，使其為 8 的倍數。 解法： 如果有 0，那麼就變 0。否則基於 8 的倍數只與後三位有關的性質，進行動態規劃，紀錄 0 至 999 的數是否可以達到。 string _seq; void init(){ cin >> _seq; } vi…

Problem - 547b - Codeforces 題意： 給一組數列。對於 x for each 1 to N，輸出數列中，屬於連續 x 個元素構成的區間裡最小值的最大值。 解法： 由大的數字至小，每次將大的數字和左右的數字於並查集結構中，以位置為單位並在一起，若且為若左右的數比它本…

Problem - 545C - Codeforces 題意： 在一維空間中給一堆樹，用位置和高度描述。現在要砍樹，砍完可以選擇向其左方或右方倒，倒完後高度就會往那方向躺平佔據區間。求可以砍多少樹，使得任意點不被兩棵樹同時佔據。 解法： dp[ i ][ j ] : 考慮前 i 棵樹，最…

Problem - 543A - Codeforces 題意： 給 N, M, B, MOD, 分別是編程者數量，程式碼行數，可容忍的 bug最大上限數，和神秘餘數。接著一行給出各編程者一行會寫出多少 bug。從一號開始，每個編程者完成剩餘的行數中任意多個( 0 ~ 完成 )，求完成指定的程式碼行…

Problem - D - Codeforces 題意： 給若干個點和其權重，求最多一組點，使得任意兩點距離大於等於權重和。 解法： 將點看成圓心，權重看成半徑後，問題等價選最多一組點使得圓之間無重疊。由於上下的概念無意義，可以轉化為一維的區間不覆蓋問題。給若干個區…