Problem - D - Codeforces題意： 有 K 種卡片，每天都可以抽一張，抽到的種類機率分佈是隨機均勻。Q 筆詢問，問第幾天開始可以確定，對於任意一種卡片，有 P / 2000 的機率有至少一張。資料規模： First line consists of two space separated integers k, q…

Problem - E - Codeforces題意： 給一個由 '+', '*', '0' ~ '9' 組成的合法數式，要求在任意合法的位置插入一對括弧，求最大可能結果。資料規模： The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digi…

Problem - C - Codeforces題意： 給一個長度為 N 的數列，要做 K 次操作。每次將數列排序後，奇數項 ( 1 based ) 和 X 做 xor，偶數項不變。問所有操作結束後，數列的長相。資料規模： First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤…

題意： 有些整數點上有朋友，每個朋友有個最高速率。問所有朋友集結到任意實數點需要的最短時間。資料規模： The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends. The second line contains n integers x1, x2, ..., xn (1…

Problem - C - Codeforces題意： 給一個 N * M 的矩陣。K 筆詢問，每次問 [ L, R ] 範圍的行是否存在一個列，使得在 [ L, R ] 之間為非遞減。資料規模： The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the num…

Problem - D - Codeforces題意： 你有 N 個牛奶，第 i 瓶會在 A[ i ] 天後壞掉。商店有 M 個牛奶，第 i 瓶會在 B[ i ] 天後壞掉。你一天喝至多 K 瓶牛奶，問最多可以買多少牛奶，使得你不必喝任何壞掉的牛奶。資料規模： N, M ≤ 1e6 過期天數 ≤ 1e7 TL: 2000…

Problem - C - Codeforces題意： 給一棵節點帶權的樹。問是否存在一種分割方法，使得可以分成三個非空子樹，使得權重總和相同。輸出方案。資料規模： The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

Problem - C - Codeforces題意： 你的目標濃度是 N / 1000。你有 K 種液體，濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量，求最小正整數，代表使用的總容量成功調配出目標濃度。資料規模： The first line contains two integers n, k (…

Problem - B - Codeforces題意： 給一個 N 點 M 邊的無向圖，問有幾種方法，可以經過 M - 2 個邊洽兩次，剩下 2 個邊洽一次。沒有重邊，但可能有自環。兩個方法不同，若且唯若拜訪洽一次的任意一邊不同。資料規模： The first line contains two integers n,…

Problem - A - Codeforces題意： 給一個長度為 N 的數列 A[]。求最大的 f( l, r )，滿足 1 ≤ l 資料規模： The first line contains single integer n (2 ≤ n ≤ 1e5) — the size of the array a. The second line contains n integers a1, a2, ..., an (-1e9…

Problem - E - Codeforces題意： 給 N 種球的個數 A[]。要求按照下列規則將其分箱： 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下，可以用最少…

Problem - D - Codeforces題意： 給一個完滿二元樹，用最大編號描述。二元樹上的編號是遞迴配置的，如圖： 給 Q 筆詢問，每筆詢問給起點編號，以及操作字串，字串由 { 'U', 'L', 'R' } 組成，對於不可執行的操作無視之。問終點編號為何。資料規模： The firs…

Problem - C - Codeforces題意： 給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 3 的倍數。刪除後不得有前導 0。輸出方案。資料規模： 長度 ≤ 1e5解法： 刪除最少等價於保留最多。 dp[ i ][ j ] : 已考慮前 i 個數字，現在除以 3 餘 j，此時最大保…

Problem - C - Codeforces題意： 給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串，使得最多處切下去會是迴文。資料規模： N ≤ 26 出現頻度總數不超過 1e5解法： 因為至少要有一個迴文就必須有不超過一個奇數的頻度，所以接下來可以分開討…

Problem - B - Codeforces題意： 有 N 個技能，所有技能都用一個數值描述，上限皆為 A，你有 M 單位的金子，一個單位的金子可以提升一個技能的數值一個單位。你要最大化：數值為 A 的技能數量 * Cf + 最低的技能數值 * Cm。求最大化的值以及方案。資料規模：…

Problem - A - Codeforces題意： 給一個代表自轉中心的座標，以及順時針給的座標描述一個凸多邊形。問旋轉 360 度後，被覆蓋過的面積有多少。資料規模： N ≤ 1e5解法： 顯然要找離圓心的最遠點，以及最近點... 但仔細想想會發現不是最近點，其實是和任意線段…

Problem - C - Codeforces題意： 給一個圖，要求放 K 個機器人並給出每個機器人的路徑，路徑長至多為 ceil( 2 * N / K )，使得所有節點都被至少一個機器人拜訪過。資料規模： N, M ≤ 2e5解法： 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS，…

Problem - B - Codeforces題意： 給 N 個姓名，現在要為每個姓名做縮寫，但希望滿足以下規則： 1. 姓名是 A 的前三個字元，或 A 的前兩個字元接上 B 的第一個字元。 2. 任何縮寫不重複 3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的…

Problem - A - Codeforces題意： 給一棵 N 個節點的樹，要求給每個節點著色，滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模： N ≤ 2e5解法： 隨便找一個節點當作根，轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…

Problem - C - Codeforces題意： 給一個長度為 N 的陣列，用顏色描述。要求對於所有 K 資料規模： N ≤ 1e5解法： 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉，但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論：「答案的種類大約在 …

Problem - B - Codeforces題意： 給一張圖，N 個點，Q 個邊，起點 S。 邊有三種，各自用 u, v / L, R, w 描述： 1. u -> v : 代價 w 2. u -> [ L, R ] : 代價 w 3. [ L, R ] -> u : 代價 w 問所有終點的單源最短路徑，不存在則輸出 -1。資料規模： N, Q ≤ 1e…

Problem - A - Codeforces題意： 有 n 個星球，從 0 開始編號，順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合，遊戲採取輪流操作，每次操作時選擇自己的集合裡的一個數字，將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利…

Problem - B - Codeforces題意： 給一個字串，你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模： N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法： 因為 K 很小，所以按字典序小的出隊，接上自己後一個字符再丟回一個優先隊列…

Problem - 228E - Codeforces題意： 給 N 個點 M 條邊，邊有邊權 0 或 1。每次操作選取一個點，將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1，若有則輸出方案。資料規模： N ≤ 100 解法： 考慮每個邊，其實只能被兩端點…

Problem - D - Codeforces題意： 問有多少 A, B, C 數列的組合，使得 ( A[ i ] + B[ i ] ) % N = C[ i ]，且 A, B, C 都是 [ 0, N ) 的排列。資料規模： The single line contains integer n (1 ≤ n ≤ 16). TL: 1500 ms ML: 256 MB解法： 有用到這題的結論，…

Problem - 19B - Codeforces題意： 有 N 種商品各一個，若購買第 i 種商品，需要花費 C[ i ] 單位的錢，但是可以得到 T[ i ] 單位的店員不注意的時間，而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。資料規模…

Problem - C - Codeforces題意： 給一個長度為 N 的大寫英文字母組成的字串，一次操作可以將任一兩相鄰字符交換，問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模： The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…

Problem - 13C - Codeforces完全就是同一個題 只是這題要滾動才不會 MLE，然後詢問的是非遞減，所以不需要用到減下標的技巧。題意： 給一個陣列 A，可以任意讓值 +1 或 -1 任意多次，問最少要幾次才能將 A 變成非遞減數列。資料規模： MAXA ≤ 1e9 N ≤ 5000 T…

Problem - 11D - Codeforces題意： 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模： N ≤ 19 TL: 2000 ms解法： 考慮一個環，選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊，假設原本是 abcd 這樣的環，那其實可以用點的集合和…

Problem - 8C - Codeforces題意： 給原點 ( sx, sy )，以及 N 個座標 X, Y。每次至多選兩個座標，依序拜訪完後，回到原點。問最好的路徑，使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。資料規模： The first line of the input file contains the…