109-1校內賽題解
===

###### tags: `OI`
## Overview & 目錄

> 這次我出了 ADE 三題，這三題對經過訓練的競賽選手應該都不算太難(因為更難的題目都被拔掉了QQ)，但是做不出來沒有關係
> 如果有心想拼演算法競賽但是不知道如何開始，或者是對今天的題目有任何問題，歡迎找我或者是今天有來的任何一位學長，我們很樂意回答問題 😃 (聯絡方式可能要請你們私下來QQ)
> 如果想了解基本的演算法知識的話可以參考[這份教材](https://drive.google.com/file/d/1Rf4hvGYhxx28DNPR7Hc7unYrhKY6kYla/view?usp=drivesdk)
> 順帶一提，如果有人想知道題目的靈感來源也可以找我XD
> [name=HNO2]

<table style="text-align: center; font-weight: bold;">
<tr>
<td><a href="#A-回文串接">A</a></td>
<td><a href="#B-公司">B</a></td>
<td><a href="#C-冪次問題">C</a></td>
</tr>
<tr>
<td><a href="#D-社交距離">D</a></td>
<td><a href="#E-基地台">E</a></td>
<td><a href="#F-偽Mex">F</a></td>
</tr>
</table>

## A. 回文串接
###### 出題者: 郭軒語(HNO2)
這題的主要目的是考程式基本語法。這題需要用到if敘述、for敘述與基本的字串處理，如果對語法不熟悉的可以複習一下。
在以下題解中為了敘述方便，把 $s,t$ 兩個字串連接在一起寫成 $s+t$ 。
### Subtask 1
$n = 1$ 時只有一種組合 $(1,1)$，也就是$s_1$重複兩次。經過簡單的觀察可發現:若$s_1+s_1$是回文，則$s_1$本身必須是回文，所以只需檢查$s_1$是否為回文，是則答案為$1$，否則答案為$0$。
### Subtask 2
所有字串的長度都是 $1$ ，也就是只有一個英文字母。由於不同的字母連接在一起必定不是回文，因此我們可以統計每個字母在輸入中出現了幾次。假設一個字母出現了 $cnt$ 次，經由簡單的數學可以知道他對答案的貢獻是 $cnt^2$ 。
需要注意的是字元統計的部分: 注意到每個字元是以 [ASCII code](https://en.m.wikipedia.org/wiki/ASCII) 存在電腦中，而小寫英文字母的範圍為 $97$ 至 $122$ ，統計時記得要算對統計的範圍區間。
### Subtask 3
我們可以用雙層 for 迴圈枚舉所有的 $(i,j)$ 整數對，檢查 $s_i+s_j$ 是否為回文。在這個 Subtask 中由於每個字串長度都相同，如果字串的長度都是 $m$ 的話，那只需要再用一個for迴圈檢查 $s_{i,1}=s_{j,m}$、$s_{i,2}=s_{j,m-1}$、…、$s_{i,m}=s_{j,1}$ 即可。
### Subtask 4
同樣是枚舉所有的$(i,j)$整數對，只是這次不保證字串的長度都相同。
比較好的實作方式是，首先先想辦法把兩個字串連接在一起後，再寫一個函式檢查這個字串是否為回文。
怎麼把兩個字串連結在一起?如果是用 C++ 的 string ， `s` 和 `t`兩個字串連結在一起可以直接寫成 `s+t` ，而如果是用字元陣列的話可以使用內建的 `strcat` 函式。
[範例程式碼](http://codepad.org/lgXjyUmc)

## B. 公司
###### 出題者: 沈立程(AceIn)
### Subtask 1
所有人的直屬上司都是編號為 $1$ 的老闆。編號 $2$ 至 $n$ 的下屬只有自己，用一個陣列記錄每個人的狀態即可。另外記錄當前處於上班狀態的總人數，即為編號 $1$ 的答案。
### Subtask 2
編號 $i$ 的直屬上司是編號 $i-1$ ，畫成圖示可得知編號 $i$ 的所有下屬包含編號 $i$ 至 $n$ 。 使用陣列記錄狀態，遇到第二種操作時使用 for 迴圈計算數量後輸出。時間複雜度 $O(nq)$。
### Subtask 3
需要樹狀資料結構的先備知識。建構出員工間階級關係的樹，查詢時DFS遍歷以該點為根節點的子樹。時間複雜度 $O(nq)$。
### Subtask 4
需要線段樹或樹狀樹組等資料結構的先備知識。延續Subtask 2，編號 $i$ 的所有下屬包含編號 $i$ 至 $n$ ，但是這次的人數不允許每次用迴圈計數。使用線段樹等資料結構可以每次在 $O(\lg$ $n)$ 時間做到單點的修改與區間和的查詢。時間複雜度 $O($ $(n+q)$ $\lg$ $n$ $)$ 。
### Subtask 5
建構出樹後，需要快速求出子樹中所有點的狀態值的和。從編號 $1$ 開始DFS遍歷整棵樹並記錄順序，可以觀察到每個子樹可以對應到一個區間。DFS時可以記錄每個子樹對應到的區間的起點與終點。上述的做法稱為「樹壓平」。如此一來，便能如同Subtask 4使用資料結構解決區間和問題了。時間複雜度 $O($ $(n+q)$ $\lg$ $n$ $)$ 。
[範例程式碼](http://codepad.org/AvsD2S3O)

## C. 冪次問題
###### 出題者: 陳亮瑜(creepy_crap)
### Subtask 1
因為 $1$ 的任何冪次都是 $1$ ，所以由 $1$ 的所有冪次組合之和中第 $k$ 大的值，勢必就是任意$k$個$1$的冪次加總起來，也就是 $1 \cdot k = k$ 。

### Subtask 2
排除 $n = 1$ 的case後，經過簡單的觀察，可以發現每當 $k$ 可以寫成 $2^m$ ， $m$ 為非負整數時，答案會剛好是 $n^m$ ，所以首先要先把 $k$ 取以 $2$ 為底的 $\log$ ，然後再把 $n$ 自乘 $m$ 次，記得每乘一次就模 $10^9 + 7$ ，才不會overflow。

### Subtask 3
在 $k \leq 20$ 的情況下，我們可以假設僅由 $n^0$ , $n^1$ , $n^2$ , $n^3$ , $n^4$ 這 $5$ 個數字的組合就能得到 $k \leq 31$ 的所有答案，因為這 $5$ 個數字共有 $2^5 = 32$ 種組合，減掉 $5$ 個數字都沒選到的情況，就有 $31$ 個可能的值。得到這 $31$ 個值後，把他們sort過再查詢第 $k$ 個數字就好囉。

### Subtask 4
觀察了那麼久，應該也發現Hint裡面的秘密了吧(?)在 $n = 10$ 時，答案就是把 $k$ 轉成二進位。為甚麼是這樣呢?本題可以理解成在 $n$ 進位制底下，只由0和1組成的數中第 $k$ 大的數，用十進位制表示是多少?講成這樣就很容易了吧(?)只需要將 $k$ 轉成二進位，然後就是基本的 $n$ 進位轉十進位了。複雜度 $O(Q \cdot \lg(k))$
[範例程式碼](http://codepad.org/PbCkM9l8)

## D. 社交距離
###### 出題者: 郭軒語(HNO2)
### Subtask 1~3
首先，我們可以觀察到以下事實:
* 對於每個人來說，他需不需要戴口罩只由他相鄰的人決定: 如果他距離他相鄰的人距離都超過 $a$ ，則他不需要戴口罩，否則他需要戴口罩。原因很簡單:相鄰的人是距離他最近的人，其他人的距離只會更遠。
* 對於每個距離 $d_i$ 而言，其中一個最佳解是將其改為 $d_i$ 或 $a$ 其中之一。 如果一個人不戴口罩，而他距離他相鄰的人未滿 $a$ ，則需要拉到距離為 $a$ ，否則不需要調整;如果一個人需要戴口罩，則他與周遭人的距離多少都沒有關係。

以上三個 Subtask 的目的都是為了引導觀察到以上事實，只要理解以上事實便能得到這三個 Subtask 的分數。注意 Subtask 1 的答案可能會超過 `int` 的儲存範圍，需要使用 `long long` 儲存答案。

### Subtask 4
由於人數不多 ($n \leq 16$) ，我們可以枚舉在終止狀態時，每個位置的人是否要戴口罩。我們仿照題目中的表示法，寫成一個口罩序列 $[h'_{1},\cdots,h'_{n}]$ ，稱之為一個**狀態**。對於每個狀態，要檢查以下事項：
* 如果對於某個人 $i$ ， $h'_{i}=0,h_i=1$ ，則需要跳過這個狀態。
* 如果對於某個人 $i$ ， $c_{1,i}=-1$ ，但是 $h_i \neq h'_{i}$ ，則需要跳過這個狀態。
* 如果一個人 $h'_{i}=0$，則他距離他相鄰的人都要距離至少 $a$ 。如果 $c_{2,{i-1}}=-1,d_{i-1}<a$ 或 $c_{2,{i}} = -1,d_{i}<a$ ，則需要跳過這個狀態。

找出所有沒被跳過的狀態後，找出這些狀態所需花費的最小值。如果全部狀態都被跳過則無解。

### Subtask 5
從這個 Subtask 開始，我們需要用到DP (Dynamic Programming,動態規劃) 的概念，沒有概念的人可以看一下我在Overview 給的教材的內容。
根據前面提到的兩項觀察，一個人需不需要戴口罩只由他前後的人決定，且如果距離要加長，一定會加長到距離為 $a$ 為止。透過以上我們可以列出以下DP狀態與轉移式：
* 狀態： 令 $dp_{i,0}$ 代表要讓前 $i$ 個人符合防疫新生活運動，且第 $i$ 個人**不戴口罩**時最少需要時間。同樣的，令 $dp_{i,1}$ 代表要讓前 $i$ 個人符合防疫新生活運動，且第 $i$ 個人**戴口罩**時最少需要時間。如果無法做到則設為 $+ \infty$ ；實作上可以將其設為一個很大的整數如 $10^{18}$ 。
* 轉移：

\begin{cases}
dp_{i,0}=\min(dp_{{i-1},0},dp_{{i-1},1})+\max(0,a-d_{i-1})\cdot c_{2,{i-1}} & \text{if} \space h_i=0 \\
dp_{i,0}=\infty & \text{if} \space h_i=1 \\
dp_{i,1}=\min(dp_{{i-1},0}+c_{1,i}+\max(0,a-d_{i-1})\cdot c_{2,{i-1}},dp_{{i-1},1}+c_{1,i}) & \text{if} \space h_i=0 \\
dp_{i,1}=\min(dp_{i-1,0}+\max(0,a-d_{i-1})\cdot c_{2,{i-1}},dp_{i-1,1}) & \text{if} \space h_i=0 \\
\end{cases}

可以自己想想看以上轉移式每一條是怎麼來的(?)

### Subtask 6
和 Subtask 5 幾乎一樣的做法，只是這次有 $c_{1,i}=-1$ 與 $c_{2,i}=-1$ 的情形。這裡提供一個實作方便的做法：將那些等於 $-1$ 的值上面一樣設為一個很大的整數，這樣就可以確保不會有不合法的轉移。
然而這個值的選擇要十分小心：太小會因為答案被這個值限制而無法正確轉移到答案；太大會在運算過程中 overflow 而出現奇怪的值。稍微估算一下可以知道這個值大概取在 $10^{14}$ 左右是最理想的。
[範例程式碼](http://codepad.org/ZPqwcqlw)

## E. 基地台
###### 出題者: 郭軒語(HNO2)
這題整題都需要用到圖論的先備知識，不熟悉的人同樣可以看一下我在Overview 給的教材的內容。
### Subtask 1
由於 $b_i=a_i+1$ ，我們可以依照基地台依照 $a_i$ 分類。
假設 $a_i=x$ 的有 $cnt_x$ 個，我們令 $cnt'_x=cnt_x+cnt_{x+1}+\cdot$ ，則對於每個 $a_i=x$ 的基地台答案就是 $cnt'_{x+1}+1$ 。這是因為，這座基地台會放出頻率 $x+1$ 的電磁波，會自動啟動 $a_i=x+1$ 的基地台，而 $a_i=x+1$ 的又會自動啟動 $a_i=x+2$ 的...。由於存在一座基地台可以啟動全部，所以中間不會斷掉，直到最後。
### Subtask 2
和上一個 Subtask 幾乎一樣的做法，只是這次中間可能斷開。同樣令 $a_i=x$ 的有$cnt_x$個，我們可以同樣算出 $cnt'$:
$cnt'_i=$ \begin{cases}
0 & \quad \text{if } cnt_i=0\\
cnt_i+cnt'_{i+1} & \quad \text{if } cnt_i \neq 0
\end{cases}

之後就可以輕易的算出所有答案了。

### Subtask 3
考慮圖論模型: 我們對於每台基地台建立一個節點，對於任兩座基地台 $i,j$ 如果 $b_i=a_j$ 則建一條有向邊。
之後只要對每個節點都DFS一次，查看能走到幾個節點即可。

### Subtask 4
這個 Subtask 可以分情況討論，每個成立的理由可以自己想想看:
* 如果不存在 $a_i \neq b_i$，則所有答案都是 $1$。
* 如果$(a_i,b_i)=(1,2),(2,1)$的pair都存在，則所有答案都是 $n$。
* 如果只存在 $(a_i,b_i)=(1,2)$ 的整數對 ((2,1)情況也類似),令$(a_i,b_i)=(1,2),(1,1),(2,2)$ 的分別有 $x,y,z$ 個，則這三個的答案分別是 $z+1,x+y+z,z$。

### Subtask 5
在 Subtask 3 中，我們把每個基地台當節點，顏色當邊; 這次反過來用顏色當點，基地台當邊。
你可能已經注意到人工啟動和自動啟動的差異只在是否有接受頻率，所以是否可以對每個 $(a_i,b_i)$ 建有向邊，之後對每個節點DFS，之後只要輸出 $b_i$ DFS後的答案即可?
很可惜這個想法有一個漏洞: 如果在 $b_i$ DFS後不會再經過這條邊，則算出來的答案會漏算自己，和正確答案差 $1$ ! 因此在 $b_i$ DFS後，如果不會走過 $a_i$ ，則答案要加1。
Note: 這題中答案要加一的邊正式的圖論術語來說是"不位於任何一個強聯通分量的邊"。
[範例程式碼](http://codepad.org/yC0yNwFU)

## F. 偽Mex
###### 出題者: 沈立程(AceIn)
### Subtask 1
沒有人在$a$裡面，答案就是$k$。
### Subtask 2
開一個陣列記錄每個數是否在$a$裡，使用while迴圈從$1$開始跑，記錄一個$cnt$代表跑到目前為止不在$a$裡的數量，$cnt=a$ 時便找到答案。時間複雜度 $O($ $q(n+k)$ $)$ 。
### Subtask 3
先將$a$排序，每次從$a_1$開始跑，檢查$a_i-i$(即目前在第幾小)和$k$的關係可以找出答案。可以使用$O(n^2)$的排序法，時間複雜度 $O(n^2+nq)$ 。
### Subtask 4
因為 $a_i$ 和 $k$ 都不超過 $10^5$ ，答案不會超過 $2 \cdot 10^5$ 。我們可以使用類似爬行法的方式，先將 $a$ 用 $O(n \lg n)$ 的方式排序後，算出每個 $k$ 對應的答案。之後詢問時只要以 $O(1)$ 回答即可。
### Subtask 5
對答案二分搜，假設現在猜的答案是 $tmp$ ，計算不超過 $tmp$ 的有幾個不在序列 $a$又需要一次二分搜。時間複雜度 $O(n\lg n+q \lg^2 n)$。
### Subtask 6
#### Solution 1
將$a$排序後可以得出$a$中的數字會排在第幾小的地方，存在新的陣列中，詢問時便可以對這個陣列二分搜，再加上差值得出答案。時間複雜度$O($ $(n+q)\lg n$ $)$。
#### Solution 2
將詢問存起來後排序，對$a$和詢問陣列兩邊爬行。時間複雜度$O(n\lg n+q\lg q)$。
[範例程式碼](http://codepad.org/PP8TpEax)
>其實這題原本我寫了有關念課文的題敘，但是太爛所以拿掉了xD