0w1

Training guide

UVA 1608 Non-boring sequences ( DC )

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 11214 Guarding the Chessboard ( IDDFS )

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 10817 Headmaster's Headache ( 位元DP )

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

UVA 1218 Perfect Service ( 樹DP )

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

UVA 1626 Brackets sequence ( DP 括弧匹配 )

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

UVA 1625 Color Length ( DP 維護未來花費 )

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

UVA 1025 A Spy in the Metro ( DP )

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 10825 Anagram and Multiplication ( 暴搜 next_permutation )

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

UVA 1555 Garland ( 二分 )

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

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 10905 Children's Game ( Ad hoc )

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

UVA 1508 Equipment ( DFS )

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

Math Vector Template

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 1346 Songs ( Greedy, std::nth_element )

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

UVA 10382 Watering Grass ( 區間覆蓋問題 )

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 10020 Minimal coverage ( 水題區間覆蓋 )

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 10970 Big Chocolate ( 數學水題 )

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

UVA 11626 Convex Hull ( 凸包模板 )

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 681 Convex Hull Finding ( 凸包模板 )

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

UVA 1543 Telescope ( DP )

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 10816 Travel in Desert ( 最小瓶頸生成樹 + 最短路徑 / 二分 + 最短路徑 )

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

UVA 10600 ACM Contest and Blackout ( 水題次小生成樹 )

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 10369 Arctic Network ( 水題最小瓶頸生成樹 )

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 12275 Sensor network ( 增量最小瓶頸生成樹 )

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

UVA 1395 Slim Span ( 水題最小瓶頸生成樹 )

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 10603 Fill ( PFS )

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

UVA 10972 RevolC FaeLoN ( 偽SCC的橋BCC )

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

UVA 1357 Cells ( 水題時間戳記 )

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

UVA 11396 Claw Decomposition ( 水題二分圖判定 )

UVa Online Judge 正確率挺高的果然只是個裸二分圖判定。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; int n; vector<int> G[MAXN]; struct Bipartite{ int col[MAXN]; void init(){ memset( col, 0, sizeof(col) ); } bool canBip(int u){ for(in</int></bits/stdc++.h>…

UVA 11354 Bond ( 最小瓶頸路徑 Kruskal + LCA )

UVa Online Judge 題目是很裸的最小瓶頸路徑,一般的做法是 O( n * n ) 生成樹相關問題 -- 訓練指南 - 0w1 但這題 n ≤ 50000,行不通,這時候就要使用比較難寫的最小瓶頸路徑,先進行一些預處理降到 O( n lg n ) 級別。注意求最小瓶頸路徑時我們用的 maxcost…

UVA 1494 Qin Shi Huang's National Road System ( 次小生成樹 )

UVa Online Judge 很明顯是一個類似次小生成樹的問題,因為只刪除一個邊,我們考慮一一枚舉要刪除的邊互相比較。將每個點對的最小瓶頸路徑預處理 O( n * n ),檢查刪除後的權值總和就能達到 O( 1 )。總複雜度 O( m lg m + n * n )。關於最小瓶頸路徑可以看這…

生成樹相關問題 -- 訓練指南

訓練指南裡提出了幾個經典的生成樹問題,我想做一點整理。 首先提出了最小生成樹有兩個性質: 1. 切割性質:任一個圖 G的子集 G'非空且不為 G本身,則其中一個端點在 G'裡,另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。 2. 迴路性質:任…

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

UVA 10537 Toll! Revisited ( PFS )

UVa Online Judge 從終點逆推回去更新最小值。具體來說用 Priority First Search,尋找目前還沒用過的擁有最小值的節點來更新它所有可能的前驅點。打印路徑的時候只要反方向( 其實也就是順向 ) 檢查哪些點是可通行的,取其字典序最小慢慢遞進就行了。複雜度…

UVA 10917 Walk Through the Forest ( Dijkstra + DP )

UVa Online Judge 用 Dijkstra 求一次從家裡到各個點的單源最短路徑,則所求是公司到家的路徑數,可走的有向邊只存在於滿足 DIjkstra 求出的 dis[ v ] v,很明顯是個 DAG,用 DP 隨便處理就行了。 #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const i</int,></bits/stdc++.h>…

UVA 11374 Airport Express ( Dijkstra + Route printing )

UVa Online Judge 從起點和從終點各做一次單源最短路徑,並紀錄pre 陣列方便打印最短路徑。因為經濟線只能用一次,所以枚舉所有可以用的經濟線,還有一次完全不用經濟線的情況,比較哪個最好。時間複雜度 O( M lg N + K ) #include <bits/stdc++.h> using namespace std; ty</bits/stdc++.h>…

UVA 1108 Mining Your Own Business ( 點雙連通分量 )

題目的圖論模型是要求將儘量少的點標記,使得刪除任意一點後每個聯通分量有至少一個被標記的點。 我們要發現一般來說標記在割點上不會比較好,而且在同一個點雙連通分量上標記兩個以上的點是無意義的。再說如果一個點雙連通分量含兩個以上的割點,我們可以不…

UVA 1423 Guess ( 拓撲排序 + 並查集 )

UVa Online Judge 用前綴和去想,若矩陣某個 ( i, j ) 為 +, 代表 pa( j ) - pa( i - 1 ) > 0, 同時意味著 pa( i - 1 ) ( j ) 建有向邊,最後的拓撲序就能是他們合法的大小關係。比較特別的是當pa( j ) - pa( i - 1 ) == 0 的時候,因為這代表 pa( j ) == pa…

UVA 10054 The Necklace ( Euler's Path )

UVa Online Judge 可以把顏色當作節點,則珠子就是節點之間的邊,題目要求就等價於問是否能用每個邊恰好一次構成一個迴路。這就是經典的尤拉迴路問題。 若滿足"所有點構成的圖聯通且不存在奇度數的節點"則必有尤拉迴路( 而且隨便走都是 ),而尤拉路徑除此之…

UVA 11624 Fire! 水題BFS

UVa Online Judge 一個大水題,先對火做BFS預處理每個格子發生火的最早時間,然後再搞人的就行了。注意會需要用到 ( t, x, y ) 三個變數一組的某種結構,以前都搞什麼雙重pair 真是太恐怖了,tuple我現在還不太會用。。寫完這題就想,我以後就像這樣子做吧。…