緩慢更新中...感謝 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$。
就約瑟夫問題變形。雖然 $N$ 很大，但 $O(N log N)$ 做法就可以 AC 了。與一般的約瑟夫問題一樣，可以倒著用 $O(n)$的時間複雜度 dp 回來。
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$ 呢？能如法炮製嗎？
數據範圍：$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
根本 Hackerrank 上的 Ad Infinitum 8 - Math Programming Contest Value of all Permutations。
12915 TripleCorn
正常的 dp 優化題？
沒有留言:
張貼留言