Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 799 D. Field expansion ( Dummy Constraints, Greedy )

Problem - D - Codeforces題意: 你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤,但是容的時候邊之間必須平行或垂直。你有 N 個放大燈,選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈,問至少要用幾個放大燈…

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 806 B. Dynamic Problem Scoring ( Dummy Constraints, Greedy )

Problem - B - Codeforces題意: 有 N 個人參加比賽,有五題,每個人的參數是五題的答對時間,沒有答對則以 -1 表示。一個人在一個題目的得分是這樣計算的: 考慮一個題,令 p 為答對人數,q 為參賽人數,則 p / q 對應到表格中的該題的最大分數。 對於一個…

ARC 073 E - Ball Coloring ( Greedy )

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個箱子,裡面有兩個球,球有各自的重量。對於每個箱子,都需要將其中一顆球放到袋子 A,另一顆放到袋子 B。一個袋子的價值是其中最大的重量和最小的重量的差。求最小的價值乘積。制約…

CFR 803 C. Maximal GCD ( Greedy )

Problem - C - Codeforces題意: 給 n, k,要求構造一個數列,數列長度必須是 k,元素總和必須是 n,而且要是嚴格遞增的。在此前提下,數列的 gcd 要最大。若不存在解則輸出 -1。制約: The first line consists of two numbers n and k (1 ≤ n, k ≤ 1e10).…

CFR 803 A. Maximal Binary Matrix ( Greedy )

Problem - A - Codeforces題意: 構造一個字典序最大的 N * N 的 01 矩陣,其中洽有 k 個 1,而且對於主對角線是對稱的。若不存在則輸出 -1。制約: The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 1e6).解法: 首先若 K > N * N 顯…

Yuki 421 しろくろチョコレート ( Greedy, Maximum Bipartite Matching )

No.421 しろくろチョコレート - yukicoder題意: 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了,用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100,每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10,隨便吃一塊會得到幸福值 1,問最大幸…

ARC 072 F - Dam ( Greedy, Monotonous, Deque )

F: Dam - AtCoder Regular Contest 072 | AtCoder題意: 有一個水壩,容量是 L。有 N 天,第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩,晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i,問使得第 i 天恰有容量 L 的水在水壩…

ARC 072 C - Sequence ( Greedy )

C: Sequence - AtCoder Regular Contest 072 | AtCoder題意: 給 N 個數字的數列 A。一次操作選一個數字 +1 或 -1。問最少要幾次操作,才能使得前綴和的正負交替。制約: 2≦n≦1e5 |ai|≦1e9 ai は整数解法: 枚舉開頭是正或負。由左到右確定數字,只有在必要…

CFR 795 C. Maximum Number ( Greedy )

Problem - C - Codeforces題意: 你有無限多個七段顯示器,問不超過 n 個段可以發光的前提下,可構成的最大數字是多少。制約: The first line contains the integer n (2 ≤ n ≤ 100 000) — the maximum number of sections which can be highlighted on the…

CFR 795 A. Amusement Park ( Greedy, Ternary Search )

Problem - A - Codeforces題意: 有 N 個人,用一個 01 序列描述,0 代表小孩,1 代表大人。給定 C1, C2,你要將這些人分群,使得每個群至少有一個大人,而且最小化 sum( C1 + C2 * ( X[ i ] - 1 )^2 ),其中 X[ i ] 代表第 i 個群的人數。制約: The first …

GCJ 2017 Qual A. Oversized Pancake Flipper ( Greedy )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 給一個由 '+', '-' 組成的序列。問能不能透過任意次操作將該序列全部元素變成 '+'。操作只有一種,將連續 K 個元素內容反轉。制約: 1 ≤ T ≤ 100. Every character in S is either + or -. 2 …

ARC 071 C - 怪文書 ( Greedy )

C: 怪文書 / Dubious Document - AtCoder Regular Contest 071 | AtCoder題意: 給 N 個字串,求一個最長的字串,若相同則字典序最小,使得每一個字串都能透過任意刪除、交換位置得到。制約: 1≤n≤50 i=1,…,n に対して、 1≤|Si|≤50 i=1,…,n に対して、 Si は…

CSAcademy 23 D. Disk Mechanism ( Greedy )

Round #23 (Div. 2 only)題意: 給若干個中心,現在你要以這些中心擺放圓。有左數起第 i 個圓的半徑可以是 [ L[ i ], R[ i ] ] 中任意整數。兩個相鄰的圓必須相切。問有幾種方案。限制: 2≤N≤1e5 The point coordinates are given in increasing order and t…

CSAcademy 23 B. Fast Travel ( Greedy )

Round #23 (Div. 2 only)題意: 有 N 個城市,以座標描述。兩個城市之間的移動的所需時間是曼哈頓距離。有些城市是特別的 ( S = 1 ),特別的城市之間可以花費 T 單位時間進行瞬間移動。Q 筆詢問,每次問兩個城市之間最少需要花費的移動時間。限制: 2≤N≤1000…

CFR 301 A. Yaroslav and Sequence ( Greedy )

Problem - 301A - Codeforces題意: 給一個長度為 2 * N - 1 的數列 A。你可以進行任意次以下的操作: 選擇任意 N 個相異的元素,讓他們的符號反轉 ( 乘上 -1 )。 問操作後,可以得到的最大數列和為何。資料規模: The first line contains an integer n (2 …

CFR 44 E. Anfisa the Monkey ( Greedy )

Problem - 44E - Codeforces題意: 給 K, A, B,以及一個字串 S。要求輸出方案,使得將 S 分為 K 個子字串,滿足所有子字串長度在 [ A, B ] 之間。資料規模: The first line contains three integers k, a and b (1 ≤ k ≤ 200, 1 ≤ a ≤ b ≤ 200). The secon…

CFR 781 A. Andryusha and Colored Balloons ( Greedy, DFS )

Problem - A - Codeforces題意: 給一棵 N 個節點的樹,要求給每個節點著色,滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模: N ≤ 2e5解法: 隨便找一個節點當作根,轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…

IOI 2007 Sails ( Greedy )

1343 - [IOI 2007, Day 1] Sails | TIOJ INFOR Online Judge題意: 有 N 個桿子,第 i 個桿子的高度為 H[ i ],待放的旗子數量為 K[ i ]。 對於一個高度,若有 x 個旗子,那麼該高度的貢獻為 x * ( x - 1 ) / 2。 求最小總貢獻。資料規模: 輸入的第一行有一…

POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze題意: 有 N 個工作,假設當前時間已經過 T 單位,那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作,問最短時間完成的工作序列。資料規模: In the first line of the standard input there is…

IOI 2016 Molecules ( Greedy )

http://ioinformatics.org/locations/ioi16/contest/day1/molecules/molecules-TWN.pdf 1956 - [IOI 2016] Molecules | TIOJ INFOR Online Judge題意: 給 L, U, W, N, result,要你找一個在集合 S,使得該集合為下標的 W 的總和在 L 和 U 之間 ( 含 ),寫在…

CFR 215 D. Hot Days ( Greedy )

Problem - 215D - Codeforces題意: 有 N 個地點要依序拜訪。每個地點都要叫至少一台車,一台車的花費為 cost。車的溫度為 t,學生能忍受的溫度為 T。一個車內如果有 x 個學生,那麼該車的溫度為 t + x。對於一個車,如果車的溫度大於 T,在車裡面的所有學生…

CFR 389 E. Fox and Card Game ( Greedy, Game )

Problem - E - Codeforces題意: 有 N 個堆,第 i 個堆有 S[ i ] 個元素,每個元素都有權值 C[ i ][ j ] 。玩家 A 每次選一個堆,取最上面的元素,玩家 B 每次選一個堆,取最下面的元素。玩家 A 開始,並輪流操作。求雙方最大化自己的權值總和為前提,玩家 A…

CFR 442 B. Andrey and Problem ( Math, Probability, Greedy )

Problem - B - Codeforces題意: 你有一件事情要完成,但你太懶所以想請你朋友做。你可以同時請很多朋友做,但是如果兩個以上個朋友同時做出來,他們會覺得你把他們當工具人,不特別看待他們。求最佳策略下,可以不讓朋友傷心而完成這項作業的機率是多少。資…

CFR 402 D. Upgrading Array ( Greedy )

Problem - D - Codeforces題意: 給一個數列,以及一些厄運質數。一個數的價值等於,質因數分解後,非厄運質數數量 - 厄運質數數量。可以做任意次操作,每次操作選擇數列中一個下標,將該下標以前的所有數字都除以他們的共同最大因數。求最大總價值。資料規…

CFR 67 A. Partial Teacher ( DP, Greedy )

Problem - A - Codeforces WA 好多次... 題意: 有 N 個數字,給你兩兩之間的大小關係,左大,左小,或相等。求總和最小的合法數列長相。資料規模: The first line of input contains the number of students n (2 ≤ n ≤ 1000). The second line gives (n -…

CFR 3 D. Least Cost Bracket Sequence ( Greedy )

Problem - D - Codeforces題意: 給一個序列,有 '(', ')', '?' 三種符號,每個 '?' 有相應的代價可以轉換成左括弧或右括弧,求最小總代價,使得變成合法的括弧序列,或者判斷不存在合法的方案。資料規模: 序列長度 1 ≤ N ≤ 5e4 轉換代價 1 ≤ A[ i ], B[ i …

CFR 738 D. Sea Battle ( Greedy )

Problem - D - Codeforces題意: 給船的數量,船的長度,以及已嘗試射過多少位置,以及射的位置分布。地圖是一維的,而船的分佈未知。求至少還要再射多少位置,以及是哪些,才能保證至少射到一個船。資料規模: 1 ≤ n ≤ 2e5, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1解…

CFR 294 B. Shaass and Bookshelf ( Greedy )

Problem - 294B - Codeforces 題意: 給一堆相同高度的書,用厚度和寬度描述。放書的方法是相放一層豎的,再將剩下的橫放在那層上。橫放的那層寬度總和不得超過下面豎著放的那層厚度總和。求最小厚度總和。 解法: 由於書的厚度只有兩種,因此可以分開枚舉兩…

CFR 416 C. Booking System ( Greedy )

Problem - 416C - Codeforces 題意: 給一堆客人的要求,用人數和獲益描述,接著給一些桌子其容量。每個桌子只能招待一組客人的要求,而某個桌子可以招待一組客人若且唯若其容量不小於人數,此時若選擇配對則獲得該獲益。求最大總獲益,並輸出對應配對。 解…

CFR 527 D. Clique Problem ( Greedy )

Problem - D - Codeforces 題意: 給若干個點和其權重,求最多一組點,使得任意兩點距離大於等於權重和。 解法: 將點看成圓心,權重看成半徑後,問題等價選最多一組點使得圓之間無重疊。由於上下的概念無意義,可以轉化為一維的區間不覆蓋問題。給若干個區…

CFR 289 B. Polo the Penguin and Matrix ( Greedy )

Problem - 289B - Codeforces 題意: 給 N * M 的整數值矩形,和一個數字 D。求是否可以只透過對值加或減 D 使得矩形最後所有值相同,以及最少步驟數。 解法: 若有解,使所有數成為中位數顯然是最優方案。因此檢查是否每個值都能成為原矩陣值的中位數。 int…

HR Equal ( Greedy )

https://www.hackerrank.com/challenges/equal An important observation to make, is to realise that "adding value x to all elements except element y" is equivalent to "decreasing value x from element y". Once this is made clear, it will be ob…

HR Far Vertices ( Greedy )

https://www.hackerrank.com/challenges/far-vertices Let's find out all pairs of ( u, v ) where dis( u, v ) > K, put them into a set, and change the question to: "How many nodes should be removed, so that u and v do not coexist in any pairs …

GCJ 2016 R1A pA. The Last Word ( Greedy )

Dashboard - Round 1A 2016 - Google Code Jam It is very intuitive to come up with the greedy strategy where, alphabetically less characters go to the back, otherwise to the front. #include <bits/stdc++.h> using namespace std; int main(){ int T; scanf("%d"</bits/stdc++.h>…

SRM 687 Med. Quacking ( Greedy + Imosu )

TopCoder Arena Greedily gather each quack from the left as earlier as possible. Suppose a quack found in that way is in some interval [ s, t ], than we are to find the count of the position with maximum quacks lying on. We could simply add…

GCJ 2016 QR B. Revenge of the Pancakes ( Greedy )

Dashboard - Qualification Round 2016 - Google Code Jam This can be solved by DP, too. However the greedy approach is easy to come up with and shorter in code. With some observation, it is easy to find that the flips will be made from left …

CFR 245 1A. Xor-tree ( Greedy + DFS )

Problem - 429A - Codeforces It is obvious that if all nodes above are cleared and the current node is not the target, it has to be flipped. It is never better to flip its ancestors, for it will cost extra for nothing. We don't have to go d…

IOI 15 Sorting ( Binary Search + Greedy )

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

UVA 11167 Monkeys in the Emei Mountain ( 區間分配置點問題 )

很經典的算法。只是不知道時間複雜度對不對。嘛AC了就算了。 追記:後來發現這是題 Dinic題,竟然被我亂水過了,估算一下我的時間複雜度,O( N * lg N + MAXB * M * lg N ),咦,感覺挺好的啊。。 blog.csdn.net 大神 241行的 code.. Orz 拜了 這故事告訴我…

TOJ 277 騎腳踏車 ( Greedy )

http://sprout.tw/oj/pro/277/ 很明顯如果希望疲累度最大,就不能讓休息站幫我們太多。讓休息站最沒有幫助的方法無疑是連續的,還有一個起點一個終點的情況。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; const int MAXA = 1e3 + 3; typedef </bits/stdc++.h>…

CFR 500 B. New Year Permutation ( Greedy + Union Find )

Problem - 500B - Codeforces 如果某兩個數可以交換,那麼可以和那兩個數的任意一個交換的數同樣能和另一個交換,所以我們可以維護一個集合代表當前的位子可以用的數字有哪些。欲處理完就能貪心的由左到右依次選取集合中最小的。 #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

POJ 1456 Supermarket ( Greedy + Union Find )

1456 -- Supermarket 很顯然要從最貴的開始放,而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ],代表第 i天( 含 )之前最晚的還沒有賣東西的時間,又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = …

IOI 15 Boxes with Souvenirs ( Greedy )

PEG Judge - IOI '15 - Boxes with Souvenirs 実はそんなに難しくない Greedy。まず、どういう操作があるか考えてみよう。 1、時計回りに動いて逆時計回りに戻る 2、1の真逆 3、一周する 1をする場合は半周を過ぎないのは簡単に見える(そうする必要が…

CFR 526 B. Om Nom and Dark Park ( Greedy )

Problem - B - Codeforces Since it is always better to put lamps on an edge nearer to the root, rather than putting the same quantity on both brother edges, we will maintain the subtrees along backtracking DFS, such that when considering a …

CFR 635 E. Package Delivery ( Greedy + Stack Monotonicity )

Problem - E - Codeforces Basically when the car is in gas station i, there is one and only one optimal decision. If it is possible to move to the first station with cheaper gas price after this one, buy the minimum amount of gas here in or…

UVA 10026 Shoemaker's Problem ( Greedy )

UVa Online Judge 先想像一個最佳排列已經出來了。那麼任意相鄰的工作交換後不會影響其他工作,所以我們考慮這個已經是最優的排列中的相鄰工作是怎麼排出來的。假設現在這兩個工作分別是 a和 b,那麼 先排 a再排 b的總花費是 ( a.duration * a.fine + ( a.du…

UVA 11134 Fabled Rooks ( 二維置點問題 )

UVa Online Judge 和這題是一樣的算法: h0rnet.hatenablog.com 即使變二維,可以將水平座標和鉛直座標做拆解成為兩個相互獨立的置點問題。比較雷的是我忘記判斷優先佇列是空的時候,代表這個位置不能放任何東西,需要跳過,就吃了RE。 #include <bits/stdc++.h> using name</bits/stdc++.h>…

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

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

UVA 1346 Songs ( Greedy, std::nth_element )

UVa Online Judge 很明顯長度越長且頻率越小放在前面一定比較好,但我只會直覺上想到應該會是以其中一個數乘上另一個數的倒數為基準做排序。證明是查了別人的文章 http://blog.csdn.net/synapse7/article/details/17160607 看到這位大神的 code我還另外學到…