0w1

Codeforces

CFR 815 C. Karen and Supermarket

Problem Description: There are N items, the i'th item costs C[i], and we have a coupon that can reduce its price by D[i]. However, for every coupon i to be effective, coupon X[i] must be used, i.e., i'th item bought. You have B units of mo…

CFR 825 F. String Compression

Problem Description: Given string S, find the minimum length of its running length encoding.Constraints: 1 ≤ len(S) ≤ 8000Solution: dp[i]: answer for S[0...i] dp[j] = min(dp[i] + cost(i, j) for i in 0...j) kmp[i]: maximum length of common …

CFR 843 D. Dynamic Shortest Path

Problem Description: You are given a directed weighted graph with N nodes and M edges. Q queries follow: OP = 1: Output the shortest path from node 1 to node V. OP = 2: Read C values, the C[i]'th edge should have its weight incremented by …

CFR 428 D. Winter is here

Problem Description: You are given an array A[] of N values. For each subset that has gcd greater than 1, its contribution is gcd * size_of_subset. Output the sum of contributions for every such subset, modulo 1e9 + 7.Constraints: 1 ≤ N ≤ …

CFR 444 C. DZY Loves Colors ( Segment Tree, Dummy Constraints )

Problem - 444C - Codeforces題意: 給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。 M 筆詢問,兩種形式: 1 l r x:將 [ l, r ] 都塗色為 x 2 l r:輸出 [ l, r ] 的貢獻總和 初始時所有元素的貢獻為 0。 當一個元素由 u 變為 v 時,增加貢…

CFR 522 D. Closest Equals ( Segment Tree )

Problem - 522D - Codeforces題意: 給你長度 N 的數列 A[]。 M 筆詢問,問 [ L, R ] 中,最近的相同元素距離是多少。若不存在,輸出 -1。制約: 1 ≤ N, M ≤ 5e5 abs( A[ i ] ) ≤ 1e9解法: 可以很快想到,給每一個位置 i 紀錄前一個 A[ i ] 的位置 pre[ i ]…

CFR 556 D. Restructuring Company ( Union Find )

Problem - 566D - Codeforces題意: 給你 N 個人,初始時他們自己一個組。 Q 筆詢問,三種形式: 1 x y:merge( x, y ) 2 x y:merge( x, x + 1, ..., y ) 3 x y:print "YES" if group( x ) == group( y ) else "NO"制約: 1 ≤ N ≤ 2e5 1 ≤ Q ≤ 5e5解法: …

CFR 639 C. Bear and Polynomials ( Hash )

Problem - C - Codeforces題意: 給你 N 次多項式 F()。 係數的絕對值不能超過 K。 問你修改一個值之後,F( 2 ) = 0 的方案數。 特別的,A[ N ] != 0。制約: 1 ≤ N ≤ 2e5 abs( K ) ≤ 1e9解法: 哈希水掉。 原本不能暴力算的原因只是因為數字會太大,不過哈…

CFR 526 D. Om Nom and Necklace ( KMP, Periodic )

Problem - D - Codeforces題意: 給長度 N 的字串,以及定數 K。 對於 i = [ 0 .. N - 1 ],問是否存在字串 A 和 B,使得 A + B + A + B .. + A = S[ 0 .. i ],其中 A 重複 K + 1 次,B 重複 K 次。 A, B 可為空字串。制約: 1 ≤ N, K ≤ 1e6解法: KMP 真是…

CFR 492 D. Vanya and Computer Game ( Binary Search )

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

CFR 611 D. New Year and Ancient Prophecy ( DP, Hash, LCP )

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

CFR 1 C. Ancient Berland Circus ( Geometry )

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

CFR 491 C. Deciphering ( MCMF )

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

CFR 62 E. World Evil ( Flow, Mincut, DP, bitmask )

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

CFR 434 D. Nanami's Power Plant ( Flow, Mincut )

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

CFr 811 D. Vladik and Favorite Game ( Interactive, Ad hoc )

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

CFR 811 C. Vladik and Memorable Trip ( DP )

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

CFR 513 F. Scaygerboss ( Flow, Binary Search )

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

CFR 739 E. Gosha is hunting ( MCMF )

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

CFR 78 E. Evacuation ( Flow )

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

628F - Bear and Fair Set ( Flow )

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

CFR 362 E. Petya and Pipes ( MCMF, Binary Search )

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

CFR 717 G. Underfail ( MCMF )

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

CFR 164 C. Machine Programming ( MCMF )

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 …

CFR 316 C. Tidying Up ( MCMF )

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

CFR 237 E. Build String ( MCMF )

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

CFR 277 E. Binary Tree on Plane ( MCMF )

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

CFR 730 I. Olympiad in Programming and Sports ( MCMF )

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

CFR 653 D. Delivery Bears ( Flow, Binary Search )

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

CFR 269 C. Flawed Flow ( Flow )

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