NCTU PCCA Winter Camp Contest 2020 - 題解

如果你想在比賽結束後解題，請在 DOMjudge 界面的右上角 contest 選擇 "PCCAWinter2020p"(NCTU PCCA Winter Camp Contest 2020 - Practice) 再上傳，否則只會收到各種 TOO-LATE

目錄

A	B	C	D
E	F	G	H

A. Ascend the Alps

出題者：黃克崴(toxicpie)

題目翻譯

給平面上一條折線，對於每個頂點

$P$，請求出

$y$ 座標最高的頂點

$Q$ 使得線段

$\overline{PQ}$ 除了端點外都嚴格在折線上方(即

$P$ 看得到

$Q$)。(好像沒翻譯到)

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 }$。
2. $P$ 看不到
   $Q_1^{\prime }$，代表存在某個點
   $X$ 在
   $Q_1^{\prime }$ 和
   $P$ 之間使得
   $\overrightarrow{P{Q}_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$ 為每個連通塊的最大美麗值 初始丟入

$\mathrm{最}\mathrm{大}\mathrm{值}\ast n$
接著對於美麗值做一個

$RMQ$ 結構， 查詢區間最大值。
每做一次移除

$X$ 操作會先在

$set$ 中查找出目前連通塊的左右界

$L,R$，接著找出這個範圍內的美麗值

$max$，在

$multiset$ 中將

$(R-L-1)\ast RMQ(L+1,R-1)$ 移除。
若

$X$ 不為

$R-1$ 則右邊會切出一塊新的，在

$multiset$ 中加入

$(R-X-1)\ast RMQ(X+1,R-1)$。
若

$X$ 不為

$L+1$ 則左邊會切出一塊新的，在

$multiset$ 中加入

$(X-L-1)\ast RMQ(L+1,X-1)$。
在

$set$ 中加入

$X$，輸出

$multiset$中的最大值，即完成一次操作。
每次操作複雜度為

$O(\lg N)$ 總複雜度為

$O(M\lg N)$

D. Dope Design

出題者：呂爾軒(HanaYukii)

題目翻譯

給定定義好的山的形狀，問限定寬度及高度下，有幾種合法的山。

解法

定義 dp[目前位置] [結尾高度] = 非遞減序列數量
此表可由下列式子建出

$$dp[i][j]=\{\begin{array}{l}1,\mathtt{\text{ when }}i=1\mathtt{\text{ or }}j=1\\ dp[i][j-1]+dp[i-1][j]\end{array}$$
接著枚舉中間點位置及高度，設位置為

$x$ 高度為

$y$，則組合數為後方合法方法數 * 前方合法方法數

$$\sum _{k=1}^{y-1}dp[x-1][k]\ast \sum _{k=1}^{y-1}dp[n-x][k]$$
固定位置，由小至大枚舉的高度即可在計算和時重複利用先前的和。
注意好

$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^{2}E)\approx 64\times {10}^{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和一個最小的偶數。