# NHSPC 決賽 2021~2022
## 2022
[題目](https://nhspc2022.twpca.org/release/problems/problems.pdf)
### B. 自行車歸位 (bicycle)
有$n$個腳踏車，$m$個空位，給定一維座標，問把所有腳踏車都移到空位的最小總距離。
:::spoiler 解法:
從範例開始觀察，可以發現當$m=n$時，照順序由小到大依序歸還必是一組最佳解。也不難推出，對於所有情形，必有一組最佳解為 腳踏車座標越大，歸還座標越大。

為了簡化問題，我們將所有的$a<b<x<y$ $a\rightarrow x, b\rightarrow y$換為$a\rightarrow y, b\rightarrow x$，即所有的連線皆完全包含或不相交。
一輛腳踏車 b 只會有兩個可能被歸還的地方：
$l_b$:在$b$左邊，滿足$[l_b, b]$間腳踏車與空格數量相等，座標最大的空位
$r_b$:在$b$右邊，滿足$[b, r_b]$間腳踏車與空格數量相等，座標最小的空位
可利用stack在線性時間得出所有可能的連線，然後再做一次dp就好了。
:::
### C. 卡牌 (card)
每一回合從未選卡牌序列的最左邊或最右邊選一張卡片。隨著每回合減少了一張卡牌，剩餘卡牌的得分就會各加上其最初得分的十分之一，也就是第$k$回合結束時還未選的卡牌的得分
會為最初得分的$1+0.1k$倍。在最佳的選卡策略時，給定的卡牌序列最多可以獲得多少總得分？
保證初始分數皆為10的倍數。
* $n\leq 1000$
:::spoiler 解法:
定義dp[i][j]為，序列剩下[i,j]時，目前可獲得的最大分數，有可能從dp[i][j+1] or dp[i-1][j]轉移。

for(int i=0;i<n;i++){
		for(int j=n-1;j>=i;j--){
			if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]+v[i-1]*(10+n-1-j+i-1)/10);
			if(j<n-1) dp[i][j]=max(dp[i][j],dp[i][j+1]+v[j+1]*(10+n-1-j-1+i)/10);
		}
	}

最後答案即為

for(int i=0;i<n;i++) ans=max(ans,dp[i][i]+v[i]*(10+n-1)/10);

:::
### D. 文字編輯器 (editor)
有以下規則:
• 單獨一個$x$是一個合法表達式。
• 如果$e$是合法表達式，則$|e|$也是合法表達式。例如:$x$是合法表達式，所以$|x|$也是合法表
達式。
• 如果$e$是合法表達式，則$[e]$也是合法表達式。例如：$x$是合法表達式，所以$[x]$也是合法表
達式。
• 如果$e1$和$e2$是合法表達式，則$e1+e2$也是合法表達式。例如：$|x|$和$[x]$是合法表達式，所以
$|x|+[x]$也是合法表達式。
現給一個只由"$x$"、"$|$"、"$+$"組成的字串，要把恰一個"$|$"改成"$+$"，並把剩下的"$|$"都改成"$[$"或"$]$"。
:::spoiler 解法:
先觀察到一件事:"$[$"和"$]$"必在"$x$"、"$+$"之間，連在一起的一定都同方向，"$x$"左邊必為左括號，右邊必為右括號。
先找$+$可能放的區間(必在兩個"$x$"之間)，窮舉放的位置，如果左邊的和($[$為1，$]$為-1)+右邊的和=$0$，就是合法的。
:::
### E. 齒輪組 (gears)
齒輪彼此接合或帶動，問最後一個齒輪的方向和轉速。
:::spoiler 解法:
直接線性做就好。
:::
### F. 百萬刮刮樂 (scratchcard)
有$n$張卡片，每張卡片$i$上面，由上至下依序有四筆數字$W_i, A_i, B_i, C_i$，其中$W_i\in \{ 1e6, 2e6, 3e6\}$。
抽出兩張相異卡片$x$和$y$，如果這兩張卡片上面的數字滿足以下條件，那麼中獎金額就是$K=W_x+W_y$，否則就沒有中獎。
條件:兩張卡片的$A, B, C$值相加皆須大於等於$K$
問有可能的$K$有多少種。
* $n\leq 2e5$
* $A_i, B_i, C_i\leq 6\times 10^6$
:::spoiler 解法:
$K$只有可能是$2e6, 3e6, 4e6, 5e6, 6e6$，所以題目變成:給定$K$，是否存在兩張刮刮樂滿足條件
若只有一個條件(如$A$)可以先排序後用簡單的用雙指標算對於每一個$i$，有那些$j>i$滿足$A_i+A_j\geq K$。
現在要再加入兩個條件，可以想成維護一個資料結構，檢查完$i$要檢查$i+1$時，把可以和$i$配但不能和$i+1$配的$j$拿掉。

---
現在的問題是:要如何建立一個資料結構可以查詢是否有$j$滿足$B_j\geq K-B_i$ 且$C_j\geq K-C_i$，並且可以支援刪除。
**對B的值域開線段樹**，存C的值，查詢[$K-B_i, B_{max}$]中
C的最大值是否大於等於$K-C_i$。
另外要注意因為$B$有可能重複，每個葉節點裡面要再放個multiset儲存該$B$值對應的$C$值。
:::
### G. 算樹 (tree)
給一棵樹的每個節點的度數，求可能的[Prüfer序列](https://zh.wikipedia.org/zh-tw/%E6%99%AE%E5%90%95%E5%BC%97%E5%BA%8F%E5%88%97)中，字典序第$k$小的。
:::spoiler 解法:
先觀察(或通靈)出一個性質:一個點在序列中出現的次數恰為 該點的度數$-1$ ，且任何序列都可以構造出一棵樹。
因此用排列組合算出一個序列的排列數，然後再依次算第一位、第二位該放哪個數字。往下一個位數做的時候不需要再重新算一次排列數，可以直接由上一個位數轉移。詳細如下:

定義數字$i$在序列中出現$a_i$次
所有的排列數為
$$
K := \frac{(a_1+n_2+\ldots+a_n)!}{a_1! a_2! \ldots a_n!}
$$
以$i$為開頭的序列個數為:
$$
K_i := \frac{(a_1+\ldots+a_n -1)!}{a_1! \ldots (a_i-1)! \ldots a_n!} = K\frac{a_i}{a_1+\ldots+a_n}
$$
:::
### I. 聖誕燈飾 (xmas)
有一組$n$顆$m$色燈泡的燈飾。這些燈泡排成一列，由左至右編號為$1, 2\cdots n$。燈泡的顏色是可變的，編號為$1, 2\cdots m$。若一顆燈泡的顏色為$i$，其中$i\leq m$，則改變顏色會變為$i+1$；若一顆燈泡的顏色為$m$，則改變顏色會變回$1$。
每顆燈泡下皆有一個按鈕可以改變燈飾整體的顏色，按下燈泡$k$的按鈕，會一齊改變燈泡$k, 2k, 3k\cdots$的顏色。例按下燈泡 2的按鈕，只能使編號為偶數的燈泡變色。已知初始 n 顆燈泡的顏色分別為$a_1, a_2\cdots a_n$，小千打算按下$\zeta _i$次燈泡$i$的按鈕，使得最後的顏色變成 $b_1, b_2 \cdots b_n$，請幫她找出滿足條件的$\zeta _1, \zeta _2\cdots \zeta _n$。若有多組滿足條件，請找出字典序最小的那組；若不存在這樣的方案，請輸出$−1$。
:::spoiler 解法:
先把問題轉換為以下數學式:
$$
\begin{cases}
\begin{aligned}
\zeta _1&\equiv b_1-a_1\\
\zeta _1+\zeta _2&\equiv b_2-a_2\\
\zeta _1+\zeta _3&\equiv b_3-a_3\\
\zeta _1+\zeta _2+\zeta _4&\equiv b_4-a_4\\
\vdots\\
\Sigma _{d|n} \zeta _d&\equiv b_n-a_n
\end{aligned}
\end{cases}
mod(m)
$$
題目要求字典序最小，因此$\zeta _1=b_1-a_1$，那麼$\zeta _2$就可以代入$\zeta _1$求出來，以此類推。
因此作法如下:
對於每個$i$，將第$2i, 3i\cdots$條算式都減掉$\zeta _i$，就能保證走到每一條算式時都只會剩下一項。
:::
## 2021
[題目](https://tioj.ck.tp.edu.tw/pmisc/nhspc110.pdf)
### [A. 髮廊服務優化問題(barbershop)](https://tioj.ck.tp.edu.tw/problems/2251)
給定$n$位客人需要的服務時間，問最小的總等待時間。
* $n\leq 200$
:::spoiler 解法:
排序後greedy地從最大的開始。
:::
### [B. 校園公車 (bus)](https://tioj.ck.tp.edu.tw/problems/2252)
有一條由$n$個線段組成的折線，給一個點$O$，問此點到折線的最短距離。
:::spoiler 解法:
窮舉每一條線段，最後取min。
先用畢氏定理判斷點$O$和線段兩端圍成的三角形是否為鈍角三角形。
若是，則最近的點為線段兩端點之一。
若非，用向量外積算出三角形面積，然後除以線段長度，即為點到線段最短距離。
[向量寫法](https://hackmd.io/@Viecon-342524/HJLBoymz2#%E5%90%91%E9%87%8F)
:::
### [D. 汽車不再繞圈圈(car)](https://tioj.ck.tp.edu.tw/problems/2254)
給一張有邊權的有向圖，管理員有權限值$P$可以將任意條邊權小於等於$P$的邊翻轉方向，使得圖中不存在環。問最小的$P$為何，並輸出一種翻轉方案。
:::spoiler 解法:
對排序後的邊權二分搜答案(因為$P$一定等於某一個邊權)，若要檢查$x$，可以先把所有邊權小於等於$x$的邊都刪掉，檢查剩下的圖是否有環，若剩下的圖沒有環，那麼加任意條可以改變方向的邊，一定有辦法構造出一種方案。就可以找出最小的$P$了。

找出$P$後，如何找出翻轉方案?
對剩下的圖做[拓撲排序](https://hackmd.io/@Viecon-342524/Hk-K-vw8j#%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F)，讓加入的邊符合這個順序。
因為加入符合順序的邊不會改變原本的拓樸順序，而只要所有點都在拓樸排序內，就一定不會有環。
:::
### [F. 挑水果 (fruit)](https://tioj.ck.tp.edu.tw/problems/2256)
有$c$種水果和$c$個城市，在第$i$個城市可以選擇是否要以每顆$S_i$元的價格將**前$i$種水果全部卸貨**，且對於種類$j$，能賣出$r_{i,j}$顆給消費者，另外到達第$i$城市時船上的每顆水果要花費$P_i$元(不論種類)，現給預算$T$，問在哪些城市卸貨能使賣出的水果最多。
:::spoiler 解法:
令`dp[i][j]`為最後一次在城市$i$卸貨，目前銷售量為$j$時所花的最小成本。
dp[這一次卸貨的地方][目前總共的銷售量]=dp[枚舉上一次卸貨的地方][上一次的銷售量]+船上的水果量$\times$這一段的總$P$+這個地方的$S$$\times$這一次的卸貨量

$$
dp[i][j]=\mathop{\min}_{0\leq k<i} (dp[k][j-\sum _{x=k+1} ^i r_{i,x}]+\sum _{x=k+1} ^c n_{x} \times \sum _{x=k+1} ^i P_x+S_i\times \sum _{x=k+1} ^i n_x)
$$

sigma 可以用前綴和處理。然後算答案時記得加上船上剩餘的水果載到終點的運費。
最後答案即為不超過$T$的答案中最大的$j$
:::
### [G. 鳳梨關稅 (pineapple)](https://tioj.ck.tp.edu.tw/problems/2257)
給一個樹，支援兩種操作:
1. 將一條邊的權重從$1$變為$0$
2. 問從根節點到某個節點的權重總和
:::spoiler 解法:
[樹壓平](https://hackmd.io/@Viecon-342524/r1qfzJEm3#%E6%A8%B9%E5%A3%93%E5%B9%B3)後就可以套BIT或線段樹了。
:::
### [I. 鐵路鋪設 (rail)](https://tioj.ck.tp.edu.tw/problems/2259)
有一個$2*L$的矩形，有多少種鋪鐵路的方式?
規則:
每個格子只有一條路線，路線皆須要是環，每條路線至多只有一條是斜的
:::spoiler 解法:
這題有滿多種想法的，這裡提供一種。
假設以$A_L$表示$L$的答案，且定義$A_0=1, A_1=0$。
有$A_{L-1}$種情況可從$L-1$往右延伸一格:

---
那麼有哪些情況不能從$L-1$延伸?
最右邊為這三種情形:

針對第三種情形，方法數就等同於$A_{L-2}$。
針對第一種，可以枚舉倒數第二個環的大小，以下以$L=5$為例。
可以觀察出有$A_{L-3}+A_{L-4}+\cdots +A_0$種
且第二種和第一種一樣多。
把上面全部加起來可以得到:
$$
\begin{aligned}
A_L&=A_{L-1}+A_{L-2}+2(A_{L-3}+A_{L-4}+\cdots +A_{0})\\
&=A_{L-1}+A_{L-3}+A_{L-2}+A_{L-3}+2(A_{L-4}+A_{L-5}+\cdots +A_0)\\
&=A_{L-1}+A_{L-3}+A_{L-1}\\
&=2A_{L-1}+A_{L-3}
\end{aligned}
$$
這個很漂亮的算式。
最後再套進[矩陣快速冪](https://hackmd.io/MGfghW7KQu2MdWTOzM6WcQ?view#%E7%9F%A9%E9%99%A3%E5%BF%AB%E9%80%9F%E5%86%AA)就好了
:::
## 參考
https://nhspc2022.twpca.org/editorial/editorial