0x02 2020 花中二模題解

## 0x02 2020 花中二模 題解 ---- ### 大綱 - pG - 簽到題之二 (Registration2) - pA - 競標 (Bidding) - pB - 畫作鑑定 (Art) - pC - 打工 (Work) - pD - 河內塔 (Hanoi) - pE - 小天使 (Angel) - pF - 塗鴉跳躍 (Jump) --- ### pG. 簽到題之二 (Registration2) ---- #### 簽到題之二 - 給定 $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$ --- ### pA. 競標 (Bidding) ---- #### 競標 - 有 $N$ 個人在競標，每個人有若干資金 $\small(\le 10^9)$。 - 給 $M$ 次喊價紀錄，請問最後得標者及成交價格。 - 合法的出價定義： - 要有足夠的錢 - 要比上一次喊的高 - 不能連續喊兩次（只有第一次會算合法） ---- #### 競標 -- Subtasks - $[10]$ 人名沒有空格、都是合法出價 - $[20]$ 人名沒有空格、價格一定越喊越高 - $[40]$ 人名沒有空格 - $[30]$ 人名可能有空格 ---- #### 競標 -- Solution - 用 `getline` 輸入人名 - 用 `map<string, int>` 存每個人的資金 - 剩下的好好判斷就行 $\color{lime}{\mbox{Accepted}}\ 100/100$ ---- #### 競標 -- 結論 - 這題主要是在考驗你們會不會使用 `map` - 不過因為範圍小，也可以直接存陣列暴力找 --- ### pB. 畫作鑑定 (Art) ---- #### 畫作鑑定 - 有 $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 為什麼會對 --- ### pC. 打工 (Work) ---- #### 打工 - 有一張 $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$ --- ### pD. 河內塔 (Hanoi) ---- #### 河內塔 - 輸出 $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 recur(n+1, c, b, a); /// 上面的 c -> a cout < c recur(n+1, a, b, c); /// 上面的 a -> c } ``` - `recur(0, 1, 2, 3);` --- ### pE. 小天使 (Angel) ---- #### 小天使 - 給定 $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$ --- ### pF. 塗鴉跳躍 (Jump) ---- #### 塗鴉跳躍 - 有 $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://i.imgur.com/TGWJucQ.jpg) --- ### 謝謝收看東西都放在[這裡](https://drive.google.com/drive/folders/10puAreRd1_sTSBsTvq3leNTDYeYntXvt)了