2015年4月28日 星期二

UVa12907-12915

緩慢更新中...感謝 morris821028 幫忙寫 code 驗證我理解是否有誤 m(_ _)m

12907 Toby the adventurer 

題意:有一塊大陸,有 $N$ 個城市,以及 $M$ 條單向道路,每條道路有對應的通行費,有一個人要在這塊大路上冒險,最初他在邊號 $R$ 的城市,他可以付一條路所對應的費用,延著該條路的方向,到一個新的城市,此外,他可以不用付任何費用就回到任何一個他已去過的城市,請問他至少要花多少錢才能逛完所有城市?並輸出旅行的方案。若無解則輸出 impossible。

數據範圍: $測資組數 \leq 100, 3 < N \leq 10000,3 < M \leq N,0 \leq R < N$。

tag:[ 圖論 ]

  乍看之下這題就只是個 DMST (Directed Minimum Spanning Tree) 問題 (一般情況可使用 Edmond's algorithm 解之),且是一個要輸出解的 DMST。但大家應該有發現他有一個超怪的條件: $M \leq N$ !事一定有蹊蹺!?

  首先有件很理所當然的事: $N$ 個點的 DMST 恰有 $N-1$ 條邊。所以我們可以藉此聯想到一個 $O(N^2)$ 的演算法:考慮 $N=M$ 的 case,我們可以枚舉要刪除哪條邊,並 $O(N)$ check 剩下的邊是否為一個合法的 DMST。若 $M<N$ ,答案應該蠻顯然的。

  接下來可以想想看,我們真的要枚舉那麼多種可能性嗎?首先注意到,合法的 DMST 中,每個點的 in degree 幾乎都是 $1$,但 $n$ 條邊 in degree 的總合只有 $n$ 的 ,實際上,除起點外,若有哪個非起點的點在原圖中的 in degree 是 $0$,就沒有解;若 in degree 是 $1$ 則非得選不可。所以可選可不選的邊至多只有兩條!找出那兩條,然後枚舉哪兩種可能看看哪個比較好,就解決這題了。

  若真的遇到 DMST 找解的問題,可是非常痛苦的 ...,我比賽中在解 DMST 問題時,總是直接從 codebook 複製貼上。但是現今大部分的人所使用的 codebook 都沒有包含構造出一組 DMST 解這件事,所以就必須好好重新想想 Edmond's algorithm。實際上,2013-2014 NEERC 就有一題要構造出解的 DMST 問題: UVa 1681 Dictionary,大家可以試著去挑戰他 XD 挑戰完把他加進 codebook XD

  若有在 UVa 找最經典的 DMST 問題:則請看 UVa 11183 - Teen Girl Squad

12908 The book thief

題意:有一個小偷把一本書的所有頁數數字加起來,但漏加了一個數字,告訴你小偷算出的總和的值,請求出該本書有幾頁以及漏加的是哪個數字。

tag:[ 數學 ]

嗯...可以 O(1) 快速得知至少需要幾頁 (1加至總頁數必須大於 input 值),再 check 是否能減掉某個數字就得到 input。實際上你總是能得到一個合法的漏掉的頁數唷!

12909 Numeric Center

題意:給定 $n$,請問 ${1}$, ${1,2}$,${1,2,3}$, ... , ${1,2, \dots , n}$ 的集合中,有多少個集合,能在集合中恰找到一個數 $x$ ,使得集合中小於 $x$ 的數的總和和大於 $x$ 的數的總和相等。例如說,集合 ${1,2,3,4,5,6,7,8}$ 可選 $6$ 為 $x$,使得 $1+2+ \dots + 5 = 7+8$。

tag:[ 數學 ]
關鍵字: Pell's Eaquation

  據說這題只要把最小的幾個數搜出來再拿去 google 就能 google 到數學公式了。

  若要自己解,可以先列出關係式,據說化簡後會得到 $8*x^2 + 1$ 必須是完全平方數,也就是說 $x$ 式所有 $y^2-8*x^2 = 1$的整數解。這東西叫做 佩爾方程,可以 google 到很多關於這東西的資訊,他可以使你用手算一算後很快的得到所有 $x$ 的解的遞推公式。

12910 Snakes and Ladders

題意:蛇梯棋遊戲,使用公平的六面骰,問結束遊戲時的步數期望值。
tag:[ 數學 ]
關鍵字:高斯消去

  就...一臉高斯消去樣,把期望值的關係式列出來後解聯立方程式。

12911 Subset sum

題意:給 $N$ 個數的集合,請問有多少非空子集的集合內數字總合等於給定的值 $T$。
數據範圍:$1\leq N \leq 40$。
tag:[ 小品 ]
關鍵字:分兩半

  通常看到 $N = 40$ 附近的問題... 就會值接兩響到把數據切成兩半的做法。這題的類題不勝枚舉,把集合拆成兩半,每半部的集合都枚舉所有 $2^{N/2}$ 種subset,枚舉其中一半部時 hash 每個總合的值出現多少次,而枚舉另外一半部時,就可以根據hash值得知他有多少種和前一半部的組合加總可以湊成 $T$。

12912 Josephus lottery

題意:有 $N$ 個人圍一圈,由順時針分別從 $1$ 號編號到 $N$ 號,由 $1$ 號開始數,第一輪順時針數 $K$ 個人,並把被數到 $K$ 的人移除,下一輪從被移除的下一個人開始數,但這次是逆時針數 $K$ 個人,一樣把第 $K$ 個人移除,如此反覆順時針逆時針交互的數,直到只剩下一個人,請問剩下的人編號是多少?
數據範圍:$1 \leq \leq K \leq N \leq 10^6$。

  就約瑟夫問題變形。雖然 $N$ 很大,但 $O(N log N)$ 做法就可以 AC 了。與一般的約瑟夫問題一樣,可以倒著用 $O(n)$的時間複雜度 dp 回來。

12913 Grounded

題意:給定 $N$、$K$,$S$ 為包含 $0 \sim 2^N - 1$ 間所有整數的集合,請問 $S$ 有多少子集合滿足集合內所有數的 xor 結果,轉乘二進位後恰有 $K$ 個 bit 是 1。

數據範圍:$1 \leq K \leq N \leq 10^6$
tag:[ 數學 ]
關鍵字:集合

和 Hackerrank 上的 Ad Infinitum 10 - Math Programming Contest Number of zero-xor subsets 概念一模一樣,差別只在於 Hackerrank 那題只問 $K = 0$ 的 case,所以去參考Hackerrank 上的 Editorial 理解後應該也能做出這題。

我來用我自己的方法解釋 $K = 0$ 的 case。 $K = 0$ 意即該集合所有數的 xor 結果為 $0$。先隨便亂抓一個集合,例如說 $N = 3$ 時,我們任取一個集合:{2,3,5,6},這四個數 xor 結果為 $2$,並不是 $0$,現在我們想要把這個集合稍做修改,讓他變成 $0$,要怎麼做呢?應該會很直覺的把集合內的 $2$ 去掉吧?那若現在取的集合是 {4,6} 呢? 此集合 xor 後的結果也是 $2$,那我們就可以把 $2$ 加進這個集合裡,能使集合的 xor 值也變成 $0$。

於是我們可以發現,任取一個 $S$ 的子集,我們都有辦法恰對集合新增或移除一個數,讓集合內所有數 xor 結果為 $0$ (注意我們新增或移除的數可能是 $0$),且方法恰只有一種。所以說,總共有 $2^{2^N}$ 種子集合,我們就能變出 $2^{2^N}$ 個 xor 值為 0 的集合嗎!?當然不可能啦 XD 實際上,會有好多個集合改變後會對應到同一個集合,那麼一個 xor 值為 $0$ 的集合,會被幾個集合對應到呢?例如 $N = 2$ 時,{1,2,3} 集合內所有數 xor 值為 $0$,而會對應到他的集合有 {0,1,2,3}、{2,3}、{1,3}、{1,2} 共四種。到這裡應該能看出點頭緒了吧?對於每一種集合內所有數 xor 值為 $0$ 的集合,都恰有 $2^N$ 個集合能經過加減一個元素的操作對應到它。所以全部 $S$ 的子集合,每 $2^N$ 個集合會對應到一個 xor 值為 $0$ 的集合,故全部共有 $(2^{2^N})/(2^N)$ 個 xor 值為 $0$ 的集合!這也就是 hackerrank 那提的答案。

至於 $K$ 不為 $0$ 要怎麼辦呢?剛才我們解的是 xor 值為 $0$ 的集合數,那 xor 值為 $1$ 呢? xor 值為 $2$ 呢?能如法炮製嗎?

12914 Sum of all permutation


12915 TripleCorn


正常的 dp 優化題?