0w1

UVA

UVA 11506 - Angry Programmer ( Mincut, Flow )

UVa Online Judge題意: 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。制約: 2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000 0 ≤ 容量 ≤…

UVA 10601 Cubes ( Burnside Lemma )

UVa Online Judge題意: 給 12 條邊各自的顏色,顏色是 [ 1, 6 ] 間的整數,問可以組成多少種不同的立方體。旋轉後相同則視兩立方體相同。資料規模: The first line of input contains T (1 ≤ T ≤ 60), the number of test cases. Then T test cases follow…

UVA 10818 - Dora Trip ( DP, bitmask )

UVa Online Judge題意: 給一個 R * C 的圖,保證周圍都是牆( # ),也不能拜訪 ( X ),起點在 ( S ),問在拜訪最多 ( * ) 的前提下,最短迴路的最小字典序序列序列是什麼。資料規模: The input file contains no more than 20 test cases. The details of e…

UVA 3716 DNA Regions ( Math )

ACM-ICPC Live Archive題意: 給兩個字串 A 和 B,你要選擇一個 [ L, R ] 使得所有滿足 L ≤ x ≤ R 的 x 都滿足 A[ x ] ≠ B[ x ] 的比率佔長度的 p% 以下。求最長長度。資料規模: N ≤ 1.5e5解法: 考慮對 A[ x ] ≠ B[ x ] 先做前綴和,令前 x 個字符裡相異的…

UVA 12086 Potentiometers ( 平方分割 Range Sum Query )

UVa Online Judge Range Sum Query の基礎問題を平方分割で処理した。 ncastar.hatenablog.com この記事が大変参考になりました。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; int kase; int n; int a[ MAXN ]; int BS; vector< int > bucket</bits/stdc++.h>…

UVA 11487 Gathering Food ( DP 統計路徑數 )

傳出去才覺得dp判斷該不該走的部分怪怪的,不過AC了。之後可能要小心一點,從終點回去比較好。 #include <bits/stdc++.h> using namespace std; const int MAXN = 10 + 2; const int INF = 0x3f3f3f3f; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }</bits/stdc++.h>…

UVA 11167 Monkeys in the Emei Mountain ( 區間分配置點問題 )

很經典的算法。只是不知道時間複雜度對不對。嘛AC了就算了。 追記:後來發現這是題 Dinic題,竟然被我亂水過了,估算一下我的時間複雜度,O( N * lg N + MAXB * M * lg N ),咦,感覺挺好的啊。。 blog.csdn.net 大神 241行的 code.. Orz 拜了 這故事告訴我…

UVA 11297 Census ( 2D Segment Tree Single Point Modify )

UVa Online Judge 之前的寫法是錯的 每一個二維結構存的應該是一個 x軸的線段樹,每一個節點保有該二維的上下界範圍內所有 y的 min / max。但我之前只是隨便更新而已,變成只要O( lg n ),但如果同個節點被修改兩次就會發生問題,因為包含自己的二維結構不會…

UVA 11270 Tiling Dominoes ( 輪廓線DP )

UVa Online Judge 訓練指南上的輪廓線DP基本題。一開始看的時候怎樣都看不懂,沈下來想就懂了。要考慮的是放一個 tile不管橫置還是直擺,以當前那個格子為那個 tile的右下角,這種“結束考慮這個格子"的情況當作狀態。那麼如果上面的格子沒有放東西,我們就被…

UVA 12265 Selling Land ( Stack Monotonicity )

UVa Online Judge 白訓練指南的一道經典的單調棧好題。思路是先想像我們大致會做一個高度單調遞增的維護,注意到要判斷一個左上角到當前的右下角構成的矩形周長是否足夠優,只需要知道它的高和當前的列的差( 寬 )。由於只有寬是動態增加的,所以只要能不斷的…

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剪枝也沒有希望。想一下,浪費時間是因為其實真正會用到的五元組不多,更仔細想想,會用到的定義是將…

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