賽中我只寫了前四題 OAQ 賽後賭氣似的把所有題目都寫了一遍，所以這算是近期頭一場我真的有親自寫過所有題目的Div. 1 Codeforces Round。
點我連到官方 Editorial
problem A --- King of Thieves
題意：給一個僅包含 '*' 和 '.' 的字串，請問是否存在恰 5 個 '*'，他們的位置是成等差數列。
數據範圍：字串長度不超過 100。
tag：[ 模擬 ]
= = = = = = = = = = = = = = =有各種做法，我的做法是枚舉等差數列的開頭位置和公差，逐一判斷。
Problem B --- Om Nom and Dark Park
題意：給一個完全二元樹，每個邊上都有一個正整數的權重，現在你要把一些邊的權重加上一個正數，使得所有 root 到 leaf 上的的路徑權重合都相同，請問所有邊要增加的值至少多要多少？
數據範圍：樹的深度至多為 11。
tag：[ 貪心 ]
= = = = = = = = = = = = = = =tag 設為 [貪心] 可能有點怪怪的，還是要把他當作數學啊？
從 root 到每個 leaf 的路徑上權重合都一樣，可推得給定任一點 x，則 x 到所有在他 subtree 下的 leaf 的路徑上的權重合也都一樣。所以我們難免想要從比較小的 subtree 先考慮。
使用數學歸納法的方式去思考：
現在我們先考慮只有三個點的完全二元樹，他只有兩個邊，根據條件這兩個邊值必須相同，那顯然最好的情況就是把比較小的那個邊加上兩個邊的權重差的絕對值。
接著我們考慮有 2^n-1 個點的完全二元樹，我們先個別把 root 的左子樹和右子樹(也就是大小為 2^{n-1}-1)用遞推的方式各別解決，然後把 左/右 子樹的 root 到 leaf 的路徑權重合加進 root 連到 左/右 子樹的邊裡，把他想像成只有三個點的完全二元樹去解決就行了。
所以這題的時間複雜度是 O(n)。
Problem C --- Om Nom and Candies
題意：給五個正整數 C，x1，v1，x2，v2 ，請求出非負整數 a，b 滿足 a*x1+b*x2 \leq C 且 a*v1 + b*v2 最大。
數據範圍：所有數不超過 10^9。
tag：[ 數學 ]
關鍵字：根號= = = = = = = = = = = = = = =
這是個很常見的題目，例如說曾出現在 2011年上海的 ICPC regional，所以應該是一堆人都見過的題目，我也曾經很仔細的想過這題，印象中實際上可以做到 O(log(數據範圍))。我隨意找了一個 Blog大家參考看看根號數據範圍的做法吧。
而且 code 可以寫的非常簡短：rng_58 的 code (rng_58的說明)
Problem D --- Om Nom and Necklace
題意：給一個字串和一個正整數 k，問有哪些長度的 prefix 是形如 A_0B_1A_1B_2A_2..A_k，其中所有 A_i都是相同字串，所有 B_i 也是相同字串，且 A_i 和 B_i都可以是空字串。
數據範圍：字串長度不超過 1,000,000。
tag：[ 字串匹配 ]
= = = = = = = = = = = = = = =賽中我看完題目後，列了一些字串就直接猜到結論了。所是用猜的，但也並不難證明。
結論：所有滿足題間的 prefix，都是某個基本的字串 s 重覆貼個 k \sim k+1 次貼出來的，貼的第 k+1 次可以只貼 s 的 prefix，例如說 s = "abc"，k = 2 ，那麼貼出來的字串可以是 abcabc、abcabca、abcabcab、abcabcabc 四種。
證明分兩個方向，首先，若把 A_iB_{i+1} 視為 s，則可推論所有滿足題目條件的 prefix 都一定由某個字串貼出來。接著令一個方向，設 s 長度為 L，且貼的第 k+1 次貼的長度為 r ，則令 A_i 為 s 長度為 r 的 prefix， B_i 為剩餘部分，就能證出所有由 s 貼出來的字串都會是滿足題目條件的 prefix。
知道了這件事後要怎麼做呢？
作法大至上分為 Hash 派、kmp 派、Z algorithm 派。
我不喜歡 Hash，因為 Hash有可能會被像我一樣的邪惡人士構造測資而被 hack，我也不喜歡 kmp，我覺得 kmp 很深奧 0.0 所以這類的題目我都使用 z algorithm。
使用 Z algorithm 後可以知道對於字串 S 的每個 index i (0 - base)，都能求出最大的 Z_i 使得 S[0...Z_i-1] = S[i...i+Z_i-1]。
如此一來我們就可以知道當 s 長度選作 i 時，可以貼出的長度有哪些了。
Problem E --- Transmitting Levels
題意：給 n 個正整數 a_1, a_2, ... , a_n，這 n 個正整數是環狀排列的。有 q 個詢問，每次詢問會給一個 值 b，問要如何把這 n 個數切成盡量少段，使得每一段數字和都不超過 b。
數據範圍： n \leq 1,000,000，q \leq 50，a_i \leq 10^9，b \leq 10^15。
tag： [ 貪心 ]
關鍵字：環狀貪心= = = = = = = = = = = = = = =
如果不是環狀，這題大概只有 Div.2 pB 的程度而已，只要從最左邊開始，每一段都取盡可能的長，不能再取時就把下個樹當作下一段的開頭。
變成環狀後要怎麼處理呢？直覺的方法就是枚舉開頭位置，然後作和非環狀一樣的事，但這樣顯然太慢了。
首先，至少我們都能夠 O(n) 預處理求出，由每個 index i 當開頭，最長的一段能多長(暢度記為 l_i )。
接著，以下提供三種思路：
1.
無論從哪個位置開始，總是有一個時候會跨過第 n 個數和第一個數之間 (我們把某一段恰結束在第 n個位置也列入考慮)，並且，我們就直接把跨過去的那一段當作最後一段。
若這樣想的話，我們就可以從後面 dp 回來了！dp 時要記錄兩個值，分別是，由某個位置當作開頭貪心去分段，要分段直到跨過去時，共分了幾段，以及最後一段結尾的位置。如果某個位置至結尾位置長度為 n 以上，那我們就更新答案。此做法應該是相當好想好寫的一種。
關於這個做法，我覺得正確性並不明顯，有人和我相同感覺嗎＠＠？
2.
把 l_i 最小的那一段挑出來(記長度為 L )，那麼無論從哪裡當作起點 greedy，一定會跨過該段，所以我們就不妨直接枚舉那一段每個位置當作起點 greedy 去劃分段落，由於每一段長度都至少為 L，所以至多只需要 O(n/L) 就可以知道由某個位至當作起點答案是多少，總共枚舉 L 次，故每個詢問時間複雜度都是 O(n) 。
這是Editorial 給的方法。
3.
若現在不是問你最小的環狀分段法，而是問你從所有位置切下去變成不是環狀後，最小的分段法個是如何。那麼以上兩個方法都不能用了。而這個方法仍可解決，但多了 union find 的時間複雜度。
首先把這 n 個數字重複共貼 3 遍，例如說 1, 2, 3 就會變成 1, 2, 3, 1, 2, 3, 1, 2, 3。
以 b = 4 作舉例，我們把所有 index 都當成是一個點，並且每個點都會向右連出去一條邊，連到以該 index 為起點，最長的段落能到達的右界的點，如下圗：
我們若有知道從某個數當開頭，至少要幾要切成幾個段落，就等於在這張圖上問，從某個點當起點，至少要經過幾條邊才會跨過至少 n 個點。
現在問們要使用 Union Find 來解決這個問題。在 Union Find 的過程中，我們還得記錄每個點到其所在 group 最遠的點的用通過的邊數。
Union Find的順序就由左到右一個一個加把邊兩個端點 Union 起來，以上圗來說，就是綠邊 => 藍邊 => 紅邊 => 綠邊 => 紅邊 => 藍邊的順序。我們只須考慮前 2n 條邊。並且當我們union完第 k 條邊時，我們就會發現第 k-n+1 個點所記錄的到該 group 最遠的那個點所需的邊數，就會是由該點所代表的數開始當第一段，greedy 出來的答案。
Problem F --- Pudding Monsters
題意：在 n*n 的表格中，每行每列都恰有一個擺有布丁，問有多少 k*k 的子表格，也是每行每列恰有一個布丁(k 可以是任意數)？
數據範圍： 1 \leq n \leq 3*10^5。
關鍵字：[ D&C ] [ 資料結構 ]
= = = = = = = = = = = = = = =唔... 關於這題的解法我沒有特別想講什麼...，我賽後寫的方法完全參考 Editorial。
我賽中一直往資料結構的方向去想，可是我的腦袋對稍微複雜的資料結構實在是沒轍，但賽後看到了另外一個關鍵字：[ Divide and Conquer ] 就如同吸血鬼被打樁一樣... 因為我連想到了這題： sgu 512 Friendly Points，以 D&C 的做法而言這兩題超像啊....，同時 friendly Points 的類題也是日本 JOI 2013/2014 三模的題目かかし (日文解答)。過去雖然我知道有這麼一題存在，可是從來沒有寫過 Orz。
Problem G --- Spiders Evil Plan
題意：給一個每邊都有給長度的 Tree，有好多個詢問，每個詢問有兩個數 x, y，你必須回答，至多 y 條 path 所覆蓋的聯通的邊集，且包含點 x，則邊集的總長度最大為多少？每個詢問回答玩才能得知下個詢問是什麼。
數據範圍：點數、詢問數不超過 10^5。
tag：[ 貪心 ]
= = = = = = = = = = = = = = =我賽後才看了這題的題目，看完題目後的感想：這題不就是 POI 的題目在稍微變化一下而以嘛 = = 如果我在賽中看了這題而且 pretest 夠強的話應該能在賽中 AC 吧 @@
POI的相關題目是 POI 13th stage 2 Subway，也可以參考 HOJ 101 捷運路線，和這題的差別就是沒有多組詢問，也沒有一定要包含某個點 x 的條件。
有沒有做過 POI 那題真的對思考這題的時間差很多，另外 POI那題也和 Codeforces gym100020裡的 pH --- Tree 大有關係。Tree 這題問的是，給一個有根數，每次可以從root問某個葉子走下去並把所有邊塗色，問塗 k 次至多能讓多少邊被塗上顏色。我會說 Tree 這題是 POI subway 的簡化版。
關於捷運路線這題可參考 這裡。
接下來我要說的是我解這題的方法的概念，實作細節我就不提了...
對於每個詢問 x, y，如果點 x 包含在最長的前 2y 條路徑裡面，那麼答案就是前 2y條的路徑和。
否則我們就強制在最長的前 2y條路徑中，在多連一條與前 2y 條路徑包括 x 的最長路徑，如下圖， y = 2，最長的四條為非黑色的路徑，點x是圖上標記的紅色的點。顧我們把紅點連到綠點的綠色路徑也加進去，於是目前就滿足了包括點 x 的條件，但是現在多了一條路徑，於是我們必須要刪除一條路徑，而刪除的路徑我們只須考慮兩種選擇，第一種是藍色路徑綠點一下的半截，第二種事原本 2y 條路徑中最短的那條(紫色路徑)。
我想這個做法是非常直覺的，但證明和實作上就必須加把努力囉。
沒有留言:
張貼留言