0w1

Greedy

Yuki 615 集合に分けよう

Problem Description: There is a set of N numbers. You would like to split the set into K non-empty subsets, so that the sum of contribution of each subset is minimal. Contribution of a subset can be computed as the absolute difference betw…

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