UVa Online Judge 最佳策略其實就是留給對手最差的狀態，從這部份著手，很容易得到轉移方程： dp( i, j ) = sum( i, j ) - min{ 0, min{ dp( k, j ), dp( i, k ) | Ɐ i ≤ k ≤ j } } 用言語表達就是要嘛左邊取來要嘛右邊取來，甚至是全取( 留 0給對手 )會讓對…

把需要被覆蓋的節點押進該深度的節點表裡，之後依次選擇深度最深的為覆蓋的節點，用貪婪的思維找尋其 k級祖先設置伺服器。注意題目只要求葉節點覆蓋。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; int n, s, k; vector<int> G[MAXN]; vector<int> dept</int></int></bits/stdc++.h>…

UVa Online Judge 先計算完全沒有用子網路集的生成樹，留下可能用到的 n - 1 條邊，再二進位枚舉子網路的可能子集。這麼做可以大大減少考慮不可能用到的邊。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = MAXN * MAXN / 2; c</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，所以必須不拜訪直接處理。除錯了好久才…

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

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

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

UVa Online Judge 由於順序無關，我們可以將每個操作獨立出來，令 dsum( u ) 為作用在 u 上的所有 d 權和，那麼對於一個邊 u -> v，它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化，我們考慮二分搜尋，假設最小值的最大可能為…

UVa Online Judge 要求平均權值極大化，一個很常用的技巧是假設平均權值為 x，如果我們將全部的值減去 x以上的值，或全部減去 x - 1以下的值，前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環，所以我們發現我們可以二分搜尋最接近正確答案的 x，…

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

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

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

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

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

http://sprout.tw/oj/pro/144/ Short summary for the problem: given an array of N ≤ 1000 numbers a[ 1 ], a[ 2 ] .., a[ N ], each pair of numbers a[ i ], a[ i + 1 ]adjacent to each other can merge into a new single number, producing a[ i ] + …

UVa Online Judge - Offline Here are some good resources I read through in order to understand how to implement persistent RBST for this problem. morris821028.github.io blog.csdn.net #include <bits/stdc++.h> using namespace std; const int MAXMEM = 5e7; co</bits/stdc++.h>…

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

Many people are familiar with hash algorithms on string because they are easy to write. However, not many are really aware of the probability of collision. Like me, I had always thought the probability of collision is ( 1 / MOD ), and I ha…