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)$ 的值。

計算過程中可能會使用到矩陣以及矩陣快速冪，不熟悉的同學建議可以先在這題練習如何透過矩陣計算線性遞迴函式。

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: 因為希望答案

$\le 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