D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder題意： 給長度 3 * N 的數列 A[]。刪除 N 個元素後，希望前 N 個元素總和 - 後 N 個元素總和最大。制約： N ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法： 考慮一條線，從 N 掃描到 2 * N。 這條線會將數列分成兩塊，…

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder題意： 把巧克力沿著線切，分成三個非空的塊。 問最大和最小的塊的面積差最小是多少。制約： 2 ≤ H, W ≤ 1e5解法： 只可能有兩種切法 | | | 或 | -。90 度旋轉再做一樣的事情。 第一刀切下去之後顯…

https://www.hackerearth.com/challenge/competitive/may-circuits-17/algorithm/zulu-visits-wonderla-1/題意： N 層的地下迷宮，M 種物品。 在時間 x，你能拿第 i 個物品若且唯若所有 Level 比 Level[ i ] 小的物品的過期時間不早於 x，並且 x + Time[ i ]…

https://www.hackerearth.com/problem/algorithm/zulu-and-alarm-clock-1/題意： T 筆測資。 N 個鬧鐘，K 個時間。 你要把 K 個鬧鐘調成這 K 個時間。 你可以上下調整時、秒、分，會進位退位。 問最小調整次數。制約： 1≤T≤2 1≤N≤50 1≤K≤17解法： 可以用遮罩…

Problem - 492D - Codeforces題意： 甲 1 / X 秒攻擊一次，乙 1 / Y 秒攻擊一次。 對於第 i 隻怪獸，其耐打 A[ i ] 次，問最後一擊是誰的。制約： 1 ≤ N ≤ 1e5 1 ≤ X, Y ≤ 1e6 1 ≤ A[ i ] ≤ 1e9解法： 二分搜打死怪獸的最早時間。 只要知道這個時間，判斷一…

Problem - 611D - Codeforces題意： 給你一個大數。要求分割成若干個數字，滿足嚴格遞增，而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約： 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法： dp[ i ][ j ]：最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…

Problem - 1C - Codeforces題意： 有一個正 N 邊形，給你其中三個點，問最小可能面積。制約： 保證最佳的 N 不超過 100。解法： 用餘弦定理求的三個角分別多少。 用正弦定理求外接圓半徑。 枚舉 N，如果三個圓心角都是 360 度 / N 的整數倍，那麼就能直接算…

Problem - 491C - Codeforces題意： 給你長度 N 的字串 A 以及字串 B。 你可以做一組字母對字母的一對一映射，使得同位置相符的字符數量最多。制約： 1 ≤ N ≤ 2e6 1 ≤ K ≤ 52解法： MCMF 亂流。 映射前映射後。 源點建弧到映射前的容量是 1，費用是映射前的…

Problem - 62E - Codeforces題意： 給一個多角形柱體形成的網路，問最大流是多少。 起點是上面的面的所有點，匯點是下面的面的所有點。制約： 2 ≤ N ≤ 5 2 ≤ M ≤ 1e5 解法： 顯然不能暴力跑網路流算法。 考慮用 dp 求解。 最大流不好求，求最小割。 考慮水平…

Problem - 434D - Codeforces題意： 有 N 個二次函數，以及 M 條不等式。 你想要最大化所有二次函數的輸出的總和。 對於第 i 個二次函數，參數範圍是 [ L[ i ], R[ i ] ] 的整數。 第 i 條不等式表示 X[ U[ i ] ] ≤ X[ V[ i ] ] + D[ i ]。 問最大輸出總和。…

Problem - 811D - Codeforces題意： 給一張地圖，有些是炸彈，走上去馬上死。 起點在左上角，目標是 'F'。 你可以上下左右移動，但是上和下的控制可能是反的，左右也是。 互動走到 F。 操作數不可超過 2 * N * M。制約： 1 ≤ N, M ≤ 100 保證有至少一條路徑…

Problem - 811C - Codeforces 題意： 給長度 N 的數列 A[]。你想要取出若干個連續數列，使得每個數列中相異元素的 XOR 和，之和最大。 但是有個條件，如果某個元素 x 在取出的某個數列裡，那麼所有元素 x 都必須在該數列中。制約： 1 ≤ N ≤ 5000 0 ≤ A[ i ] …

Problem - 513F2 - Codeforces題意： 有個 N * M 棋盤，有些格子是障礙。 有一個怪盜，以及 Males 個男生，Females 個女生。 這些人都會用 r, c, t 表示座標位置以及移動一單位距離所需要的時間。 問至少要多少時間，才能使每個人都恰好和一位異性在同一個格…

Problem - 739E - Codeforces題意： 你有 A 個普通球，B 個超級球。 有 N 隻神奇寶貝。 對於第 i 隻神奇寶貝，如果用普通球，抓到的機率是 P[ i ]; 如果用超級球，抓到的機率是 U[ i ]。 對於同一隻神奇寶貝，兩種球都只能至多丟一次。 問最佳策略下，期望可…

Problem - 78E - Codeforces題意： 在 N * N 的地圖上，有一些格子是障礙物，有些有若干個科學家，有些有若干個氧氣筒。 在時刻 0，某個障礙物腐朽瓦解，發出毒氣，並向相鄰非障礙物的格子以一單位時間一格的速率擴散。 科學家只要移動到有氧氣筒的地方，就…

Problem - 628F - Codeforces題意： 有人說：他有 N 個數字，範圍在 [ 1, B ]。 他告訴你 Q 個式子，第 i 個為： [ 1, upTo[ i ] ] 之間有 quantity[ i ] 個數字。 除此之外，N 個數字 % 5 == [ 0 .. 4 ] 的數量是相等的。 問是否有可能。制約： 5 ≤ N ≤ B ≤…

Problem - 362E - Codeforces題意： 有 N 個節點，以及有向弧，用鄰接矩陣表示。 若 C[ i ][ j ] = 0，代表 ( i, j ) 之間沒有弧。 源點 1，匯點 N。 對於一個弧，可以花費一單位的金子增加一單位流量。 你有 K 單位的金子，問最大流量。制約： 2 ≤ N ≤ 50 0…

Problem - 717G - Codeforces題意： 給長度 N 的字串 T。 有 M 種字串 S[]，如果把第 i 個字串疊在 T 的上面重合，可以得到 P[ i ] 分。 對於 T 的所有位置，都不能有超過 X 個字符疊在上面。 問最大總得分。制約： 1 ≤ N ≤ 500 1 ≤ M ≤ 100 1 ≤ P[ i ] ≤ 10…

Problem - 164C - Codeforces題意： 你有 K 個機器，可以獨立處理任務。 你有 N 個任務可以選擇接或不接。 任務 i 需要在 [ S[ i ], T[ i ] ) 期間佔用一個機器，價值為 C[ i ]。 問最大總價值。制約： 1 ≤ N ≤ 1000 1 ≤ K ≤ 50 1 ≤ S[ i ], T[ i ] ≤ 1e9 1 …

Problem - 316C2 - Codeforces題意： 給一個 N * M 的矩陣，裡面有 N * M 個數字，[ 1, N * M / 2 ] 各出現兩次。 問最少要將幾個格子裡的數字移位，才能使得存在一種匹配，每個匹配都是相鄰的兩格子，且內容相同。制約： 2 ≤ N * M ≤ 80解法： 用最大流保證…

Problem - 237E - Codeforces題意： 你有一個目標字串 T。 你有 N 個字串。 如果你拿第 i 個字串裡面的某個字符，每拿一個花費 A[ i ]。 拿掉的字符不能再拿。 問總花費。無法則輸出 -1。制約： 1 ≤ N ≤ 100 0 ≤ A[ i ] ≤ 100解法： MCMF 隨便流。 把 T 拆成…

Problem - 277E - Codeforces題意： 有 N 個點在二維整數坐標上。 要求做一個二叉樹。 一個點 i 可以作為點 j 的父親，若且唯若 Y[ i ] > Y[ j ]。 問最小的邊長總和。若無解輸出 -1。制約： 2 ≤ N ≤ 400 abs( X[ i ] ), abs( Y[ i ] ) ≤ 1000 所有點相異 容…

Problem - 730I - Codeforces題意： 有兩個屋子，容量分別為 P, S。 有 N 個人，他們會各自選擇一個屋子進去。 第 i 個人對屋子 A 的喜好度是 A[ i ]，對屋子 B 的喜好度是 B[ i ]。 輸出方案，使得滿意程度 ( 選擇的屋子的喜好度 ) 總和最大。制約： 2 ≤ N …

Problem - 653D - Codeforces題意： N 個節點 M 條有向邊的圖。有 X 隻熊。起點 1，終點 N。 這些熊要搬運貨物，如果一隻熊要搬運 W 單位，那麼其他所有熊也必須搬運 W 單位。 每條邊都有限制重量，也就是經過的重量總和不能超過它。 問可以搬運的最大總重量…

Problem - 269C - Codeforces izrak の提出見て回答。題意： 給你一張無向圖，邊有容量，要求定向，使得有最大流。源點 1，匯點 N。制約： 2 ≤ N ≤ 2e5 N - 1 ≤ M ≤ 2e5 C[ i ] ≤ 1e4解法： 初始時對所有邊的端點添上該邊的容量。 為了要滿足流量守恆，也就…

Problem - 510E - Codeforces題意： 給長度 N 的數列 A[]。要求將每個元素分別放在某個圓桌裡，一個圓桌必須滿足以下條件： 每個元素和兩個元素相鄰。 相鄰元素的和必須是質數。制約： 3 ≤ N ≤ 200 2 ≤ A[ i ] ≤ 1e4解法： 和是質數，那麼偶數一邊，奇數一邊…

Problem - 546E - Codeforces題意： 有 N 個城市，M 條無向邊。 起初第 i 個城市有 A[ i ] 個士兵。 現在進行一次移動，每個士兵都可以選擇不動，或者移動到相鄰的城市。 輸出方案，使得移動後第 i 個城市有 B[ i ] 個士兵。若不存在方案，輸出 -1。制約： 1…

Problem - 589F - Codeforces題意： 有 N 種菜，你想要全部都吃一樣多的時間。 第 i 道菜可以吃的時間是 [ A[ i ], B[ i ] )。 只能在整數區間內吃菜，而且是至多一道。 問你最多可以吃多久時間。制約： 1 ≤ N ≤ 100 0 ≤ A[ i ] 解法： 二分搜答案，每次重新…

Problem - 498C - Codeforces題意： 給長度為 N 的數列 A[]。 有 M 筆操作： u v：選一個 A[ u ] 和 A[ v ] 的公因數 g，進行 A[ u ] /= g, A[ v ] /= g，保證 ( u + v ) % 2 == 1 問最多能有幾次，你選的公因數 g 不為 1。制約： 2 ≤ N ≤ 100 1 ≤ M ≤ 100 1…

Problem - 808F - Codeforces題意： 你有 N 張卡。第 i 張卡有 P[ i ] 單位的力量，C[ i ] 單位的魔法性質，L[ i ] 的門檻。 你想組一個總力量不小於 K 單位的牌組，但是這些牌的門檻必須不超過你的等級，並且任意兩張的魔法性質總和不為質數。 你現在的等級…