# NCPC 清大校內初選 題解

題本：TBD

## A. Anaconda

我們可以使用一個支援下功能的線段樹求解，每一個動作複雜度都是 $O(\log n)$ :

* 1. 計算區間總和
* 2. 計算區間最大值
* 3. 區間加減值

每一次的詢問，我們就直接對整段每一個數字都加 1，然後使用一個無窮迴圈，找修改的區間是否有數字的最大值超過 $n$，如果有就把這一個數字減 $n$，直到沒有為止。

不論怎麼修改區間，一個位置至少要被修改 $n$ 次才可能會需要被挑出來減 $n$，因此一個位置最多會被減掉 $\frac{q}{n}$ 次。因此這一個暴力的修改，對所有的位置最多總共只會被執行 $n\times\frac{q}{n}=q$ 次，因此每次修改平均複雜度為 $O(\frac{1}{q}\times q\log n)=O(\log n)$

## B. Killing Machine

給一個桌子 $(l,r)$, 顯然他造成的影響可以由左到右區分為

A: (由左到右)遞增成本部分
B: 無解部分
C: 遞減成本部分

若B部分不為空, 則可以簡單地直接切割成遞增和遞減部分加入掃描線. 若B為空, 則我們需要處理AC交集的部分. 我們把這個狀況往下區分為

1. 交集部分包含 $(l+r)/2$, 取floor或ceiling不影響
2. 交集部分完全落在左半邊
3. 交集部分完全落在右半邊

對於 Case 1, 顯然成本分布對稱. Case 2 則讓交集部分使用遞增成本, Case 3 vice versa. 如此再把成本切割成遞增和遞減部分丟入掃描線. 複雜度 $O(m+n)$.

## C. Pole of Inaccessibilit

可以考慮動態規劃的方法，對於每一個點，假設最遠陸地在右上象限，我們可以很簡單的使用迴圈找出

dp[i][j] 
  = 0                               if map[i][j] is island
  = 1 + min(dp[i][j-1], dp[i-1][j]) for the others

枚舉所有象限，即可找出每一個點離陸地的最近距離，再題目要求輸出答案即可

找距離的部分也可以使用多起點的最短路徑 / BFS 演算法來求答案。

## D. Matsuri

$O(n^3)$ KM 演算法模板。台灣比賽常見網路流題目，抽查大家參考資料準備是否周全。

## E. Trinitas

根據正弦定理有

$$\frac{a}{\sin A}=2R$$

任意三角形面積公式

$$S=\frac{1}{2}bc\sin A$$

因此

$$\sin A=\frac{2S}{bc}$$

帶入正弦定理得

$$R=\frac{abc}{4S}$$

其中 $a,b,c$ 可以簡單的用畢氏定理求出，$S$ 可以用向量外積求出，兩者相除即為所求：

$$R^2=\frac{|\overline{AB}|^2|\overline{BC}|^2|\overline{CA}|^2}{4\times|\overline{AB}\times\overline{AC}|^2}$$

## F. Hosting a Parking Lot

依題意的基本解法，有許多可能性

設法將相同的 Hash 轉成相同的整數進行 Array 操作，或是直接用 map。

也可以 sort by hash，將時間差算出後相加。

正解

在公式上，入場時間是減項，離場時間是加項。

故不需考慮 hash，使用一個 stack 或是 queue 記錄目前還在場中的入場時間；每遇見一個離場時，隨意抵銷一個入場，如此並不會影響最終計算的總時間。

在排隊理論中，如果僅考慮 “加總” 或 “平均” 的 “等待時間”，那麼只要 Queue 持續被消化的話，queue 中的 priority 似乎不太重要。

看來只看 “覆蓋率” 的疫苗施打似乎也是如此。

## G. Power Network

題目敘述：給定一棵大小為 $N$ 樹，問有多少 vertex subset 只屬於 dominating set 或是只屬於 vertex cover

觀察：樹上 vertex cover 必定屬於 dominating set (事實上，只要連通圖都符合這點)

因此解答為 dominating set 個數 - vertex cover 個數

計算 vertex cover 個數可以使用動態規劃，時間複雜度 $O(N)$：

- 維護 dp[N][2]
- dp[v][0] 表示考慮以 $v$ 為根的子樹中，$v$ 不屬於 vertex cover 的個數
- dp[v][1] 表示考慮以 $v$ 為根的子樹中，$v$ 屬於 vertex cover 的個數

$$
\begin{align}
dp[v][0] &= \prod_{c \in \text{child of } v} dp[c][1] \\
dp[v][1] &= \prod_{c \in \text{child of } v} (dp[c][0] + dp[c][1])
\end{align}
$$

計算 dominating set 個數也可以使用類似方法，時間複雜度 $O(N)$

- 維護 dp[N][3]
- dp[v][0] 表示考慮以 $v$ 為跟的子樹中，$v$ 並不屬於 dominating set，也尚未被 dominating set 中節點 dominate 的個數
- dp[v][1] 表示考慮以 $v$ 為跟的子樹中，$v$ 並不屬於 dominating set，但是已經被 dominating set 中節點 dominate 的個數
- dp[v][2] 表示考慮以 $v$ 為跟的子樹中，$v$ 屬於 dominating set 的個數

$$
\begin{align}
dp[v][0] &= \prod_{c \in \text{child of } v} dp[c][1] \\
dp[v][1] &= \prod_{c \in \text{child of } v} (dp[c][1] + dp[c][2]) - \prod_{c \in \text{child of } v} dp[c][1] \\
dp[v][2] &= \prod_{c \in \text{child of } v} (dp[c][0] + dp[c][1] + dp[c][2])
\end{align}
$$

## H. Hive

思路：在每個蜂巢的格子內填入水管的方向，並且以圖中的輪廓線表示每個狀態：


並且標記巢狀格子的每個邊是由哪跟水管通過。每次填入一格水管後更新輪廓線上水管通過的狀況。
總共有 22 種填入水管的方式，如下圖所示。填入水管時需注意水管不能斷掉，不同的水管也不能接在一起。


透過此輪廓線 DP 的方法，可以在 $O(R \cdot C \cdot 3^{2C})$ 的時間內求出答案，其中 $R$ 是蜂巢的列數，$C$ 是蜂巢的行數。

## I. Sidewalk

求區間總和，根據高中數學，$a_i+a_{i+1}+\cdots +a_j=S_j-S_{i-1}$

其中 $S_i=a_1+a_2+\cdots +a_i$，即可透過預處理後，$O(1)$ 求出解答。

## J. Image Rotation

依題意解答