UVa Online Judge It is obvious that once we find an element that is "non-boring", we can split segment to two sub segments to apply divide and conquer for each. The problem is that if we try to find that "non-boring" element from either si…

UVa Online Judge Store the information of a queen set by the row, column and both diagonals it occupies in order to accelerate the search. A little prune used is to skip decisions that will not occupy any line. #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

UVa Online Judge 前 m個老師就無選擇給他取下來，其他 n個分開來搜用與不用的情況。哪些課有兩個老師上、一個老師上、或還沒有老師可以上用狀態記錄下來，輪一輪，調一下就應該要水過去了。 碎念：這題真是我永遠的苦痛，TOI考過一模一樣的題目，那時候真菜…

UVa Online Judge 題目大意：N ≤ 1e4 個節點形成一個樹狀結構，求安裝最少的伺服器數量，使得每個不是伺服器的節點恰好和一臺是伺服器的節點相鄰。 由於是樹的結構，我們可以大略閃過一些可能可以當作狀態的字彙，本身是否為伺服器、父節點是否為伺服器。進…

UVa Online Judge 題目大意：給定一個括弧序列，可任意增加、插入括弧，求最少增加的情況下的合法括弧序列。 可以考慮遞迴，一個序列大致有三種情況可以處理，一種是它的外部是合法的，可以試著直接將外部刪去，第二種是在某個切割點分開的情況做分治，這就…

UVa Online Judge 由於花費的定義是每個顏色的最後出現位置減去最先出現位置的總和，樸素的動態規劃做法是不好做的。比較好的方法是根據當前的字母是否為最後一個，或是剛開始，維護由這個狀態轉移到別的狀態所需要的花費。令 dp( i, j ) 為已經使用 p的前 i…

UVa Online Judge 令 dp( i, j ) 為時間點 i時在車站 j時的最短等待時間，邊界 dp( T, n ) = 0。另外預處理 hasTrain[ k ][ i ][ j ] 車站 j在時間點 i是否有往左 / 右的火車。 #include <bits/stdc++.h> using namespace std; const int MAXT = 200 + 2; const int MAXN = </bits/stdc++.h>…

UVa Online Judge 解題關鍵在於只要個位數確定，做完乘法後的個位數也會隨之確定，並且這個數會是做完乘法後的個位數的排列。因此只要枚舉個位數後判斷是否合法即可。比較挫的是，我很少用 std::next_permutation()，沒有意識它只會重新排列成比呼叫時字典序…

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

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 挺有趣的一道題。一開始很直覺的直接比較字典序，WA了一波才想到問題在於長度相異的時候比較時，像是 cmp( 2, 27 ) 和 cmp( 2, 21 ) 是不同的，前者要回傳 false使成為 272，而後者要回傳 true使成為 221才會對。所以這時候應該要直接比較 …

UVa Online Judge 題目大意是給 n ≤ 10000個五元組，求取 k個的情況下每個位置的最大值相加的值最大。 感覺就只能暴搜，但五元組數量太多，裸裸的 2^10000剪枝也沒有希望。想一下，浪費時間是因為其實真正會用到的五元組不多，更仔細想想，會用到的定義是將…

Haven't yet tested well, might have some bugs. #include <bits/stdc++.h> using namespace std; const double EPS = 1e-10; const double PI = acos( -1.0 ); int dcmp(double x){ if( fabs( x ) < EPS ) return 0; return x < 0 ? -1 : 1; } struct Vector{ double x, y</bits/stdc++.h>…

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>…

UVa Online Judge 給一個 n * m的巧克力，問最少要切幾刀才能全部變成 1 * 1的巧克力，一次只能切在一塊的整數線上。 直覺上把巧克力變成 n條 m個巧克力的條或 m條 n個巧克力的條不會比縱橫亂切差，簡化一下代數又發現這兩種都必須要切 n * m - 1次。。如果…

UVa Online Judge 不太懂告訴我們一個點是否在凸包上到底有何意義。。嘛反正也是無恥水過去。注意座標會過大要用ll。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; struct Vector{ int x, y; Vector(){} Vector(int _x,</bits/stdc++.h>…

UVa Online Judge 沒有變化的單純求凸包。比較特別的要求是起點要印兩次，且必須是 y值最小的，若有多個相同則 x值最小的。這部分很容易解決，將點排序的時候照他要求排就行了。 碎念：以為每次後面都要吐出 -1，沒想到是測資與測資之間啊。。。 #include <bits/stdc++.h> u</bits/stdc++.h>…

UVa Online Judge 題目要求圓內選擇 m個點時最大的 m多邊形面積。由於點是給逆時針排序的，所以省掉了做一次凸包的麻煩。以 dp[ i ][ j ][ k ]為 [ i, j ] 中選了 k個點( 包含 i 和 j )時的最大面積動態規劃下去就行了。 #include <bits/stdc++.h> using namespace std; con</bits/stdc++.h>…

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

UVa Online Judge 算出最小生成樹上每對最小瓶頸路徑就能 O( n * n ) 解決。 碎念：find() 函數忘了寫 return這個字= = #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; // 1 idx const int MAXC = 300 + 2; const int MAXM = MAXN * MAXN / 2; c</bits/stdc++.h>…

UVa Online Judge 取到排序後第 p - s + 1個最小的就可以了。 #include <bits/stdc++.h> using namespace std; const int MAXS = 100 + 2; const int MAXP = 500 + 2; const int MAXM = MAXP * MAXP / 2; int n, m; struct Edge{ int u, v; double w; Edge(){} Edge(int _u,</bits/stdc++.h>…

UVa Online Judge 和 UVA 1395 Slim Span是同一個問題，但測資加強 UVA 1395 Slim Span ( 水題最小瓶頸生成樹 ) - 0w1 因為允許18秒，所以試了看看哪裏可以做小優化，發現我每次加入一個邊都有重新排序，這是無意義的，做第一次就行了。但搬出來還是TLE。又…

UVa Online Judge 先將邊以邊權排序後，枚舉以哪個邊為最小值，用最小瓶頸生成樹的算法算出最小的最大值。複雜度 O( n * m lg m )。據說這題有進階版 UVa Online Judge UVA 12275 Sensor network - 0w1 #include <bits/stdc++.h> using namespace std; const int MAXN = 100</bits/stdc++.h>…

UVa Online Judge 題目要求用最少的水來往達到 d或接近 d，又注意到水不會減少亦不會增加，故狀態只有二維 ( 知道其中兩個分別裝了多少就能知道剩下的那個 )，這是一種隱式圖走訪的問題，可以用 PFS解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = </bits/stdc++.h>…

UVa Online Judge 是POJ 3352的進階版Biconnected Components - 0w1，差在不保證連通性。 題目給一個不保證連通的圖，要求將原本的邊隨意定向，求最少還要加入幾個有向邊才能使新圖強連通。先想能不能縮環，因為邊雙連通分量定向後一定可以是強連通分量，所…

UVa Online Judge 題目要求多筆詢問回答 a是否為 b的祖先。可以用時間戳記做樹壓平，只要 b所代表的區間[ in[ b ], out[ b ] ) 包含於 a的區間就說是。這題比較特別的是葉節點可以到很大，如果真的一一拜訪下去會 RE，所以必須不拜訪直接處理。除錯了好久才…