NCTU PCCA Winter Camp Contest 2020 - 題解
===

:::info
如果你想在比賽結束後解題，請在 DOMjudge 界面的右上角 contest 選擇 "PCCAWinter2020p"(NCTU PCCA Winter Camp Contest 2020 - Practice) 再上傳，否則只會收到各種 `TOO-LATE`
:::
## 目錄
<table style="text-align: center; font-weight: bold;">
<tr>
<td><a href="#A-Ascend-the-Alps">A</a></td>
<td><a href="#B-Blocking-Buildings">B</a></td>
<td><a href="#C-Capoo’s-Christmas">C</a></td>
<td><a href="#D-Dope-Design">D</a></td>
</tr>
<tr>
<td><a href="#E-Eerie-Echo">E</a></td>
<td><a href="#F-Flawlessly-Fortified">F</a></td>
<td><a href="#G-Gap-Gambolling">G</a></td>
<td><a href="#H-Hard-to-Handle">H</a></td>
</tr>
</table>

# A. Ascend the Alps
###### 出題者：黃克崴(toxicpie)
## 題目翻譯
給平面上一條折線，對於每個頂點 $P$，請求出 $y$ 座標最高的頂點 $Q$ 使得線段 $\overline{PQ}$ 除了端點外都嚴格在折線上方(即 $P$ 看得到 $Q$)。(好像沒翻譯到)
:::spoiler spoiler
這題是生另一道~~毒瘤~~難題時順便產出來的東西，但比賽縮短成 3 小時後難題就被砍掉了QQ
~~賽中覺得應該放那題而不是這東西~~
:::
## 解法
**Lemma:** 對於每個點 $P$，它往左能看到最高的點 $Q_1$ 一定在它左邊的凸包上。

證明：假設 $P$ 關於左邊凸包的切點是 $T$，那 $P$ 看得到的頂點們一定在 $T$ 和 $P$ 之間。假設這其中最高的點是 $Q_1^\prime$ (注意到 $Q_1^\prime$ 一定在該凸包上)，可以分成兩種 case：
1. $P$ 看得到 $Q_1^\prime$，那就有 $Q_1=Q_1^\prime$。
1. $P$ 看不到 $Q_1^\prime$，代表存在某個點 $X$ 在 $Q_1^\prime$ 和 $P$ 之間使得 $\overrightarrow{PQ_1^\prime}\times\overrightarrow{PX}\le 0$。由於 $X$ 的 $y$ 座標 $\le Q_1^\prime$ 的 $y$ 座標，我們有 $\overrightarrow{PT}\times\overrightarrow{PX}\le 0$ ，即 $P$ 看不到 $T$，與 $T$ 的定義矛盾。

因此有 $Q_1=Q_1^\prime$。對於每個點 $P$，他的答案是往左能看到最高的點 $Q_1$、往右能看到最高的點 $Q_2$ 以 $P$ 三者 $y$ 座標的最大值。根據 lemma，我們只要從左右各建一次凸包就可以維護每個點的答案。
# B. Blocking Buildings
###### 出題者：呂爾軒(HanaYukii)
## 題目翻譯
給定 $1 \sim n$ 每個點的高度，多次詢問某個 $[L,R]$ 區間高度不大於 $K$ 的點有幾個
## 解法
本題有多種解法，以下為其一。
先假設位置 $0$ 的高度為 $0$，對於每個詢問，可以將其拆成 ( $[0, R]$ 有幾個點不大於 $K$ ) - ( $[0,L - 1]$ 有幾個點不大於 $K$ )。我們可以離線處理，先存下每筆詢問所有需要查詢的資訊，由左向右建對於高度出現次數的 BIT，湊出每筆詢問的答案。
# C. Capoo’s Christmas
###### 出題者：呂爾軒(HanaYukii)
## 題目翻譯
給定計算美麗值的規則，再每拔掉一顆聖誕樹時輸出當下最高的美麗值。
## 解法
本題有多種解法，以下為其一。
維護一個 $set$ 為已經被移除的點，初始丟入 $0,n+1$
維護一個 $multiset$ 為每個連通塊的最大美麗值 初始丟入 $最大值 * n$
接著對於美麗值做一個 $RMQ$ 結構， 查詢區間最大值。
每做一次移除 $X$ 操作會先在 $set$ 中查找出目前連通塊的左右界 $L,R$，接著找出這個範圍內的美麗值 $max$，在 $multiset$ 中將 $(R - L - 1) * RMQ(L + 1, R - 1)$ 移除。
若 $X$ 不為 $R - 1$ 則右邊會切出一塊新的，在 $multiset$ 中加入 $(R - X - 1) * RMQ(X + 1, R - 1)$。
若 $X$ 不為 $L + 1$ 則左邊會切出一塊新的，在 $multiset$ 中加入 $(X - L - 1) * RMQ(L + 1, X - 1)$。
在 $set$ 中加入 $X$，輸出$multiset$中的最大值，即完成一次操作。
每次操作複雜度為 $O(\lg N)$ 總複雜度為 $O(M\lg N)$
# D. Dope Design
###### 出題者：呂爾軒(HanaYukii)
## 題目翻譯
給定定義好的山的形狀，問限定寬度及高度下，有幾種合法的山。
## 解法
定義 dp[目前位置] [結尾高度] = 非遞減序列數量
此表可由下列式子建出
$$
\begin{equation}
dp[i][j] =
\left\{
\begin{array}{**lr**}
1, \texttt{ when }i = 1 \texttt{ or } j = 1\\
dp[i][j - 1] + dp[i - 1][j]
\end{array}
\right.
\end{equation}
$$
接著枚舉中間點位置及高度，設位置為 $x$ 高度為 $y$，則組合數為後方合法方法數 * 前方合法方法數
\begin{equation} \sum_{k=1}^{y-1}dp[x-1][k] * \sum_{k=1}^{y-1}dp[n-x][k] \end{equation}
固定位置，由小至大枚舉的高度即可在計算和時重複利用先前的和。
注意好 $mod$ 的處理
總複雜度為 $O(NM)$
# E. Eerie Echo

###### 出題者：劉姿利(tracyliu.cs06)

## 題目翻譯
在定義好的 $♪(x)$ 上找循環。
$♪(x)$ 是將 $x$ 內的數字重新排序，由大到小減去由小到大。

## 解法
因為黑洞數的性質 $♪(x)$ 會收斂得非常快，直接跑 $♪(x)$ 的值並記下時間戳記（假設青蛙一秒跳一次），當遇到重複的話就拿當前的時間減去記下的時間輸出就好。

# F. Flawlessly Fortified
###### 出題者：楊政道(marmot0814)
## 題目翻譯
給一個$N\times N$ 無向Grid, 有點權跟邊權, 問 s 是 (1,1),t 是 (n,n) 的 minimum st-cut
## 解法
### 1. minimum cut = maximum flow (TLE)
每個點拆成in-node跟out-node, 兩個node之間放點權, 其餘邊權接好(out-node -> in-node), 取最大流就是最小割。
(對應到第一張圖的例子)
#### 複雜度
$N = 1000, V = 2N^2, E \approx 8V$
$O(V^2E) \approx 64\times10^{18}$(worst case不好構, 高估很多, 實測約比標程式慢2.5倍)
### 2. 平面圖minimum st-cut = 轉換圖中的最短路徑
綠色邊邊權為0, 紅色邊邊權為切到原圖對應邊的邊權, 彩色點權對應到原圖的點權, 灰色點權為0。作s->t的帶邊權帶點權的Dijkstra即為所求。(灰色邊並不在所建的圖之中)
(對應到第一張圖的例子)
#### 時間複雜度
$N=1000, V=2N^2, E \approx 4V$
$O((V+E)\log V) \approx 2\times 10^8$
# G. Gap Gambolling
###### 出題者：呂爾軒(HanaYukii)
## 題目翻譯
池塘中間有N個石頭編號1到N, 第N個石頭後面就是陸地, 每顆石頭一開始都各站一隻青蛙, 每個石頭上都有一個數值, 代表站在該石頭上的青蛙想要跳躍時會向右跳的距離, 詢問跳$K$步之後有多少隻青蛙到達岸上。
## 解法
可以將這個數列建成一棵樹, 每個石頭和陸地都是一個節點, 若第$i$個石頭的值是$a_i$, 則從節點$i + a_i$建一條有向邊到節點$i$, 若$i + a_i > N$則從陸地接出去。
從陸地的節點開始做bfs, 做到深度為K時停下來, 計算走過多少點即為答案。
### 時間複雜度
建圖花費$O(N)$, 每個石頭會連出去一條邊。
bfs花費$O(N + M) = O(2 \times N)$, 因此總時間複雜度為O(N)。
# H. Hard to Handle
###### 出題者：黃柏豪(bohau)
## 題目翻譯
數列中詢問有沒有偶數個(不包括0)偶數值的數, 並按照題目要求輸出對應的答案。
## 解法
分case討論,
1) 若整個數列只有出現1個偶數或是一個偶數都沒有, 輸出NO。
2) 若整個數列恰出現偶數個偶數, 則輸出YES並把所有偶數小到大排序輸出。
3) 剩下情況為偶數出現奇數次並且偶數個數$\ge 3$, 輸出OuO和一個最小的偶數。