# 期末考題解

題解應該都不會打得太仔細，所以有問題可以直接丟給助教:0

## P01 成年禮的伴手禮

大家都有寫出來，反正就判一下是不是母音。

---

## P02 去機廳還要出題喔

我考完之後就有大概解釋了，大家都想太難了，只要維護好當前最佳方案就好，每次輸入就先比較他跟當前最佳有沒有可以穿更多時間，有的話就取代，假如一樣就再比較代幣誰更好，基本上就這樣。

---

## P03 題目讀不完

教學應該有講了，總之他的定義會強制他是一個 $1$ 到 $N$ 的等差為一的數列，然後底乘高除二就好:0

---

## P04 病毒擴散

數列長度的上界是曼哈頓距離(x+y)，如果大於上界一定會到
下界由較長的座標決定(max(x,y))，如果小於下界一定不會到。
如果長度界於上下界，由歸納法可以發現至少要 $x+y-n$ 個 $8$ 就會到 ，否則不會到。

---

## P05 不揪喔

跟我之前講貪心的時候電影那題一模一樣，不會寫回去看。

---

## P06 nowob的機廳冒險

功課題

---

## P07 身為DD的我，這麼幸福是合法的嗎?

觀察一下可以發現他是一個背包問題，但跟之前教的不一樣的是同一種物品會有很多個，解決的方式很直覺，就是直接開一個迴圈分開丟到你的陣列裡面把他變成單純的有限背包，至於怎麼寫有限背包相信大家都會:)。

---

## P08 不要再越級了

之前上課上過的LIS裸題

---

## P09 成年禮還要出題喔

第一個變化比較大的題目，首先可以觀察到他要求的是組合數而且 `N` 很小所以可以想到拿 `dfs` 做暴搜(像是之前講過的樂透那樣，用遞迴直接把所有組合炸出來)。

再來可以觀察到這題對於每個題目可以做的事情就是選或不選，所以在遞迴函式裡面會有兩種走法拿或不拿，而因為前面有提到這裡要做的是報搜所以無論是選或不選都得繼續開一個函式再走下去看看。

用 `code` 來看基本上就是你可以寫一個函式 `dfs(index, current_sum)`，代表現在正在考慮第 `index` 題，且前面選出的題目總分是 `current_sum`。

選這題：往下一層傳 `dfs(index + 1, current_sum + A[index])`。

不選這題：往下一層傳 `dfs(index + 1, current_sum)`。
(A陣列拿來存分數的)

當 `index == N`（代表所有題目都考慮完了），這時候看一下 `current_sum` 是不是等於目標 $K$，如果是，就回傳 $1$（代表找到一種方案），否則回傳 $0$。最後把所有的結果加起來就是答案。

小優化（剪枝）：
因為題目給的配分 $A_i$ 都是正整數，所以如果在遞迴過程中 `current_sum` 已經大於 $K$ 了，後面再怎麼加都不可能剛好等於 $K$，這時候就可以直接提早結束。

---

## P10 三塔事件

跟之前雙塔想法幾乎一樣，就一樣是二維dp去做。
如何實現這裡不多講跟雙塔一模一樣，重點放在怎麼找規律。

這裡先定義三種狀態:

狀態 A (| | |)：三個格子彼此獨立。代表這一層由三個 $1 \times k$ 的積木組成（頂部看來是分開的）。
形狀：$\{1, 1, 1\}$
變數：`dp[i][0]`

狀態 B ([ ] | 或 | [ ])：兩個格子連通，另一個分開。
形狀：$\{2, 1\}$ 或 $\{1, 2\}$
變數：`dp[i][1]`
(因為左右對稱（例如 [ ] | 和 | [ ]），它們的方案數是一樣的。我們可以用 dp[i][1] 記錄其中一種的數量，最後計算總數時乘以 2。)

狀態 C ([ ])：三個格子全部連通，代表這一層是一個 $3 \times k$ 的大積木。
形狀：$\{3\}$
變數：`dp[i][2]`

只是跟雙塔不太一樣的是，如果這個也是用兩層炸開會有點太不人道(雖然我出的時候也是用炸的)
然後題解我用到有點死了去問gemini他說我是傻逼有更好的做法:

我們考慮從第 $i$ 層長到第 $i+1$ 層時，每一個既有的積木部分可以選擇 「延伸」 或 「切斷」。

延伸：積木向上長高，不產生橫線。

切斷：產生橫線，上方開始新的積木。

(可以用兩層有沒有線隔著比較好判斷)

---

### (1) 從 狀態 A (| | |) 轉移
第 $i$ 層是三個獨立柱子:

#### 轉移到 A (| | |)：
每個柱子都可以獨立選擇「延伸」或「切斷」。
共有 $2^3 = 8$ 種組合（例如：延伸第1個，切斷2、3 相信各位排組都學得比我好）。只要有任一柱子延伸，或者全部切斷後重新放三個 1x1，結構都維持 A。

係數：8

#### 轉移到 B ([ ] |)：
必須切斷第 1、2 柱（為了能放新的 [ ]），第 3 柱可以切斷或延伸（但為了形成 B，通常視為重新構建）。根據規律推導，只有「全切斷並重組」或「特定延伸」的一種情況。

係數：1 （全切斷後放 [ ] |）
(對稱同理，轉移到 | [ ] 也是 1)

#### 轉移到 C ([ ])：
必須三個柱子都切斷，才能放一個新的大 [ ]。

係數：1

---

### (2) 從 狀態 B ([ ] |) 轉移

第 $i$ 層是 {2, 1}（左邊寬2，右邊寬1）。

#### 轉移到 B ([ ] |)：
左邊的大塊（寬2）可以選擇「整體延伸」或「切斷」（2種）。
右邊的小塊（寬1）可以選擇「延伸」或「切斷」（2種）。
$2 \times 2 = 4$ 種組合都會保持結構不變。

另外，如果全部切斷，可以重新放一個 B。所以這裡可以再直接歸納成 5（包含 4 種延伸組合 + 1 種從對稱形狀變過來的全切斷重組）。

係數：5

#### 轉移到 A (| | |)：
必須把左邊的大塊切斷（變成兩個小塊），右邊隨便。

係數：2

#### 轉移到 C ([ ])：
必須全切斷。

係數：1

---

### (3) 從 狀態 C ([ ]) 轉移

第 $i$ 層是一個大塊 {3}。

#### 轉移到 C ([ ])：
選擇「延伸」或「切斷後重放 C」。

係數：2

#### 轉移到 A (| | |)：
就切斷。

係數：1

#### 轉移到 B ([ ] |)：
就切斷。

係數：1

---

最後把上面那坨做點歸納就可以得到一個漂亮的 `dp` 式。(自己想，跟雙塔一樣原理就是要怎麼從前面的狀態往後推，我直接給會沒難度，但真的不懂還是可以問我，我單純怕有人不看題解就把結論抱走了嗚嗚嗚，這題解我應該換了三百種講法才找到一個可能比較好理解的)

然後要記得一個很重要的事情是上面的 B 型態我們只算了一種，但考慮到他的對稱要記得乘二才能得到正解(像是第一層的解會是 $A + 2B + C$。

---

## P11 又是BFS

題如其名，就是BFS，但可以發現他的資料大到用一般二維陣列存不下，我們可以嘗試把原本的座標當成編號來看，再講白話點可以想成我們只要在乎可以走的點就好。

這裡提供兩種做法:D

---

### 排序 + 二分搜

可以說我們在字典裡面找字:

我們把所有可以走的 $N$ 個點 $(x, y)$ 用 `vector<pair<int, int>>` 存起來，然後按照座標大小排好順序。例如：(10, 10) 在前，(10, 11) 在後，(11, 10) 更靠後。

當我們要找鄰居 (nx, ny) 時，我們用二分搜去找這本排好序的字典。
白話點就是原本 `BFS` 往四周看的時候，這裡改成對四邊做一次搜尋看我們有沒有儲存過，基本上其他做法就跟一般 `BFS` 差不多了。

### Unordered Map

跟上面的想法類似，一樣把我們有的點都丟到這個 `map` 裡面，然後往四周看的時候就可以快速找到。

我們的這個 `map` 的 `key` 是座標，`value` 是用來計他有沒有存在。
往四周看的時候得到四周的座標，丟回去看他有沒有存在。

剩下的就一樣跟一般 `BFS` 差不多了!

---

## P12 AC自動機

我沒有要題解。

---