Problem A - Apple Pen
小測資算是基本的 string 習題，讀入後把所有物件的組合有兩種順序湊在一起看看是否有其中一種等於 $T$，是的話就先把答案記錄下來，最後再輸出。細節請直接參考程式碼：
大測資似乎很容易讓大家走火入魔去使用 hash 或 trie 等比較厲害的東西，等仔細思考後可發現，我們並不需要任兩個物件都湊湊看，因為 $S_i$要碼是 $T$ 的前綴字串會後綴字串才有可能被和其他字串組出 $T$，所以對於每個 $S_i$ 只需要比較兩次而已，並開兩個表格 $pre$ 和 $suf$，分別記錄 $T$ 的某個長度的前綴或後綴是等於第幾項東西的名字。最後再枚舉 $T$ 的所有中切兩半的方法，試試看是否切出的兩段都是某個東西的名稱。
我的大測資程式碼如下：
Problem B - Two Swords Style
小測資的重點是給初學者練習位元運算或是 bitset 吧 XD 每個詢問都個別計算。對於單一詢問，只要枚舉兩把劍的組合，計算他們屬性的聯集是否包含任務所需的屬性集合，懂得運用位元運算或 bitset 就會變得很好寫 code，請直接參考程式碼，我的程式碼是使用 bitset：
中測資則可利用與集合有關的 DP 問題解它。一樣是每個詢問都個別計算，但這次對於單一詢問，我們只枚舉一把劍，希望能快速得知有多少劍與枚舉到的劍互補。
從這裡我們開始使用集合的相關術語和符號。首先把屬性編號為 $1 \sim m$，我們所討論的宇集就是 {$1, 2, \ldots, m$}，$S_i$ 為第 $i$ 把劍所擁有的屬性集合，令 $M$ 為任務所需屬性的集合。所以我們想要快速知道的事情是：對於每個 $S_i$，有多少個 $S_j \subset M - S_j$ ( 減號表示 $M$ 和 $S_j$ 的差集，運算結果將包含所有在 $M$ 卻不在 $S_j$ 的元素 ) 。 實際上，這件事可以用 DP 以 $O(m \times 2^m)$ 的時間複雜度預處理 。我們用 $dp$[$x$][$T$] $=$ 滿足 $T$ 為 $S_i$ 子集且 $S_i$ 為 {$1,2, \ldots, x$} $\cup$ $T$ 的子集 的 $S_i$ 的個數，且dp[0][$T$] 就是 滿足 $S_i = T$ 的 $S_i$ 的個數。這樣的 DP 狀態會有以下關係式：
如果 $x$ 包含於 $T$， $dp$[$x$][$T$] $=$ $dp$[$x-1$][$T$] 否則 $dp$[$x$][$T$] = $dp$[$x-1$][$T$] $+$ $dp$[$x-1$][$T+{x}$]。
這個 dp 表格求出來後 dp[$m$][$T$] 就是 包含 $T$ 的 $S_i$ 的個數了。
再實作時可以發現，我們其實只要用 $O(2^m)$ 的記憶體就可以得到最終我們要的東西，詳情請以下程式碼：
現在來到了大測資，對 FWT ( Fast Walsh–Hadamard transform, 可參考此連結 ) 熟的人大概一看就知道大測資可以用 FWT 解掉了吧？( 賽中 AC 的三個人有兩個人是使用 FWT )，但若問題繼續推廣成問三刀流或四刀流呢？這時還能用 FWT 解嗎？就我的理解是不能啦，所以我寫在這裡的解法會是個甚至可以推廣到 $K$ 刀流 (可惜對於一筆測資 $K$ 必須是固定的)，且是繼續使用上述中測資的解法的類似概念。
若我們能快速知道對於所有集合 $T$ ，有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j = T$，那我們就可以利用中測資所說的方法求出答案了！但這似乎有沒那麼簡單？
再退而求其次，我們改求有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$，但這也沒那麼簡單的樣子，那我們就再退一步吧。
這次只求有多少 $S_i$ 滿足 $S_i \subset T$。現在這個問題就可以使用類似中測資的 DP 方式解了！這次則是用 $dp$[$m$][$T$] $=$ 滿足 $S_i$ 為 $T$ 子集且 $T$ - {$1,2, \ldots, x$} 為 $S_i$ 的子集 的 $S_i$ 的個數，轉移也將是 $O(1)$ 轉移，大家可以試著自己推推看～
剛剛退了那麼多步，我們終於要開始前進了！現在已知"有多少 $S_i$ 滿足 $S_i \subset T$"，要推得"有多少組 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$"，其實只要把取組合述就好了，也就是若有 $v$ 個 $S_i \subset T$ 那麼將有 $\frac{v \times (v-1)}{2}$ 個 ($i$, $j$) 滿足 $i < j$ 且 $S_i \cup S_j \subset T$。
接著，我們要從 $T$ 的 subset 的數量求回等於 $T$ 的數量，這個也只要把上上一步的運算全部倒回做就行了，其概念就像是 $A$ 加上 $B$ 後等於 $C$，那我們就只要用 $C$ - $B$ 就可以求回 $A$ 一樣！於是現在我們每一步都會做了！
關於所有細節請細細的品味以下程式碼 >__<
Problem C - Zekken Easy
小測資沒使用特別技巧的 DP 題，考驗看看你有沒有正確理解題意，有可能的 bug 諸如運算有沒有使用 long long 或有沒有注意到 $t = 0$ 時你的座標是在 $x = 0$。首先，把所有落葉按照落下時間排序，接著用 $dp$[$i$] 表示若有擊中第 $i$ 個落葉，在這之前至多可以擊中幾個，在計算 $dp$[$i$] 時，枚舉所有小於 $i$ 的 $j$並判斷若有擊中第 $j$ 個落葉，是否可以再繼續擊中第 $j$ 個落葉，若可以，則用 $dp$[$j$]$+1$ 去更新 $dp$[$i$] 的最大值。總時間複雜度是 $O(n^2)$。
中測資開始我們用圖片示意，先考慮 $d = 1$ 的情況如下，水平座標代表落葉落下的位置，垂直座標代表烙下的時間，綠色的點代表落葉們。每擊中一片落葉後下一片能擊中的落葉必須落在當前落葉左右各張開 $45$ 度的直角框框裡，看這張圖可能還不會有什麼啟發，現在我們施點魔法，把他向右旋轉 $45$ 度！
至於大測資的差別只是紅色的虛線張的比較大而以，但我們只要把所有落葉的落下時間都乘以 $d$ 就變得和中測資一樣了。(也許對大部分的人來說中測資和大測資難度沒什麼差吧>__<)
這次直接附上大測資的程式碼：
沒有留言:
張貼留言