0w1

Binary Search

Yuki 301 サイコロで確率問題 (1)

Problem Description: You have a dice with 6 faces, mapping to integer in 1..6. You roll the dice, and sum up them along the process. However, you will reset the sum to 0, when the sum has exceeded N. Find the expected number of rolls you h…

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…