owned this note
owned this note
Published
Linked with GitHub
---
title: 0x02 2020 花中二模 題解
tags: Editorial
slideOptions: # 簡報相關的設定
theme: solarized # 顏色主題
transition: 'fade' # 換頁動畫
controls: false
---
## 0x02 <br> 2020 花中二模 <br> 題解
----
### 大綱
- pG - 簽到題之二 (Registration2)
- pA - 競標 (Bidding)
- pB - 畫作鑑定 (Art)
- pC - 打工 (Work)
- pD - 河內塔 (Hanoi)
- pE - 小天使 (Angel)
- pF - 塗鴉跳躍 (Jump)
---
### <font color="black"><b> pG. 簽到題之二 (Registration2) </b></font>
----
#### 簽到題之二
- 給定 $d$ $\small(0 \le d \le 10)$、$X$ $\small(1 \le X \le 1000)$、以及奇數 $N$ $\small(1 \le N \le 99)$。
- 輸出 $N$ 個數字 $A_1, A_2, \ldots, A_N$ 使：
1. $A_i \in [1, 10^9]$，對 $i = 1, 2, \ldots, N$
2. $A_{i+1} - A_i \ge d$，對 $i = 1, 2, \ldots, N-1$
3. $A_{(N+1)/2} = X$
4. 最小化 $\sum A_i$
----
#### 簽到題之二 -- Subtasks
- $[10]$ $N = 1$
- $[25]$ $d = 0$
- $[65]$ 無額外限制
----
#### 簽到題之二 -- Subtask 1
- 輸出 $X$ 就好。
- 送分的子題。
$\color{red}{\mbox{Wrong Answer}}\ 10/100$
----
#### 簽到題之二 -- Subtask 2
- 中位數前的數字都放 $1$。
- 中位數後都放 $X$。
$\color{red}{\mbox{Wrong Answer}}\ 35/100$
----
#### 簽到題之二 -- Solution
- 中位數前的就依照 $A_1 = 1, A_i = A_{i-1} + d$ 去放。
- 中位數後的也類似 $A_{(N+1)/2} = X, A_i = A_{i-1} + d$。
- 如果放完發現不合法就代表無解。
- 實際上只會出現在 $A_{(N-1)/2}$ 跟 $A_{(N+1)/2}$ 之間
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
### <font color="black"><b> pA. 競標 (Bidding) </b></font>
----
#### 競標
- 有 $N$ 個人在競標，每個人有若干資金 $\small(\le 10^9)$。
- 給 $M$ 次喊價紀錄，請問最後得標者及成交價格。
- 合法的出價定義：
- 要有足夠的錢
- 要比上一次喊的高
- 不能連續喊兩次（只有第一次會算合法）
----
#### 競標 -- Subtasks
- $[10]$ 人名沒有空格、都是合法出價
- $[20]$ 人名沒有空格、價格一定越喊越高
- $[40]$ 人名沒有空格
- $[30]$ 人名可能有空格
----
#### 競標 -- Solution
- 用 `getline` 輸入人名
- 用 `map<string, int>` 存每個人的資金
- 剩下的好好判斷就行
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 競標 -- 結論
- 這題主要是在考驗你們會不會使用 `map`
- 不過因為範圍小，也可以直接存陣列暴力找
---
### <font color="black"><b> pB. 畫作鑑定 (Art) </b></font>
----
#### 畫作鑑定
- 有 $N$ $\small(N \le 600)$ 個區間 $[\ell_i, r_i]$ $\small(1 \le \ell_i \le r_i \le 10^6)$
- 你要從中挑出 $N-K$ $\small(0 \le K \le 2)$ 個使畫作數量最小
----
#### 畫作鑑定 -- Subtasks
- $[28]$ $K = 0$
- $[25]$ $1 \le \ell_i \le r_i \le 15$
- $[47]$ 無額外限制
----
#### 畫作鑑定 -- Subtask 1
- 每個區間都要選
- Greedy 的經典題
- 將區間按照右界排序，選最左邊的區間的右界當作第一幅畫的製造時間一定最好
- 把包含該點的區間丟掉，重複以上行為
$\color{red}{\mbox{Wrong Answer}}\ 28/100$
----
#### 畫作鑑定 -- Subtask 2
- 時間點只有 $15$ 個
- 枚舉每個時間點是不是一幅畫的狀態
- 總共有 $2^{15} = 32\,768$ 個狀態
- 判斷能不能**至少**滿足 $N-K$ 位專家的意見
$\color{blue}{\mbox{Time Limit Exceeded}}\ 25/100$
----
#### 畫作鑑定 -- Solution
- 剛剛 greedy 的做法實際上可以在 $\mathcal{O}(N \lg N)$ 做完
- 放完一幅畫之後不用把重疊區間丟掉，只要 continue 就好
- 維護當前最後一幅畫的位置
----
#### 畫作鑑定 -- Solution（續）
- 因為 $K \le 2$ 很小，可以枚舉每一種假專家的組合
- 總共複雜度是 $\mathcal{O}\left(N \lg N + \binom{N}{K} \cdot N\right) = \mathcal{O}(N^{K+1}})$
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 畫作鑑定 -- 結論
- 請嘗試證明看看剛剛的 greedy 為什麼會對
---
### <font color="black"><b> pC. 打工 (Work) </b></font>
----
#### 打工
- 有一張 $N+1$ 點 $M$ 邊的連通圖 $\small(N, M \le 10^5)$
- 你一開始在點 $0$，也就是廚房，而其他點代表客人們
- 客人們分別想要 $a_i$ 盤菜，但你一次只能端至多 $K$ 盤
- 你最少需要進幾次廚房重新補貨？
----
#### 打工 -- Subtasks
- $[\hphantom{0}6]$ $K = 1$
- $[11]$ $N = M$、圖是一條 $0-1-\cdots-N$ 的鏈
- $[40]$ $N = M$、圖是一棵樹，且所有 $a_i = 1$
- $[15]$ $N, M \le 2000$
- $[28]$ $N, M \le 100\,000$
----
#### 打工 -- Subtask 1
- 輸出 $(\sum a_i) - 1$
- 這個子題的意義是讓你知道要 $-1$
- $6$ 分不拿白不拿
$\color{red}{\mbox{Wrong Answer}}\ 6/100$
----
#### 打工 -- Subtask 2
- 輸出 $\lceil (\sum a_i) / K \rceil - 1$
- 這個子題的意義是讓你知道要上取整
- $11$ 分還是不拿白不拿
$\color{red}{\mbox{Wrong Answer}}\ 17/100$
----
#### 打工 -- Solution
- 對每個連通塊做一遍 DFS 找出 $a_i$ 總合
- 該連通塊的答案就是 $\lceil (\sum a_i) / K \rceil$
- 答案記得 $-1$
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 打工 -- Solution 2
- 並査集
- 對每一條不包含廚房的邊都直接 `Union`
- `Union` 的時候維護該「集團」的 $\sum a_i$
- 答案計算方法同上
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
### <font color="black"><b> pD. 河內塔 (Hanoi) </b></font>
----
#### 河內塔
- 輸出 $3$ 根柱子 $K$ $\small(1 \le K \le 9)$ 個圓盤的盒內塔最大步數
- 不能出現同樣的狀態
----
#### 河內塔 -- Subtasks
- $K = 1, 2, \ldots, 9$
- $\text{score} = [5, 5, 8, 8, 12, 12, 15, 15, 20]$
----
#### 河內塔 -- Solution
- 狀態數最多是 $3^K$
- 考慮每個圓盤在哪個柱子
- 遞迴的時候先往不是終點的狀態移就好
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 河內塔 -- Code
```cpp=
void recur(int n, int a, int b, int c) {
if (n == k) return;
recur(n+1, a, b, c); /// 上面的 a -> c
cout << a << " " << b << "\n"; /// 最大的 a -> b
recur(n+1, c, b, a); /// 上面的 c -> a
cout << b << " " << c << "\n"; /// 最大的 b -> c
recur(n+1, a, b, c); /// 上面的 a -> c
}
```
- `recur(0, 1, 2, 3);`
---
### <font color="black"><b> pE. 小天使 (Angel) </b></font>
----
#### 小天使
- 給定 $N$ $\small(N \le 7000)$ 個數字
- 你要交換其中**任意**兩個數字
- 使得泡沫排序交換次數最少
----
#### 小天使 -- Subtasks
- $[11]$ $N \le 80$
- $[48]$ $N \le 1000$
- $[20]$ $1 \le a_i \le 2$
- $[21]$ $N \le 7000$
----
#### 小天使 -- Subtask 1
- $N$ 那麼小，當然直接暴力R
- 枚舉 $\binom{N}{2}$ 種交換方法
- 直接對它 bubble sort
- 複雜度是 $\mathcal{O}(N^4)$
$\color{blue}{\mbox{Time Limit Exceeded}}\ 11/100$
----
#### 小天使 -- Subtask 3
- 顯然交換第一個 $2$ 跟最後一個 $1$ 會最好
- 證明自己想想 (?)
$\color{red}{\mbox{Wrong Answer}}\ 20/100$
----
#### 小天使 -- Solution
- 總共的交換次數就是數列裡滿足 $i < j$ 且 $a_i > a_j$ 的數量
- 可以想像把所有點 $(i, a_i)$ 都打到平面上
- 每次交換兩個元素時都會對答案貢獻一個矩形區間
----
#### 小天使 -- Solution（續）
- 用 `large[i][j]` 紀錄 $a_1, a_2, \ldots, a_{j-1}$ 有多少個數字 $> a_i$
- 用 `small[i][j]` 紀錄 $a_{j+1}, a_{j+2}, \ldots, a_N$ 有多少個數字 $< a_i$
- 這樣就可以在 $\mathcal{O}(N^2)$ 時間內預處理
- 並在 $\mathcal{O}(1)$ 時間回答每次交換的答案了！
$\color{orange}{\mbox{Memory Limit Exceeded}}\ 59/100$
----
#### 小天使 -- Solution（續）
- 把 `large` 跟 `small` 存在一起
- 把陣列型態改成 `short`
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
### <font color="black"><b> pF. 塗鴉跳躍 (Jump) </b></font>
----
#### 塗鴉跳躍
- 有 $N$ $\small(N \le 5 \cdot 10^5)$ 個踏板，分別在高度 $y_1, y_2, \ldots, y_N$
- 你現在在高度 $0$，目標是跳到高度為 $H$ $\small(H \le 10^9)$ 的終點
- 你每次都必須跳到更高的踏板上，且一次跳的高度至多為 $K$ $\small(1 \le K \le H)$
- 請問有幾種跳法可以到高度 $H$？
- 兩種跳法相異若且唯若踩的踏板集合不同
- 輸出答案對 $10^9 + 7$ 取模
----
#### 塗鴉跳躍 -- Subtasks
- $[22]$ $N \le 20$、$H = 10^6$
- $[13]$ $N \le 1000$、$H = 10^6$
- $[\hphantom{0}7]$ $K = H = 10^6$、所有踏板高度皆相異
- $[11]$ $K = H = 10^6$
- $[35]$ $H = 10^6$
- $[12]$ $H \in \{10^6, 10^9\}$
----
#### 塗鴉跳躍 -- Subtask 3
- 每個都可以選擇踩獲不踩
- 答案是 $2^N$
- 又一個送分子題
$\color{red}{\mbox{Wrong Answer}}\ 7/100$
----
#### 塗鴉跳躍 -- Subtask 4
- 每個高度都可以選擇踩或不踩
- 同樣高度只能選一個
- 答案是 $\prod\limits_{1 \le i < H}{(c_i + 1)}$
- $c_i$ 是高度為 $i$ 的踏板數量
$\color{red}{\mbox{Wrong Answer}}\ 18/100$
----
#### 塗鴉跳躍 -- Subtask 1
- 重要的只有高度，所以可以把踏板們先排序好
- $N$ 很小，可以枚舉所有情況
$\color{blue}{\mbox{Time Limit Exceeded}}\ 22/100$
----
#### 塗鴉跳躍 -- Subtask 2
- 考慮使用 DP
- 令 $\texttt{dp}[i]$ 代表走到第 $i$ 個踏板的方法數量
- 此處已將踏板們排序過
- 有 $\texttt{dp}[i] = \sum\limits_{y_j < y_i~且~y_j + K \ge y_i}{\texttt{dp}[j]}$
- 複雜度是 $\mathcal{O}(N^2)$
$\color{blue}{\mbox{Time Limit Exceeded}}\ 35/100$
----
#### 塗鴉跳躍 -- Solution
- 上述 DP 式的轉移條件：
- $y_j < y_i$ 且 $y_j + K \ge y_i$
- 相當於是 $y_j \in [y_i - K, y_i)$
- 因為 $y_j$ 是按照順序排好的，所以可以轉移的區間一定是連續的
- 二分搜最小跟最大的 $j$
----
#### 塗鴉跳躍 -- Solution（續）
- 要怎麼計算區間的 $\sum\limits_{k=j}^{i-1}\texttt{dp}[k]$？
- ~~我會線段樹／BIT~~ 差分跟前綴和！
- 令 $\texttt{sdp}[i] = \sum\limits_{k=1}^{i}{\texttt{dp}[k]}$
- 那麼 $\sum\limits_{k=j}^{i-1}\texttt{dp}[k]$ 就變成 $\texttt{sdp}[i-1] - \texttt{sdp}[j-1]$
- 這樣 DP 的複雜度就是 $\mathcal{O}(N \lg N)$
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 塗鴉跳躍 -- Solution 2
- 每次當 $i$ 增加的時候，轉移區間左右界 $j_\ell$、$j_r$ 也會增加（或不動）
- 左右界移動的次數只會是 $\mathcal{O}(N)$
- 使用 two-pointer 維護左右界同時計算區間 $\texttt{dp}$ 值之和
- 這樣 DP 的複雜度會降到 $\mathcal{O}(N)$！
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
### 總覽
- pA - 送分題
- pB - 枚舉 + greedy
- pC - DFS 或 並査集
- pD - 遞迴
- pE - 觀察
- pF - DP + 二分搜 或 two-pointer
- pG - 送分題
----
### 總覽
**以下是只用「暴力」實作可以得到的分數**
- pA：$\color{lime}{100}$
- pB：$\color{lime}{28}\ /\ \color{lime}{25}\ /\ \color{red}{47}$
- pC：$\color{lime}{6}\ /\ \color{lime}{11}\ /\ \color{red}{40}\ /\ \color{red}{15}\ /\ \color{red}{28}$
- pD：$\color{red}{0}$ 到 $\color{lime}{100}$
- pE：$\color{lime}{11}\ /\ \color{red}{48}\ /\ \color{lime}{20}\ /\ \color{red}{21}$
- pF：$\color{lime}{22}\ /\ \color{red}{13}\ /\ \color{lime}{7}\ /\ \color{lime}{11}\ /\ \color{red}{35}\ /\ \color{red}{12}$
- pG：$\color{lime}{100}$
- 總共是 $100 + 53 + 17 + [0, 100] + 31 + 40 + 100 = [341, 441]$
----
---
### 謝謝收看
東西都放在[這裡](https://drive.google.com/drive/folders/10puAreRd1_sTSBsTvq3leNTDYeYntXvt)了
Google Drive
Gist
Clipboard
Sign in with Wallet
