Moon Jam's Blog

題目網址

科學家發現了 \(n\) 種病毒，編號分別是 \(1\) 到 \(n\)，已知每一種病毒可以用一個 RNA 序列來表達，RNA 序列是一個長度為 \(m\) 的字串，其中包含 A、U、C、G、@等字元，其中 @ 為科學家沒觀察清楚的位置，可能為 A、U、C、G 其中任何一種。 科學家也研究出了這些病毒的演化關係，除了一個最原始的病毒以外，每一種病毒都是從另一個病毒演化而來的，這些病毒會構成一個樹狀結構的病毒族譜 (如圖)。

兩個 RNA 序列的的距離定義為它們的漢明距離，也就是相異的位數個數。更具體的說，對於兩個長度都是 \(m\) 的 RNA 序列 \(a, b\)，它們的漢明距離就是有幾個位置 \(i\) 滿足 \(a_i\neq b_i\) 。

你想知道目前的病毒族譜的每一個 RNA 序列中的 @ 字元的填入 A、U、C、G 中的其中一個字元後，每一個病毒與它演化來源的病毒的距離總合最小值是多少？ （後面就簡稱最小演化距離）

題目網址

輸入為 \(m \times n\) 大小的的陣列，每一格是一個介於 -100 與 100 之間的整數，表示經過這格可以累積的經驗值。 你可以從最上面一排任何一個位置開始，在最下面一排任何一個位置結束。 過程中每一步可以選擇往左、往右或往下走，但不能走回已經經過的位置。 請你算出最多可以獲得的經驗值總和 (可能是負數)。

題目網址

你是個櫃子租借商，總共擁有 M 個櫃子。 現在這 M 個櫃子分別被 N 個人借用，借用量分別為 (x0, x1, x2, …xN-1) 個櫃子， 其中 x0 + x1 + x2 + … + xN-1 ≤ M

現在你想要使用 S 個空櫃子， 在被借用的櫃子只能夠 全退 或 全不退之下，最少需要請這 N 個人退還多少櫃子？ 也就是當有一個人借用 10 個櫃子時，不能夠只請他退還 5 個櫃子。

題目網址

你有兩個數組分別為 \(n\) 和 \(m\) 的長度：
\(A_1, A_2, \dots, A_n\) 和 \(B_1, B_2, \dots, B_m\)
你可以自由決定是否要鏡射 \(A, B\) 陣列 (reverse)，也可以自由決定一個正整數 \(r\)。
且當選擇 \(A, B\) 分別交換一個長度為 \(r\) 的子陣列 (subarray)，並讓該兩個子陣列的內積最大化。

內積的定義如下：
假設從 \(A\) 陣列選擇了一段長度為 \(r\) 的子陣列 \(A_{i}, A_{i+1}, A_{i+2}, \dots, A_{i+r-1}\)，
並在 \(B\) 陣列選擇了一段長度為 \(r\) 的子陣列 \(B_{j}, B_{j+1}, B_{j+2}, \dots, B_{j+r-1}\)，
這兩個子陣列的內積就是
\[A_i \times B_j + A_{i+1} \times B_{j+1} + A_{i+2} \times B_{j+2} + \dots + A_{i+r-1} \times B_{j+r-1}\]
或可以簡單寫成 \(\sum_{k=0}^{r-1} A_{i+k} \times B_{j+k}\)

題目網址

已知有 \(n\) 個寶盒編號 \(0\) 到 \(n-1\) 以及 \(m\) 種鑰匙編號 \(0\) 到 \(m-1\)。一開始你有 \(t\) 種鑰匙分別為 \(x_1,..., x_t\)
每一個寶盒要打開都需要同時擁有 \(k\) 種鑰匙，第 \(i\) 個寶盒分別需要 \(r_{i1},r_{i2}, ... , r_{ik}\) 種類的鑰匙。每個寶盒打開後都會得到 \(k\) 種鑰匙，第個寶盒打開後分別會得到 \(s_{i1},s_{i2}, ... , s_{ik}\) 種類的鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過 \(60\)。
請輸出最多可以開啟多少個寶盒。

題目網址

謙謙最近迷上棒球，他想自己寫一個簡化的遊戲計分程式。這會讀入隊中每位球員的打擊結果，然後計算出球隊得分。 這是個簡化版的模擬，假設擊球員打擊結果只有以下情況：
(1) 安打：以 1B,2B,3B 和 HR 分別代表一壘打、二壘打、三壘打和全（四）壘打。
(2) 出局：以 FO,GO 和 SO 表示。

請寫出具備這樣功能的程式，計算球隊總得分。