Problem - D - Codeforces 題意： N 個人排成一排，每秒隊首有 P 的機率進電梯，1 - P 的機率停留原地。求 T 秒後，期望有多少人在電梯裡。 解法： dp[ i ][ j ] : 已經過 i 秒，電梯裡有 j 個人的機率。 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] * P + dp[ i -…

Problem - D - Codeforces 題意： 給若干張卡片，每張卡片都有兩種屬性值，長度及價格。用相應的價格購買某張卡片後，可以擁有向左或向右跳對應的長度的次數不限的能力。求最小花費金額，使得可以跳到任意格子。 解法： 滿足可以跳到任意格子，等價於滿足所…

Problem - D - Codeforces 題意： 給 N 張卡片，各有固定的長寬( 不可調換 )，和一張必須是第一張的卡及其長寬，求最長的序列，滿足左邊的卡長寬皆嚴格小於右邊的卡。 解法： 首先刪去無法容下第一張卡片的所有卡片，就能無視第一張卡。接著對剩下的卡片做排…

Problem - C - Codeforces 題意： 給 M ( 數字長度 )，S ( 位數總和 )，求可能構造之最小數及最大數，或判定不可構造。 解法： 由於數據範圍不大，所以狀態設計成長度相同時比較，就可以直接用 string 和內建字典序比較進行 DP。 dp[ i ][ j ] : 已有 i 位數…

Problem - B - Codeforces 題意： 給兩個不一定等長序列，求最大配對數，使得每個配對的權值差不超過 1。 解法： dp[ i ][ j ] : 已考慮前 i 個第一序列的數，已考慮前 j 個第二序列的數，此時的最大配對數。 dp[ i ][ j ] = max{ dp[ i - 1 ][ j ], dp[ i ]…

Problem - B - Codeforces 題意： 給兩個序列，序列中的+表示向右走一個，-表示向左走一格，?表示一半機率向左，一半機率向右。求多少機率兩者終點相同。 解法： 求有多少 ? 以及有多少需要變成+，數學求機率。 string A, B; void init(){ cin >> A >> B; } …

Problem - D - Codeforces 題意： 有兩種食物，白色和紅色，吃的時候是吃一種排列，滿足白色的必須是連續 K 個。多筆詢問 [ l, r ]，輸出吃 [ l, r ] 各長度方案數其和。 解法： dp[ i ] : 吃 i 個的方案數 dp[ i ] = dp[ i - 1 ] + dp[ i - K ] const int M…

Problem - C - Codeforces 題意： 給一個序列，取 K 段相互不重疊的長度為 M 的連續區間，求可能最大權值和。 解法： dp[ i ][ j ] : 已考慮序列中前 i 個值，已取 j 塊連續區間，此時的最大權值和。 int N, M, K; vi A; void init(){ cin >> N >> M >> K; A…

Problem - A - Codeforces 題意： 給一個序列，修改至多一個元素，求最長可能的嚴格遞增序列長度。 解法： 預處理每個數至右最多能遞增多長，至左最多能遞減多長。接著枚舉改變的位子，更新答案。 int N; vi A; void init(){ cin >> N; A = vi( N ); for( in…

Problem - C - Codeforces 題意： 給 N, K, D，K 描述一顆樹，其任意一個節點向 K 個子節點有邊，權值分別是 1 至 K 。求有多少由跟出發的路徑，滿足其權值和為 N，且存在至少一個邊其權值不小於 K。 解法： 由於轉移是固定的，且權值和之間狀態具有單調遞增…

Problem - B - Codeforces 題意： 給一矩陣，格子上有權值。一個人由左上角向右或向下移動，至右下角。另一人由左下角向右或向上移動，至右上角。兩人會面恰好一次，該次權值不算，求兩人路徑權值總和。 解法： 預處理四個角分別到達某個格子能獲得的最大權…

Problem - B - Codeforces 題意： 給一排房間，其轉移點。第奇數次造訪某個房間時，會轉移到轉移點，否則向下一個房間移動。轉移點保證不在該房間之後。求最少要移動多少次，才會從起點移動到終點。 解法： 第一次 / 奇數次到某個房間 x 的時候，肯定第 x - …

Problem - C - Codeforces 題意： 給一個序列，接著多筆詢問。對於每筆詢問 [ l, r ] 需要輸出該區間中每一個質數是序列中多少數的因數，其總和。 解法： 序列中的任意一個數的貢獻是，它的質因數個數。反過來說，任意一個質因數的貢獻是序列中它的倍數個數…

http://codeforces.com/contest/349/problem/BProblem - B - Codeforces 題意： 給初始金錢和每一個數字產生的花費，數字可以以字串方式連接，求可造的最大數字。 解法： 透過最少花費，先計算最長長度是多少。接著貪心取當前不會讓最長長度無法達到的前提下…

Problem - C - Codeforces 題意： 給 1 ~ 10 重量的法瑪是否存在( 若存在則有無限多個 )，和一個數字 M。輸出一種方案，使得每次輪流放在天平左側右側，且每次放置後由較輕的變為較重的，一共放置 M 個法瑪。求存在否一個合法的序列，若有則輸出。 string se…

Problem - B - Codeforces 題意： 給一個序列，和一個長度 K。求兩個長度 K 的不重疊連續塊最大總和值，若有多解，求下標字典序最小。 解法： 先預處理某個數以後生出一個長度為 K 的連續塊最大總和值。接著枚舉答案左邊塊的右端，並利用前綴和更新答案。 in…

Problem - 327A - Codeforces 題意： 給一串 0 或 1 組成的序列，接著必須取一段連續的子序列將 0 和 1 皆反轉。求最長可能連續 1 的長度。 解法： dp[ i ][ j ] : 考慮序列中前 i 個值，還沒翻 / 正在翻 / 翻完了，時的最長長度。 int N; vi A; void init()…

Problem - 2B - Codeforces 題意： 給 N * N 的矩陣。由左上角出發，走到右下角，求經過的所有數之乘積最少的結尾零個數，以及其中一個方案。 解法： 先考慮整張矩形不存在 0。分別求起點至終點經過的最少 2 因數的數量，和最少 5 因數的數量。取其最小值即…

Problem - 289B - Codeforces 題意： 給 N * M 的整數值矩形，和一個數字 D。求是否可以只透過對值加或減 D 使得矩形最後所有值相同，以及最少步驟數。 解法： 若有解，使所有數成為中位數顯然是最優方案。因此檢查是否每個值都能成為原矩陣值的中位數。 int…

Problem - 279C - Codeforces 題意： 給一個序列 b 和若干筆詢問，對於每筆詢問 [ l, r ]，判斷是否存在一個 x，滿足 l ≤ x ≤ r 且 b1≤b[l+1]≤ b[l+2] ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ br。 解法： 對每個點預處理向右非遞減和非遞增各自能最多有多長。判…

Problem - 264B - Codeforces 題意： 給一個非遞減數列，求一個序列的最長長度，序列滿足相鄰數值皆不互質。 解法： 首先因為輸入保證非遞減，我們可以直接無視序的存在，由數值小至大考慮，從而少一個維度的複雜度。一個數對求解過程中的貢獻是，可以更新比…