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 單位的牌組,但是這些牌的門檻必須不超過你的等級,並且任意兩張的魔法性質總和不為質數。 你現在的等級…
Problem - 808E - Codeforces題意: 有 N 個物品,你的背包容量為 M。第 i 個物品容量為 W[ i ],價值為 C[ i ]。求可容的最大可能價值總和。制約: 1 ≤ N ≤ 1e5 1 ≤ M ≤ 3e5 1 ≤ W[ i ] ≤ 3 1 ≤ C[ i ] ≤ 1e9解法: 如果只有兩種重量,那有多簡單。 考慮討…
Problem - 788E - Codeforces題意: 給長度 N 的數列 A[]。 這個數列代表士兵們,他們的強度。初始時所有士兵都是活著的。一個隊伍是合法的,如果他有 5 個人,令下標為 a 有 M 筆詢問,分為兩種: 1 x:反轉 x 號士兵的狀態 ( 保證活 -> 死 ) 2 x:反轉 x …
Problem - 794E - Codeforces題意: 給長度 N 的數列 A[]。現在輪流玩遊戲,選擇一個端點的元素,讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素,後手的目標是最小化最後一個元素。先手打算作弊,自己操作連續 K 輪後,當作…
Problem - 794D - Codeforces題意: 有 N 個城市,M 條路。如果存在,輸出一個方案,為每個城市 u 分配一個數字 X[ u ],使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約: N, M ≤ 3e5解法: 首先考慮這樣的一對城市 ( u, v ):它們的鄰接陣列,…
標ㄐㄧProblem - 794F - Codeforces題意: 給長度 N 的數列 A。有 Q 筆詢問,分兩種: 1 l r x y:代表要將 A[ l .. r ] 中所有 x 的數位變換成 y 2 l r:代表要輸出 A[ l .. r ] 的總和制約: N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9 For query type 1: y != 0解法: …
UVa Online Judge題意: 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。制約: 2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000 0 ≤ 容量 ≤…
No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…
Problem - 776C - Codeforces題意: 給你一個長度 N 的序列,以及 K。問有多少個區間的總和是 K 的非負整數次方。制約: The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection …
Problem - E - Codeforces題意: 有 N 個商品,用價格描述。你一共要選擇 M 樣物品,使得 Masha 喜歡其中至少 K 件,Arkady 也喜歡其中至少 K 件。問最小花費,無解輸出 -1。制約: The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤…
Problem - D - Codeforces題意: 你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤,但是容的時候邊之間必須平行或垂直。你有 N 個放大燈,選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈,問至少要用幾個放大燈…
Problem - C - Codeforces題意: 有 N 樣物品,用價格和價值描述。一樣物品可能是要用 C 類貨幣購買,也有可能是要用 D 類貨幣購買。選兩個相異的物品購買,使得價值總和最大。輸出價值總和。制約: The first line contains three integers n, c and d (2 ≤…
Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…
Problem - A - Codeforces題意: 有 N 張卡牌,正面和反面各有一個非負整數。現在兩個人玩遊戲,每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭,進行 Nim 的遊戲。雙方絕頂聰明的前提下,先手贏的機率為何。制約: T…
CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )
Problem - F - Codeforces題意: 有 N 隻老鼠,用座標描述。有 M 個洞,用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何,才能使所有老鼠進洞。制約: 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…
Problem - D - Codeforces題意: 問 [ L, R ] 之間有多少整數,是可以被自身的所有非零數位整除。制約: T ≤ 10 1 ≤ L, R ≤ 9e18解法: 考慮 [ 1, x ] 的動態規劃: 一個顯然的狀態可以這樣定義: dp[ i ][ j ][ k ][ l ]: 考慮前 i 位,模 lcm( 1, 2, .. 9 …