Greedy
Problem - 416C - Codeforces 題意： 給一堆客人的要求，用人數和獲益描述，接著給一些桌子其容量。每個桌子只能招待一組客人的要求，而某個桌子可以招待一組客人若且唯若其容量不小於人數，此時若選擇配對則獲得該獲益。求最大總獲益，並輸出對應配對。 解…
Problem - D - Codeforces 題意： 給若干個點和其權重，求最多一組點，使得任意兩點距離大於等於權重和。 解法： 將點看成圓心，權重看成半徑後，問題等價選最多一組點使得圓之間無重疊。由於上下的概念無意義，可以轉化為一維的區間不覆蓋問題。給若干個區…
Problem - 289B - Codeforces 題意： 給 N * M 的整數值矩形，和一個數字 D。求是否可以只透過對值加或減 D 使得矩形最後所有值相同，以及最少步驟數。 解法： 若有解，使所有數成為中位數顯然是最優方案。因此檢查是否每個值都能成為原矩陣值的中位數。 int…
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…
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 …
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>…
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 …
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…
PEG Judge - IOI '15 - Sorting 首先我們要想到，如果 k回合內能完成，那麼 k + 1回合內一定也能完成，這是很顯然的，因為對方換了什麼，換回來就行了。所以我們可以進行二分搜，現在問題就簡化成要在O( n ) 判斷 k回合內可不可能達成。 接著要發現，設原始…
很經典的算法。只是不知道時間複雜度對不對。嘛AC了就算了。 追記：後來發現這是題 Dinic題，竟然被我亂水過了，估算一下我的時間複雜度，O( N * lg N + MAXB * M * lg N )，咦，感覺挺好的啊。。 blog.csdn.net 大神 241行的 code.. Orz 拜了 這故事告訴我…
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>…
Problem - 500B - Codeforces 如果某兩個數可以交換，那麼可以和那兩個數的任意一個交換的數同樣能和另一個交換，所以我們可以維護一個集合代表當前的位子可以用的數字有哪些。欲處理完就能貪心的由左到右依次選取集合中最小的。 #include <bits/stdc++.h> using namespace </bits/stdc++.h>…
1456 -- Supermarket 很顯然要從最貴的開始放，而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ]，代表第 i天( 含 )之前最晚的還沒有賣東西的時間，又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = …
PEG Judge - IOI '15 - Boxes with Souvenirs 実はそんなに難しくない 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 …
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 Online Judge 先想像一個最佳排列已經出來了。那麼任意相鄰的工作交換後不會影響其他工作，所以我們考慮這個已經是最優的排列中的相鄰工作是怎麼排出來的。假設現在這兩個工作分別是 a和 b，那麼 先排 a再排 b的總花費是 ( a.duration * a.fine + ( a.du…
UVa Online Judge 和這題是一樣的算法： h0rnet.hatenablog.com 即使變二維，可以將水平座標和鉛直座標做拆解成為兩個相互獨立的置點問題。比較雷的是我忘記判斷優先佇列是空的時候，代表這個位置不能放任何東西，需要跳過，就吃了RE。 #include <bits/stdc++.h> using name</bits/stdc++.h>…
UVa Online Judge 馬上會想到二分搜最大速度，而判斷的部分就會變成經典的置點問題。每個點 ( 作業 )都有左界和右界，只能將它置於其中。一個經典的算法是先將每個點以其左界限制做排序，然後由左到右依次考慮每個位置該放置哪個點，這部分可以利用優先佇列…
UVa Online Judge 很明顯長度越長且頻率越小放在前面一定比較好，但我只會直覺上想到應該會是以其中一個數乘上另一個數的倒數為基準做排序。證明是查了別人的文章 http://blog.csdn.net/synapse7/article/details/17160607 看到這位大神的 code我還另外學到…
UVa Online Judge 用畢氏定理把輸入轉換成單純的區間覆蓋問題就可以了。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 4; int n; double l, w; double x[MAXN], r[MAXN]; typedef pair<double, double> pdd; pdd p[MAXN]; void solve(){ int m = 0; w /= 2.0; for</double,></bits/stdc++.h>…
UVa Online Judge 很單純的區間覆蓋問題。注意覆蓋的是端點而非區間。 #include <bits/stdc++.h> using namespace std; const int MAXLR = 5e4 + 4; const int MAXM = 5000 + 3; const int MAXP = 1e6 + 5; int m; typedef pair<int, int> pii; int n; pii p[MAXP]; void solve(){ sor</int,></bits/stdc++.h>…
