# 113 學年度 全國資訊學科能力競賽模擬賽 題解

[TOC]

## 工作人員

- 總召：陳柏凱
- 顧問：王淇
- 題目組：龔德恩、陳澔樂、陳柏凱、郭育愷、蔡兆豐、王淇、高翊恩、張秉中、曹允碩、劉澈、蕭凱鴻、范釗維
- 測題組：黃靖宇、鄭安喆、卓育安、鄭傑元、吳柏翰、王品翔、李其樺、詹凱智、趙翊佑、張庭瑋、張皓崴
- 系統組：陳澔樂
- 美編組：蕭凱鴻

## 題本 [zh_TW](https://mirror.codeforces.com/gym/105570/attachments/download/28654/zh_TW.pdf) [en](https://mirror.codeforces.com/gym/105570/attachments/download/28653/en.pdf)
## [記分板](https://nhspc.cc/2024/ranking/Ranking.html)

## [Upsolving](https://codeforces.com/gym/105570)

## 正式賽

### A. 玻利維亞闖關王 (challenges)
###### author 陳澔樂 / setter 陳澔樂 / editorial 陳澔樂
:::spoiler 首先想一下怎樣的情況下是沒有解的：
若有一天的風速大於等於速度，那麼必定無法完成回程，於是必須將該天捨棄不考慮，捨棄完之後剩下的有效天數 $M^{'}$ ，若 $M^{'}<N$ 則無解，否則有解。
:::
以下只考慮有解的情況
:::spoiler Subtask 1
直接枚舉所有可能的天數對上關卡的組合，取最小的那一個。
複雜度 $O(P^M_N)=O(M!)$
:::
:::spoiler Subtask 2
風速=0
顯然的，用跑越快的天數去跑越長的跑道越好，所以直接照著 $v_i$ 排序完後貪心的配上跑道。
複雜度 $O(N\log N)$
:::
:::spoiler Subtask 3
繼續貪心，假設現在的跑道長度是 $l_i$，對上的天數速度是 $v_j$ ， 風速是 $s_j$ 那麼跑的時間將是：
$$\frac{l_i}{v_j+s_j}+\frac{l_i}{v_j-s_j} = l_i \frac{2v_j}{v_j^2-s_j^2}$$
所以這個問題可以看成是有一個長度為 $N$ 的陣列 $A$ 和一個長度為 $M$ 的陣列 $B$，重新排列 $A,B$ 使得 $\sum\limits_{1\leq i\leq N} A_i B_i$ 最小， 根據排序不等式 $A$ 是順序 $B$ 是逆序時會達到最小值。

所以我們照 $\frac{2v_j}{v_j^2-s_j^2}$ 排序天數， 然後貪心的選長的跑道對上小的 $\frac{2v_j}{v_j^2-s_j^2}$ 天數。
複雜度 $O(N\log N)$
Note: 建議寫交叉相乘的全整數排序。
:::

### B. 種小黃瓜 (cucumber)
###### author 陳柏凱 / setter 陳柏凱 / editorial 陳柏凱

:::spoiler Subtask 1
$x_i=-1$ 代表字典序要最大，每次想要直接取 $b_{p_i}$，但有可能會太大導致某個 $|b_j-b_{j+1}|\le d_j$ 不成立，所以可以先用一個正著與一個反著的迴圈，令 $b_i=\min(b_i,b_{i-1}+d_{i-1})$ 跟 $b_i=\min(b_i,b_{i+1}+d_i)$，把每個 $b_i$ 調成每次取都合法的狀態，用 Dijkstra 調 $b_i$ 也可以。

複雜度 $O(n)$ 或 $O(n\log n)$。

接下來的 Subtask 都會預設 $b_i$ 一開始都被調整好了。
:::

:::spoiler Subtask 2
令 $l_i,r_i$ 是目前第 $i$ 個數字合法的區間，一開始 $l_i=1,r_i=b_i$。
每次如果遇到 $x_i=1$，就取 $l_i$，否則取 $r_i$，假設這一次取的數字是 $k$，那 $l_{i+1},r_{i+1}$ 會被調整成 $l_{i+1}=\max(l_{i+1},k-d_i),r_{i+1}=\min(r_{i+1},k+d_i)$。

複雜度 $O(n)$。
:::

:::spoiler Subtask 3
每次取 $l_{p_i}$ 或 $r_{p_i}$ 時，用這個數字暴力調整其他所有人的範圍。

複雜度 $O(n^2)$。
:::

:::spoiler Subtask 4
發現每次取一個數字時，一定是跟某個人加上前 / 後綴和取 $\min/\max$，這個東西可以用 set or map or BIT or 線段樹維護。

複雜度 $O(n\log n)$。

---

每次直接取 $l_i,r_i$ 是合法的證明：
還沒取的時候每個人區間都是合法的，假設這次取了 $l_i$，因為 $l_{i-1}\le l_i+d_{i-1}$，用 $l_i+d_{i-1}$ 更新 $r_{i-1}$ 還是滿足 $l_{i-1}\le r_{i-1}$，對於取 $r_i$ 還有往右邊更新的情況同理。
:::

### C. 滾遠一點 (getoutaway)
###### author 郭育愷 / setter 郭育愷 / editorial 郭育愷

:::spoiler 首先將題目轉化為目標更單純的圖論問題
可以發現題目所述的移動過程，在一開始的起點並非葉節點的情況下，兩人會不斷移動直到移動到葉節點，而兩人的移動路徑合起來剛好是兩個葉節點間的唯一簡單路徑；而即使起點為葉節點，實際上也只是第一個人移動後第二個人就只能在起點無法移動，直到第一個人走到另一個葉節點，此時兩人移動的路徑合起來仍是兩個葉節點間的路徑。

總之可能的路徑必然是兩個葉節點間的唯一最短路徑；另外也可以發現 $k$ 即是葉節點的數量。
:::

:::spoiler Subtask 1
由於 $k=2$ 所以輸入為鏈。唯一可能的移動方式是兩人各移動到兩個葉節點上，路徑長為所有邊的邊權和。
:::

:::spoiler Subtask 2
由於 $k=n-1$ 所以輸入為星，即 $n-1$ 個葉節點接到一個中心節點的樹。此時所有的移動情況會是從所有邊中任取相異兩條邊，因此可以對所有邊依邊權進行排序，答案分別是前兩大的邊權和與前兩小的邊權和。
:::

:::spoiler Subtask 3
不必想到上述的題目轉化，可以單純模擬題目所述的過程，不過需要先發現題目所述兩人輪流移動的這個順序並不影響結果，因此可以先讓一個人移動到無法移動後，再換另一個人直到無法移動。

預設的具體作法為，遍歷所有 $n$ 個點將其當作起點，然後進行第一個人的 DFS，並記錄每個點當前是否被拜訪，此部分複雜度為 $O(n^2)$；然後當第一個人遇到葉節點後，再從起點進行第二個人的 DFS，並且需要注意不能走第一個人拜訪過的點，而當第二個人到達葉節點後，目前兩人所走的路徑總長即為答案的其中一種情況，將最大最小值更新，由於只會在其中 $k$ 個點觸發第二個人的 DFS，故此部分複雜度為 $O(n\times k\times n)$。總體複雜度為 $O(n^2k)$。
:::

:::spoiler Subtask 4
不必想到上述的題目轉化，可以單純模擬題目所述的過程，但需要比 Subtask 3 多發現，如果我們將遍歷選擇起點時都選在葉節點，其實也可以涵蓋到所有情況，並且第二個人必然無法移動。

預設的具體作法為，遍歷所有 $k$ 個葉節點將其當作起點，然後進行 DFS，由於此時第二個人無法移動，因此第一個人到達另一個葉節點時的路徑長即為答案的其中一種情況，將最大最小值更新。總體複雜度為 $O(nk)$。
:::

:::spoiler Subtask 5
這個子任務是有想到上述的題目轉化，但沒想到用樹 DP 解的情況可能可以拿到的，但預設作法是 LCA，似乎是不比樹 DP 簡單，所以我也不確定有沒有人會拿了這個沒有滿分？

預設的具體作法是，先任意定根進行 LCA 的預處理，此部分複雜度 $O(n log n)$；然後將 $k$ 個葉節點任選相異兩個，用 LCA 找出路徑長，此部分複雜度 $O(k^2 log n)$。總體複雜度為 $O((n+k^2)log n)$。
:::

:::spoiler Subtask 6
想到上述轉化後，利用樹 DP 可以求出「一棵有根樹即其所有子樹從其根節點到其葉節點的最大、第二大、最小、第二小距離(但最大與第二大須經由不同子節點，最小與第二小也須經由不同子節點)」；轉移方式是將其所有子節點的最大/最小到葉節點距離加上與該子節點間距離，然後選出最大與第二大/最小與第二小的記錄下來，如果沒有子節點則把最大、第二大都設為 -INF，把最小、第二小都設為 INF，僅有一個子節點的時候則僅記錄最大、最小，將第二大設為 -INF，第二小設為 INF；最終遍歷所有節點，並將每個節點所記錄的最大、第二大相加來更新答案最大值，最小、第二小相加更新答案最小值。

總體複雜度為 $O(n)$。
:::

### D. 高嵩登山纜車 (gondola)
###### author 陳柏凱 / setter 陳柏凱 / editorial 陳柏凱

:::spoiler Subtask 1
首先對於每座山峰可以找出 $L_i,R_i$，代表 $h_i$ 可能的範圍。
令 $dp_{i,j,k}$ 是輪到第 $i$ 座山峰，已經蓋了 $j$ 條纜線，目前有 $k$ 個起點站還沒配到終點站，最大的收益，每個狀態可以 $O(1)$ 轉移，最後 $\max\limits_{0\le i\le m}(dp_{r,i,0})$ 即為答案。

複雜度 $O(n^2K)$。
:::

:::spoiler Subtask 2
用線段樹維護這個區間的 $L_i$ 最小值，$R_i$ 最大值，還有 $-L_i+R_j\ (i<j)$ 的最大值，每次詢問可以 $O(\log n)$ 求出答案，複雜度 $O(n+q\log n)$。

另解：將詢問排序後直接跑兩層迴圈求出左界在 $l$，右界在 $r$ 的答案，因為都是常數很小的操作，時限又給很多，所以 $O(n^2+q\log q)$ 會過。
:::

:::spoiler Subtask 3
發現把 dp 寫出來後可以 aliens 優化，penalty 的範圍為 $[0,H]$，dp 轉移可以寫成 max+ 矩陣的形式，可以對每個 penalty 蓋一個資料結構，每次詢問時二分搜 penalty，並在資料結構上求出 dp 值，如果蓋線段樹，預處理的複雜度為 $O(nHK^3)$，每次詢問的複雜度如果是直接把線段樹上的矩陣一個一個乘起來，複雜度為 $O(K^3\log H\log n)$，如果維護一個向量，照順序去乘矩陣，複雜度可以少一個 $K$ 變成 $O(K^2\log H\log n)$。
:::

:::spoiler Subtask 4
$K$ 跟詢問數量變很大，用前一個 subtask 的方法會 TLE，想要找出一個每次詢問就能很快找出答案的資料結構，於是可以蓋 $H+1$ 個貓樹，每次詢問等於是把兩個矩陣相乘，目前詢問的總複雜度為 $O(qK^3\log H)$，發現這樣還是會 TLE，觀察到乘完矩陣後只會要位置 $(0,0)$ 的數值，那根本直接算兩個向量的內積就好了，複雜度變成 $O(qK\log H)$。

時間複雜度 $O(nHK^3\log n+qK\log H)$。

空間複雜度如果是離線做可以做到 $O(nHK)$ 或 $O(nHK^2)$，在線做可以做到 $O(nHK\log n)$ 或 $O(nHK^2\log n)$ 後者如果正常寫大概是題目 ML 的一半，如果你開四倍之類的就有可能 MLE。
:::

### E. 荒野大飆馬 (horse)
###### author 蔡兆豐 / setter 龔德恩、張秉中、蔡兆豐 / editorial 蔡兆豐、蕭凱鴻

:::spoiler Subtask 1
從名次前面的嘗試構造到後面，策略是盡量延後熱係數 $h$ 必須增加的名次。
可以從名次前面的開始構造，每次選取前綴 $\max L_j$ 作為自己的 $h$，最後檢查是否滿足每個人的 $h$ 都在自己的區間 $[L_i, R_i]$ 內。
:::

:::spoiler Subtask 2
每個人都賦值成 $L_i$ 然後根據 $L_i$ sort 構造排名。
:::

:::spoiler Subtask 3
位元 dp，定義 $dp[msk] =$ 已經固定前 $\text{popcount}(msk)$ 名的情況下，最小的 $h$ 可能值。
轉移的時候可以枚舉第 $\text{popcount}(msk)$ 名是哪個人，然後用 Subtask 1 的作法賦值 $h$，在實作過程中順便檢查固定那些人是否都有在正確的位置，每個人的 $h$ 有沒有在自己的區間 $[L_i, R_i]$ 內，然後最後回溯解即可。
總複雜度 $O(N 2^N)$。
:::

:::spoiler Subtask 4
如果兩個人 $(i, j)$ 有 $L_i \leq R_i < L_j \leq R_j$ 的話代表 $i$ 的排名一定比 $j$ 還要好。
可以對於所有滿足以上性質的 $(i, j)$ 建一條 $j \rightarrow i$ 的邊，對於每個已經確定的點依照 $p_j$ 的順序由小到大把 $j$ 可以走到的點且還沒造訪過的點放到 $j$ 的前面。
總複雜度 $O(n^2)$。
或是不擅長資料結構的同學會被卡掉。
:::

:::spoiler Subtask 5
先將已固定的人用 Subtask 1 的方式縮減各自的 $L$ 範圍，於是已固定的 $L$ 隨著名次遞增。對於每個尚未決定名次的候選人，利用他的 $R$ 和前面得到遞增的 $L$，找到他一定不能放在某個後綴。

從排名後面的嘗試一一填入可能的候選人，$L$ 下降到某個值的時候，會讓一些 $R$ 大於這個值的候選人在這之後可能被選到。遇到還沒填入的空格時，若沒有可能的候選人則無解，否則在其中貪心的選擇 $L$ 最大者填入。最後再按照 Subtask 1 的作法構解即可。可以使用 max heap 實作，總複雜度 $O(N \log N)$。

證明：

---

**Claim 1**
定義一對 $i<j$ 是好的若 $L_i \leq R_j$。
有沒有解若且唯若所有 $i<j$ 都是好的。

**Proof 1**
數學歸納法假設若有解的話存在一組解的最後一名的 $h=\max L_i$。
具體證明留給讀者自行證明。

---

**Claim 2**
假設所有已固定的人中的 $L_j$ 最大的為 $L$，未固定的人中有 $R_i \geq L$ 的依照 $L_i$ 的順序由大到小從名次後面的放不會影響到有解性。

**Proof 2**
定義集合
$$
\begin{align*}
A & = \{ j \mid p_j \neq 0 \} \\
B & = \{ i \mid p_i = 0 \text{ and } R_i < L \} \\
C & = \{ i \mid p_i = 0 \text{ and } R_i \geq L\}
\end{align*}
$$
我們證明如果有解的話，將集合 $C$ 中元素的順序依照 $L_i$ 排序填入的話也沒問題。
只需考慮 $c \in C$ 和 $a \in A$ 或 $b \in B$ 之間的關係即可。
對於 $c < a$ 或 $c < b$ 的情況，因為本質上對 $c$ 排序填入後，前綴 $L_c$ 的值只有可能會變得更小，所以原本可以的話排序後這種 pair 還是不會違反好的 pair 這個條件。
對於 $c > a$ 或 $c > b$ 的情況，因為 $L_a \leq L$ 或 $L_b \leq R_b < L$ 且 $L \leq R_c$ ，所以排序後自然還是會是好的。

---

所以根據 Claim 2 一次處理已固定人中排名最後面的以及他更後面名次的，決定好這些東西的名次之後，繼續處理前面尚未處理的部分，最後再根據 Subtask 1 構造 $h$。

:::

### F. 鐵路規劃 (rail)
###### author 王淇 / setter 王淇 / editorial 王淇

沒有人過 rail 真的太誇張了 (by LittleCube)。
以下均以圖論的角度說明，題目等價於對一張簡單圖的邊雙著色。

:::spoiler Subtask 1
$n \leq 7$ 所以 $m \leq 21$，暴力枚舉。
:::

:::spoiler Subtask 2
考慮整張圖連通且點度皆為 $2$，只能形成一個環。
因此，如果環的長度是奇數，則公平度為 $n - 1$，否則公平度為 $n$。
塗色只需要在環上交替塗色即可。

為了方便，對於奇環我們唯一沒有滿足的點是「壞掉的」點。
:::

:::spoiler Subtask 3
假設圖是一個環，回到 Subtask 2。

否則，圖是一張水母圖，我們可以找到那個環，對於圖扣掉這個環的邊所形成的森林，可以隨意找到一個所有不在環上且非葉節點都被滿足的塗色方法，
剩下的狀況就簡單了：儘管環可以是奇環，我們可以把「壞掉的」點指定為有森林相鄰的點，這樣在環上交替塗色之後所有的點（除了 degree = 1）的都會被滿足。
:::

:::spoiler Subtask 4, 5
值得一提的是最大公平度永遠是 $(\sum_v [\deg v \geq 2]) - [\text{the graph is an odd cycle}]$，
這個結論可以用各種複雜度隨意的想法證明，如果能早早確定這個想法應該可以在推導上有很好的輔助效果。

---

從上一個子任務來的想法是找一個 spanning tree / spanning pseudo-tree 直接解決。
不過你找完之後可能會有兩種點需要修理：
- 在 spanning subgraph 上 degree 只有 1 的點，但在整張圖 degree >= 2。
- 不幸的 pseudo-tree 找成 Hamiltonian odd cycle，上面會有一個壞掉的點。

所幸兩個問題只會發生一個（因為你找到一個環就不會有 degree = 1 的狀況）。

spanning subgraph 上 degree 只有 1 的點很好修理，只要先找環，森林部份都用 DFS 走，這樣就不會有邊在兩個 degree 為 1 的點之間了，所以每個人都能找到沒有用過的邊來修理。

第二個問題也很好解決，隨便挑一個原圖 degree >= 3 的點當壞掉的點，多的邊就可以拿來修理。
找不到的話整張圖其實就是一個環，所以沒有人能修理他。

其他方法也行得通，就是小心不要讓兩個需要修理的人共用資源就好。

---

另外，這題有個輕鬆的作法：
考慮 DFS，邊的顏色由下面的方法指定：
- 如果這條邊是遍歷這個點的第一條邊，把他的顏色設成進來這個點的邊相反的顏色（對於起始點則隨意）
- 如果這條邊不是遍歷這個點的第一條邊，把他的顏色設成上一條成功遍歷邊相反的顏色
- 注意到儘管一條邊可能對面的點已經被遍歷，但如果這條邊尚未被塗色，則需要塗色（或者可以如一般歐拉迴路一樣的方式實作，改成紀錄邊是否被遍歷而非點）

注意到除了起始點，所有 degree $\geq 2$ 的點都會滿足條件，因此只要把起始點找任意一個 degree $\geq 3$ 的點就可以輕鬆滿足目標，
若是找不到則說明整張圖是一個環或是一條鍊，而上面的 DFS 正好會對應到最佳的交替塗色。

Subtask 4 的目的是給一些時間複雜度不小心寫壞的人，或者是沒有發現到起始點可能會壞掉的作法：對於所有點都嘗試一遍並取最大值就能通過。

:::

### G. 踢足球 (soccer)
###### author 蔡兆豐 / setter 張秉中、蔡兆豐 / editorial 蔡兆豐、蕭凱鴻

:::spoiler Subtask 1
寫好線段相交之後照著定義寫。
記得 cross 要先取 sign 之後再乘，要不然就去開 int128。
複雜度 $O(N M^2)$。
:::

:::spoiler Subtask 2
檢查用 subtask，少掉一些怪怪的三點共線 cases，做法和 Subtask 4 一樣。
:::

:::spoiler Subtask 3
將所有球門依照 $x$ 排序，可以枚舉每條折線，用 $O(1)$ 時間計算這條線和 $y=$ 那個相同的 $y$ 的交點座標，
:::

:::spoiler Subtask 4
將所有球門依照 $(x, y)$ 排序，只枚舉左邊連到右邊的 pair。
枚舉在左邊的球門以及某條折線計算有幾個在右邊的球門會經過這條折線。
精美作圖。
紅色的點是目前枚舉的球門，兩條折線是代表在這個極角範圍內的右邊球門才有機會，黃色的線是目前枚舉的折線，藍色區域和綠色區域中出現幾個球門就代表有幾個 pair 跨過這條黃色折線。

預處理從紅色點且在右邊的所有點的極角順序，綠色的區域是一個極角區間，可以從最右邊開始一個一個點加入資料結構裡面，用一個區間資料結構算有幾個點。
對於在兩條藍色虛線中間的球門，可以用暴力檢查，因為對於一個黃色的折線，只有一區對應的點（藍色虛線中間的）需要被暴力檢查，所以藍色區域種類的貢獻是均攤 $O(m^2)$ 的。

總複雜度是 $O(m n \log(n+m) + m^2)$ 。
:::

:::spoiler 另解 by cheissmart
對於每個球門，計算有多少點對連線**不會通過**這個球門。球門把平面分成兩半，跨越半平面的貢獻可以利用從球門的哪一側通過，分別使用極角排序搭配雙指針算出。實作可以把所有點分為四群（平面兩側、射線兩側），會簡潔很多。
:::

### H. 太鼓問題 (taiko)
###### author 高翊恩 / setter 高翊恩 / editorial 高翊恩

:::spoiler Subtask 1
可以暴力枚舉所有合法的打擊方式，複雜度 $O(N2^N)$
:::
:::spoiler Subtask 2
因為 $L=R$ ，所以題目變成「瞬移次數最少」的合法序列。
觀察到「輪流使用兩手打擊每個音符」是合法解中瞬移次數最小的一組解，所以可以 greedy 分配，複雜度 $O(N)$
:::
:::spoiler Subtask 3
考慮做 DP 。在 dp[n] 中記錄 $9$ 個數值：「在第 $n$ 單位時間末，左手已經休息『 $0$ / $1$ / $\geq2$ 』單位時間，且右手已經休息『 $0$ / $1$ / $\geq2$ 』單位時間的條件下，最少的不適度總和」，則可以根據 $s[n]$ 及 $dp[n-1]$ 推得 $dp[n]$ 的所有數值。具體細節有滿多 case 要處理，實作時需要小心。複雜度 $O(N)$

:::

### I. 巨砲排球 (volleyball)
###### author 陳澔樂 / setter 陳澔樂 / editorial 陳澔樂
:::spoiler 構解
可以發現若 $M=0$ 那麼我派出任意隊伍期望最小值都是一樣的。

再來如果 $M\ne 0$ 那麼我的 $[x,y]$ 一定是順序的對上 $k_i\ne 0$ 的點（因為 $k_i\ne 0$ 的數字也是一個區間）

那剩下的跟 $M=0$ 的解一樣，輸出剩下的數字任意排列就好了。

這樣就 20 分了 沒有的人要檢討
:::
接下來假設自己派出去的隊伍 $P$ 已經確定了
:::spoiler Subtask 1
直接$O(N!)$算 $S(\hat{k},P)$ 的期望值
:::
:::spoiler Subtask 2
Trick: 算出 $S(\hat{k},P)$ 小於等於某個數字 $d$ 的 $\hat{k}$ 的數量

怎麼算呢？ 先將我的隊伍的每一個人可以對上的人的數量算出來，假設某個人的排名是 $i$ 那排名小於等於 $i+d$ 的人都可以對上他。

現在從 $i+d$ 最小的人 （也就是 $i$ 最小的，也就是 $1$ ） 開始，他總共有 $1+d$ 種選擇 ， 第二小的人有 $2+d-1$ 種（有一種被前面選走了），第三小的人有 $3+d-2$ 種 .... 注意在 $N-d$ 之後不會有新的東西 所以可以 $O(N)$ 算期望值小於等於 $d$ 的數量 然後算差分算期望值 這樣是 $O(N^2)$
:::
:::spoiler Subtask 3
現在有些人被拔掉了 但是你還是可以用 Subtask 2的作法 $O(N)$ 算每個人有多少種選擇 所以還是 $O(N^2)$
:::
:::spoiler Subtask 4
你會發現 Subtask 2 的作法很有規律性，是某個東西的次方乘以某個連續區間相乘，所以快速冪+階乘預處理 就可以在 $\tilde{O}(N)$ 做完
:::
:::spoiler Subtask 5
發現其實每一個 $d$ 也蠻有規律性的

一個次方x連續相乘x另一個次方x另一個連續相乘

好好作也可以 $\tilde{O}(N)$ 做完
:::
輸出 $1\sim N$ 就有 8 分了 .....
部分分 50 分其實也很簡單，譴責。