0w1

Binary Search

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 513 F. Scaygerboss ( Flow, Binary Search )

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

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 653 D. Delivery Bears ( Flow, Binary Search )

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

CFR 589 F. Gourmet and Banquet ( Flow, Binary Search )

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

CFR 808 F. Card Game ( Flow, Binary Search )

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

CFR 799 E. Aquarium decoration ( Binary Search )

Problem - E - Codeforces題意: 有 N 個商品,用價格描述。你一共要選擇 M 樣物品,使得 Masha 喜歡其中至少 K 件,Arkady 也喜歡其中至少 K 件。問最小花費,無解輸出 -1。制約: The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤…

CFR 806 C. Prairie Partition ( Binary Search, Greedy )

Problem - C - Codeforces題意: 考慮一種整數的拆分方式,將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數,進行這樣的拆分後,排序好,現在給你。問所有可能的原序列長度。制約: The first line contain…

CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )

Problem - 609F - Codeforces題意: 有 N 隻青蛙在一維數線上,用位置和舌頭長度描述。現在依序有 M 隻蚊子出現,用位置和營養值描述。一個在位置 x,舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t,而且這隻青蛙是所有能吃到這隻蚊子的…

HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意: 給 N 個元素,問最小的 x ,使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約: 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法: 經典題,開 log 比較,二分搜 x。時間 / 空間複雜度…

CFR 803 D. Magazine Ad ( Binary Search )

Problem - D - Codeforces題意: 要求在 K 行以內,用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭,也不會有連續的 '-' 或是連續的空白。制約: The first line contains number k (1 ≤ k ≤ 1e5). T…

HR Spanning Tree Fraction ( 最優比例生成樹, Binary Search, Spanning Tree )

Programming Problems and Competitions :: HackerRank題意: N 個點 M 個邊,第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹,使得 sum( a ) / sum( b ) 最大。制約: 2 ≤ N ≤ 1e5 N - 1≤ M ≤ 1e5 1 ≤ a[ i ], b[ i ] ≤ 100解法: 裸的最優比例生成樹。 聽…

GCJ 2017 R1B A. Steed 2: Cruise Control ( Binary Search )

Dashboard - Round 1B 2017 - Google Code Jam嗯..? 好像根本就不用二分搜題意: T 筆測資。你在數線上的原點,目的地是 D。除了你現在騎著的馬,一共有 N 隻馬,任兩隻不共享位置的處於某整數位置,並有一個最高速度的屬性描述。當後面的馬追上前面的馬時,…

CFR 795 L. Bars ( Binary Search )

Problem - L - Codeforces題意: 有 N 天,你有 K 個巧克力棒。第一天和最後一天一定是空的,而且你一定要吃巧克力棒。其他天有些要工作,所以那些天不能吃巧克力棒。問最佳的安排下,你最少的最多不能吃巧克力棒的連續天數。制約: The first line contains…

CFR 780 B. The Meeting Place Cannot Be Changed ( Binary Search )

題意: 有些整數點上有朋友,每個朋友有個最高速率。問所有朋友集結到任意實數點需要的最短時間。資料規模: 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…

CFR 767 D. Cartons of milk ( Binary Search, Counting Sort )

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

CFR 792 D. Paths in a Complete Binary Tree ( Ad hoc, Binary Search )

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

CFR 613 B. Skills ( Binary Search )

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

POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met題意: 有 M 個環狀的地,每個地屬於一個人。有 K 次隕石事件,每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人,每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個…

POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod題意: 給一個序列 B,問是否有一個 [ 1, | B | ] 的排列 A,使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。資料規模: In the first line of the standard input there is a positive integer …

CFR 589 G. Hiring ( Segment Tree, Binary Search )

Problem - G - Codeforces題意: 給 M 個工作時間,N 個人的特徵 D[ i ] 與 R[ i ],代表第 i 個人在一天工作時,需要前 D[ i ] 單位時間預熱,然後才能開始算入工作時數,而每一天的工作時數總和起來需要 R[ i ]。問分別每個人會在第幾天做完他的作業,做不…

CFR 431 D. Random Task ( Binary Search, Digit DP )

Problem - 431D - Codeforces題意: 給 M, K。求一個 N,滿足 1 ≤ N ≤ 1e18 且在二進制下,[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模: The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法: 直覺…

CFR 484 B. Maximum Value ( Math, Binary Search, Harmonic Series )

Problem - 484B - Codeforces題意: 給 N 個數字的數列 A。求最大的 A[ j ] % A[ i ],滿足 A[ j ] ≥ A[ i ]。資料規模: N ≤ 2e5 max{ A } ≤ 1e6解法: 首先發現相同的值是沒有用的,所以 unique() 一下。此時就能因為 Harmonic Series 想到每個數的倍數數…

CFR 360 B. Levko and Array ( DP, Binary Search )

Problem - B - Codeforces題意: 給一個數列,可以更改至多 K 個數,使成為任意數,求更改後最小的相鄰值絕對差。資料規模: The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2000). The second line contains space-separated integers a1, a2,…

CFR 645 D. Robot Rapping Results Report ( Graph, TopoSort, Binary Search )

Problem - 645D - Codeforces題意: 有 N 個機器人打鬥,機器人之間勝負是依戰鬥力的大小關係定的,而所有機器人的戰鬥力相異。依順序給機器人編號 u[ i ], v[ i ],表示編號 u[ i ] 的機器人戰鬥力比 v[ i ] 的機器人高。求第幾個資訊開始能確定所有機器人…

CFR 738 C. Road to Cinema ( Binary Search )

Problem - C - Codeforces題意: 給很多車,用價格和油箱容量描述。給加油站,用位置描述。過加油站時油箱會免費加滿油。起點 0 終點 S,求最便宜的車,可以不超過 T 分鐘到達終點。對每一單位距離都有兩種移動方式,用一單位的油兩分鐘過,或用兩單位的油一…

Yuki 131 マンハッタン距離 ( Binary Search )

No.131 マンハッタン距離 - yukicoder よくわかんないけど、とにかく二分探査! #include <bits/stdc++.h> using namespace std; signed main(){ int x, y, d; cin >> x >> y >> d; x = min( x, d ); y = min( y, d ); if( not ( x >= y ) ) swap( x, y ); int a = -1; int </bits/stdc++.h>…

CFR 147 B. Smile House ( Binary Search, Fast Matrix Multiplication, DP, Binary Enumeration )

Problem - B - Codeforces題意: 給一個圖,邊用四個值表示,( x, y, Cxy, Cyx ),代表 x 至 y 長度是 Cxy,y 至 x 長度是 Cyx。求是否存在一個正環,若存在則輸出最小環的長度。資料規模: 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …

CFR 255 C. Almost Arithmetical Progression ( Binary Search + DP )

Problem - 255C - Codeforces題意: 給一個序列。求一個最長子序列的長度,子序列滿足相鄰的數字的差是正負交替。ex: 10, 20, 10, 20數據範圍: 序列長度 1 ≤ N ≤ 4000 元素大小 1 ≤ B[ i ] ≤ 1e6解法: 對每個元素預處理出現在哪些位置。接著考慮動態規劃 d…

CFR 126 B. Password ( Hash + Binary Search )

Problem - 126B - Codeforces 題意: 給一個字串,求最長子字串,滿足存在一個前綴和它相等,一個後綴和它相等,一個非前綴也非後綴也和它相等。 解法: 先預處理字串的 rolling hash,接著把滿足所有前綴和後綴相等的長度押入一個有序容器。 接著對那個容器…