Subscribed unsubscribe Subscribe Subscribe

0w1

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,接著把滿足所有前綴和後綴相等的長度押入一個有序容器。 接著對那個容器…

IOI 15 Sorting ( Binary Search + Greedy )

PEG Judge - IOI '15 - Sorting 首先我們要想到,如果 k回合內能完成,那麼 k + 1回合內一定也能完成,這是很顯然的,因為對方換了什麼,換回來就行了。所以我們可以進行二分搜,現在問題就簡化成要在O( n ) 判斷 k回合內可不可能達成。 接著要發現,設原始…

TOJ 72 Happiness Function ( 三分搜 )

http://sprout.tw/oj/pro/72/ 一個三分搜模板。每次總是縮小至少三分之一的搜索範圍,慢慢走往凹點。 #include <cstdio> int n; double a[10], b[10], c[10]; double S(double t){ double mx = 0; for(int i = 0; i < n; ++i) if(a[i]*(t-b[i])*(t-b[i])+c[i] > mx) </cstdio>…

JOI 10 本選 Bug Party ( Binary Search + MLE Persistent Segment Tree / AC Priority Queue )

Bug Party | Aizu Online Judge 很容易想到,如果固定最小值b,那麼我們必須由小到大拿進所有a,直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…

ABC 26 D - 高橋君ボール1号 ( Binary search + EPS )

D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder 精度が怖い。 出力するものがたとえ1e-10の誤差だけあったとしても関数が出るものに1e-5ぐらい影響がまだるので、ちゃんと限界まで行かないとやばい。 #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…

ABC 23 D - 射撃王 ( Binary search )

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder Search for the minimum height that is possible. Judge by the deadline, which should be pre-calculated and sorted. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXH = </bits/stdc++.h>…

CFR Educational 3 D. Gadgets for dollars and pounds ( Binary search )

Problem - D - Codeforces If a bound is set, i.e. to construct a way to buy k gadgets before some day x, we have an obvious greedy strategy where we will choose the cheapest currency days for both currency, then we will enumerate the number…

JOI 2011 春合宿 Guess Them All ( Binary Search, Interaction )

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day2.pdf guess: 数当て (Guess Them All) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 首先可以用 O( N )把 1的位置給找出來,接著對其他每個數字分別做區間的二分搜,找出它的位置。例如要找…

UVA 1555 Garland ( 二分 )

UVa Online Judge 移項一下就能得到方程式 h[ i ] = ( h[ i - 1 ] + 1 ) * 2 - h[ i - 2 ],所以只要前兩項確定,後面所有都會跟著唯一確定。前面的項越小,後面的項一定就成關係的一齊變小,所以二分枚舉第二項可不可行就好了。 注意輸出前要再呼叫一次 ok(…

UVA 1422 Processor ( 二分搜 + 置點問題 )

UVa Online Judge 馬上會想到二分搜最大速度,而判斷的部分就會變成經典的置點問題。每個點 ( 作業 )都有左界和右界,只能將它置於其中。一個經典的算法是先將每個點以其左界限制做排序,然後由左到右依次考慮每個位置該放置哪個點,這部分可以利用優先佇列…

CF 579E Weakness and Poorness ( Binary Search )

Problem - E - Codeforces We are to find x that will give minimum for max{ ABS( SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) ) Ɐ 1 ≤ i ≤ j ≤ n }. Let us first remove absolute and get max{ max{ SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) Ɐ 1 ≤ i ≤ j ≤ n }, max{ - SUM( a…

UVA 10816 Travel in Desert ( 最小瓶頸生成樹 + 最短路徑 / 二分 + 最短路徑 )

UVa Online Judge 可以先依據邊的溫度求最小瓶頸生成樹,但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra,運行時間一模一樣。 #include <bits/stdc++.h> using namespace std; const int </bits/stdc++.h>…

UVA 11478 Halum ( 二分 + 差分約束系統 )

UVa Online Judge 由於順序無關,我們可以將每個操作獨立出來,令 dsum( u ) 為作用在 u 上的所有 d 權和,那麼對於一個邊 u -> v,它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化,我們考慮二分搜尋,假設最小值的最大可能為…

UVA 11090 Going in Cycle!! ( 二分 + SPFA判負圈 )

UVa Online Judge 要求平均權值極大化,一個很常用的技巧是假設平均權值為 x,如果我們將全部的值減去 x以上的值,或全部減去 x - 1以下的值,前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環,所以我們發現我們可以二分搜尋最接近正確答案的 x,…