Day 1 上機詳解
===

###### tags:`IONCAMP2019`

[Password Generator](https://pc2.tfcis.org/dev/index.php/problem/view/83/)
----
範圍：基本技巧

[辛朵莉的盤子](https://pc2.tfcis.org/dev/index.php/problem/view/50/)
----
範圍：基本技巧
用`vector`維護
- `clear a`: `vector.push_back(a)`
- `break`: `vector.pop_back()`
- `query b`: `print vector[b-1]`（盤子最底下為1號盤子，index要扣1）

時間複雜度：$O(n)$

[蘿莉獵人詹皇](https://pc2.tfcis.org/dev/index.php/problem/view/56)
----
範圍：基本技巧

這題的作法有個特別的名子： **Two Pointer (雙指針)**

大致作法如下：

(1) 維護兩個位置 $i, j$ (左指針，右指針) 使得每個在區間 $[i, j]$ 的元素在裡面都是獨特的。

(2) 初始化 $i = 1, j = 1$ (假設陣列從 1 開始)。

(3) 每次將 $j$ **右移一格**，然後**更新** $i$ 使得 $i, j$ 仍然合乎定義。

(4) 更新之後，若 $[i, j]$ 的大小 $\geq K$ ，則他是一個漂亮區間。

(5) 若發現一個漂亮區間，將漂亮區間中的每個位置由**右往左勾選** (可以開一個 bool 陣列)。

(6) 做完之後，被勾選的位置即為**漂亮位置**，可以將他們加入**vector**後進行輸出需要的操作。

### 註1 : (3) 如何更新？

紀錄一個陣列 **cnt (counter)** ，代表每個元素在當前區間 $[i, j]$ 的**出現次數**。

如果 $j$ 在右移之後，若 $cnt[ a_j ] > 1$ ，就不斷右移左指針。

(由於每次右移左指針都會使其中一個元素離開區間，每次右移 i 時將 cnt[ a_i ] 減 1 。)

不斷右移左指針直到 $cnt[a_j] = 1$ ，則 $[i, j]$ 回到合乎定義的狀態。

### 註2 : (5) 為何由右往左？

這樣如果一個位置被多個漂亮區間覆蓋到，那他只會被勾選到 1 次。

##

[搭電梯](https://pc2.tfcis.org/dev/index.php/problem/view/67/)
----
範圍：貪心

簡單觀察後，可以發現，盡量把高樓層的人一起運送
假設有3個人要去5樓，1個人要4樓，電梯一趟可以3個人，把要去5樓的人聚集在一起可以一次運完，但如果先塞了一個要去4樓的人，那5樓就得去兩趟
所以大致做法就是，把要去的樓層排序後，從高樓層開始分組
地下室的部分，另外做一次即可
有幾個細節要注意
:::warning
* 地下1樓跟1樓只差一樓，要記得扣1
* 電梯載完人的最後一趟不用回去一樓
:::

題外話
:::info
這題改變一下可能可以變得很難，但我目前也沒想法
當要搭電梯的人的出發點並不是全部在一樓，而是分散在不同樓層，跟真實情況一樣，要怎麼做呢?
我也沒有解法，大家可以想想看XD
:::

[GY採香蕉](https://pc2.tfcis.org/dev/index.php/problem/view/65/)
----
範圍：基本技巧

首先需要發現一個簡單的性質：熟度接近的香蕉會放在同一個袋中比較好。

比方說，如果排序後的熟度由小到大為 $a_1 ... a_N$ ，

則分袋方法一定可以長的像這樣：(每個袋子中的香蕉，在本來排序後的位置都是**連續的**)

$[ a_1 ... ] [ ... ] [ ... ] [ ... a_N ]$

既然如此，那可以枚舉**包含最大熟度香蕉的袋子，包含了幾根香蕉**，再往下遞迴解開 $K-1$ 個袋子的子問題。

遞迴函數大概長得像這樣：

int recur( int i, int k ) //回傳前 $i$ 根香蕉分成 $k$ 袋的最小總熟度，特判 k=1 的情況。
{
//設回傳值rtn 為 inf
//枚舉最大熟度的那一袋 ( 第 $k$ 袋 ) 包含 j = 1, 2, 3... 根香蕉
//往下遞迴, 更新 rtn = min(rtn, A[i] * j + recur( i-j-1, k-1 )
//回傳rtn
}

在遞迴過程中，由於某些子問題可能會被多個大問題看到，所以可能需要**記憶化 (memoize)**，將每次遞迴的答案存在一個陣列中。

int recur( int i, int k )
{
//若 vis[i][k] == true ，直接回傳 ans[i][k]
//否則勾選 vis[i][k] = true
//...其餘同上，但回傳之前先將答案存在 **ans[i][k]**
}

如果已經會**動態規劃**的同學，其實可以依據剛剛的遞迴式，將問題簡單地解開。

[你不是這個時間軸的人吧](https://pc2.tfcis.org/dev/index.php/problem/view/90)
----
範圍：圖論(最短路徑)
最短路徑裸題
節點：地圖上的每個點，共$R \times C$個節點
邊：上下左右
邊權：|和相鄰節點時間係數差|
因為邊權都是正的，講義翻開 Dijkstra 抄上去就可以AC了

[工作病毒](https://pc2.tfcis.org/dev/index.php/problem/view/96/)
----
範圍：字串

把所有等於後綴的前綴都找出來之後
可以發現對於任意一個長度為 L 的前後綴
如果可以在字串中間找到他
那麼所有長度小於 L 的前後綴也都能被找到
所以可以用二分搜和線性的字串匹配找到解

另外一種解法不用二分搜
只需要普通的線性字串匹配
大家有興趣的話可以想想看

[獨行玩家](https://pc2.tfcis.org/dev/index.php/problem/view/84/)
----
範圍：進階資料結構

可以用線段樹維護最小值與最大值的位置，詢問時直接用線段樹查詢即可。
時間複雜度$O((N+Q)\log~N)$。

但注意詢問的區間長度都一樣，表示詢問最多只有$N$種，而$N$最大只到5000，那只要暴力算出答案，並且將算過的詢問答案紀錄下來，在之後詢問問過的問題時，直接查詢紀錄的結果就好。
時間複雜度$O(N^2+Q)$。

[維茲的神祕藥水](https://pc2.tfcis.org/dev/index.php/problem/view/53/)
----
範圍：進階字串
超裸的Suffix Array(後綴數組)題
直接用Suffix Array套這題的字串，然後輸出對應的排名即可。
後綴數組在進階字串課程中會教。不過這題直接暴力排序也可以爬個60分進來。

[Parenheses](https://pc2.tfcis.org/dev/index.php/problem/view/98/)
----
範圍：貪心

題意：出題者懶得放敘述，所以出裸題讓題目=題意

合法的括弧匹配一定是偶數個字元，所以需要砍字元的情況只有字串長度是奇數

假設字串長度偶數個：
我們可以算算看差幾個 `(` 跟 `)` ，然後由左到右優先填入 `(` 再填入 `)`，證明來自 Greedy

假設字串長度奇數個：
如果你會上述 Greedy ，窮舉刪除位置就有 50% Credit
我們考慮三種情況
1. 刪除一個 `?`
假設全部的字元都是 `?` ，那答案明顯 `Eevee`
否則存在有一個 `?` 相鄰 `(` 或`)`，可以改刪相鄰的半括弧也不影響答案，所以除非全部字元都是 `?` ，否則不用刪到`?`
2. 刪除一個 `)`
如果刪除第一個都不行，一定是 `Pikachu`
3. 刪除一個 `(`
如果刪除最後一個都不行，一定是 `Pikachu`

對 2. 3. 分別寫一個測試，全部問號則特判，就能過了

實作難度偏簡單，算是吃思想的題目