簽到題之二

• 給定 \(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\)

競標

• 有 \(N\) 個人在競標，每個人有若干資金 \(\small(\le 10^9)\)。
• 給 \(M\) 次喊價紀錄，請問最後得標者及成交價格。
• 合法的出價定義：
  • 要有足夠的錢
  • 要比上一次喊的高
  • 不能連續喊兩次（只有第一次會算合法）

競標 – Subtasks

• \([10]\) 人名沒有空格、都是合法出價
• \([20]\) 人名沒有空格、價格一定越喊越高
• \([40]\) 人名沒有空格
• \([30]\) 人名可能有空格

競標 – Solution

• 用 getline 輸入人名
• 用 map<string, int> 存每個人的資金
• 剩下的好好判斷就行

\(\color{lime}{\mbox{Accepted}}\ 100/100\)

競標 – 結論

• 這題主要是在考驗你們會不會使用 map
• 不過因為範圍小，也可以直接存陣列暴力找

畫作鑑定

• 有 \(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 為什麼會對

打工

• 有一張 \(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\)

河內塔

• 輸出 \(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

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);

小天使

• 給定 \(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\)

塗鴉跳躍

• 有 \(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：\(\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]\)