# 2023 NCPC 校內預賽賽後題解

## A. ICPC Start!

字串處裡，把空白去掉，所有字轉大寫後，找字串中有沒有 `ICPC`

冷知識:

strstr  (GCC 實作 O(n))
比
string.find() (O(n^2) 暴力法) 還要快!

## B. Simplify

區間離散化總和，可以考慮使用 mo's algorithm (莫對算法) 求解。

另外使用兩個 BIT 維護有數字出現的次數與數字間有多少空隙來算出答案。

## C. Sentakushi

簡單的圖論實作題，按題目定義，先用 dfs 找出哪一些點可能是 $s$ 到 $e$ 路徑上的點，標記完後再檢查是否為關鍵點。但標記時需要小心實作 dfs ，要有點類似 dp 的方法做，或是先從 $e,s$ 分別 dfs ，找連通分量的交集等。

## D. Stock

動態規劃。

設 `dp[i][j][k]` 為前 $i$ 個元素洽分 $j$ 等分，以及最後一個元素是否被使用的解，其轉移很直覺，題目要求的答案乘以 可以改成輸出三個`0`，這樣所有資料計算可以在 int 範圍內完成。

## E. Yet Another Recursive Function

可能解法:

- 方便起見假設 $i < j$
- 根據函數定義，我們可以將 $g(j)$ 表示成 $g(i)$ 和 $g(i + 1)$ 的線性組合。
- 也就是找到係數 $a, b$ 使得 $g(j) = a \cdot g(i) + b \cdot g(i + 1)$。
- 算出 $a, b$ 後，我們可以移項得到 $g(i + 1)$ 的值。
- 最後再用類似方法，計算出 $g(0)$ 和 $g(1)$ 的值。

計算過程中可能會使用到矩陣以及矩陣快速冪，不熟悉的同學建議可以先在[這題](https://cses.fi/problemset/task/1722)練習如何透過矩陣計算線性遞迴函式。

## F. Infallibly Crack Perplexing Cryptarithm

暴力模擬，枚舉字母 map 到 ``01+-*()`` 的所有可能，然後按題目的 gramma 檢查是否符合規則即可。 content free 文法可以按定義遞迴檢查即可。也可以實作 CYK 演算法。

## G. Three heads are better than one

經典面試題。本題要求 $O(n^2)$ 的 sliding window 作法。 $O(n^2\log n)$ 會 TLE

## H. Min-Max Distance Game

現在有 $n$ 個有編號的石頭放在一直線上， Alice 與 Bob 輪流拿石頭，直到剩下 $2$ 顆石頭。

Alice 希望最後的石頭距離越遠越好，而 Bob 則相反的希望越近越好，問若兩人都採取最優策略的情況下，最後的石頭距離會是多少。

我們可以考慮稍微修改一下問題，變成 **最後的石頭距離是否** > $t$ (如果是的話 Alice 勝，否則 Bob 勝)，如此一來，可以用二分搜尋法來搜出邊界找出原問題的答案。

對於修改過的問題，我們可以把問題轉成一張圖，如果有兩個石頭 $|x_i-x_j|>t$，那就把點 $i$ 與 點 $j$ 中間連線，那問題就變成給一張圖，兩人分別每回合刪掉一個頂點，問最後遊戲最後是否能剩下一條邊。

對於 Alice: 因為希望答案 $>t$ 所以他要刪掉所有的邊，最佳策略是，刪除所有的 vertice cover。

對於 Bob: 因為希望答案 $\leq t$ ，所以他要盡可能保留邊，所以他會盡可能保留 maximun clique，優先刪除非 maximun clique 上的點。

雖然上兩問題的一般狀況是 NP 的，但由於輸入的圖特殊，所以能 $O(n)$ 求解，故最後能在 $O(n\log \text{max distance})$ 完成。

詳細題解看這裡

英文 : https://www.slideshare.net/irrrrr/icpc-2015-tsukuba-unofficial-commentary
韓文 : https://koosaga.com/202