---
# System prepended metadata

title: 從0走向IOI：高中競賽歷程與趣題分享 部分題目題解

---

# 從0走向IOI：高中競賽歷程與趣題分享 部分題目題解


## 找出局部最小值！
### 題目敘述

給定一個 $N \times N$ 的矩陣，裡面元素為 $1$ ~ $N^2$ 的排列。
每次你可以查詢一個特定位置的數值。
請找出這個陣列中的局部最小值。

局部最小值：周圍四個相鄰格子的數字都比這個格子大。

### 資料範圍

$1 \le N \le 10^6$

### 解法 1
考慮隨機抽樣 $k$ 個位置，若我們抽樣到一個 $\le N$的元素，我們它開始greedy的往周圍最小元素移動，期望$N$步以內可以找到局部最小值。

我們抽一次抽到 $\le N$ 的機率是 $\frac{N}{N^2} = \frac{1}{N}$。因此抽一次抽不到 $\le N$ 的機率為 $1 - \frac{1}{N}$

考慮抽$k$次，抽不到任何 $\le N$ 的機率 $= (1 - \frac{1}{N})^k$。

當 $k = N$，$(1 - \frac{1}{N})^k$ 約等於 $\frac{1}{e} = 0.36...$

當 $k = 10 \times N$，$(1 - \frac{1}{N})^k$ 約等於 $0.00004539992$。此時有極高的機率抽樣到 $\le N$ 的元素 ($1-0.00004539992 = 0.99995460008$)。

總時間複雜度 $O(N)$。

### 解法 2
考慮分治演算。
1. 第一步我們可以先橫著正中間切一刀，找到該橫列的最小值。看看該位置的上面還是下面，哪一個比較小，把小的那一半留下來繼續分治。
2. 接著縱向正中間切一刀，找到該步的最小值，並保留當前看過的最小值所在的那一半。
3. 接著橫向正中間切一刀，找到該部最小值，並並保留當前看過的最小值所在的那一半。
4. 重複步驟2, 3，直到剩下一個元素，即為局部最小值。

可以證明，每次保留的區域內一定存在一個局部最小值。

總時間複雜度 $= O(N + \frac{N}{2} + \frac{N}{4} + ...) = O(N)$

## MCO 2017 Magical Teleporter
給定一個長度為 $N$ 字串的字串 $A$，每個位置的字元可能是 `L`, `R`, `B` 其中一種。
 如果是 `L`，代表在這個位置時，可以往左邊跳。
 如果是 `R`，代表在這個位置時，可以往右邊跳。
 如果是 `B`，代表在這個位置時，可以往左或右其中一邊跳。

再給你一個起點編號 $S$ ，終點編號 $E$ ，試求出存在多少條漢米爾頓路徑從 $S$ 到 $E$ 。

漢米爾頓路徑：每個點恰好經過一次的路徑。

### 資料範圍 
$1 \le N \le 2000$

### 解法
為了方便，先考慮 $S = 1, E = N$ 的 case。
令 $dp(i, j)$ 代表考慮前i個位置，形成$j$個聯通塊的方法數。

接下來考慮 dp 轉移得部分（假設$dp(i - 1, )$都已經計算完了），也就是要如何維護聯通塊的聯通性：
1. $i = 1$
    * $dp(i, 1) \leftarrow 1$, if $A[i] \neq$ `L`.

2. $1 < i < N$
    * 增加一個新的聯通塊（一個右箭頭）: $dp(i, j + 1) \leftarrow dp(i, j + 1) +  dp(i - 1, j)$, if $A[i] =$ `R` or `B`.
    * 加入$S = 1$所在的聯通塊：$dp(i, j) \leftarrow dp(i, j) + dp(i - 1, j)$, if $A[i] =$ `R` or `B`.
    * $S = 1$ 所在聯通塊 $\rightarrow i \rightarrow$ 左邊另一個聯通塊，之後往右： $dp(i, j - 1) \leftarrow dp(i, j - 1) + dp(i - 1, j) * x$, if $A[i] =$ `L` or `B`. 其中 $x$ 是左邊往右邊的聯通塊數量。
    * $i \rightarrow$ 左邊某一個聯通塊，之後往右：$dp(i, j) \leftarrow dp(i, j) + dp(i - 1, j) * x$, if $A[i] =$ `L` or `B`. 其中 $x$ 是左邊往右邊的聯通塊數量。
    * 左邊某一個聯通塊 $\rightarrow i$，之後往右：$dp(i, j) \leftarrow dp(i, j) + dp(i - 1, j) * x$, if $A[i] =$ `R` or `B`. 其中 $x$ 是左邊往右邊的聯通塊數量。

3. $i = N$
    * $dp(i, j) \leftarrow dp(i, j) + dp(i - 1, j)$, if $j = 1$.


對於 $S, E$ 任意的情況，我們需要改為 $dp(i, j, a:0/1, b:0/1)$，代表考慮前i個位置，形成$j$個聯通塊，$(a)$是否遇到了$S$，$(b)$是否遇到了$E$的方法數。

因為是一個 $2D/0D$ 的DP，所以總時間複雜度為$O(N^2)$。

## AI 777 進階版
### 題目敘述
給一個長度為 $N$ 的序列 $A$，和另一個長度為 $M$ 的序列 $B$ 。
現在我們可以將 $A$ 中的部分元素（不超過 $M$ 個），換成 $B$ 中的元素。
求操作過後 $A$ 的最大連續和可以多大。
註：$B$ 中的任意元素可以換到 $A$ 中的任意位置，但 $B$ 中的每個元素只能用一次。


### 資料範圍
* $1 \le N, M \le 10^5$

原題：$108$ 學年度普通型高級中等學校資訊學科能力競賽決賽 模擬賽 - 第五題. AI-777 賺多少 (AI)
原題範圍： $1 \le N \le 10^5, 1 \le M \le 100$
原題做法與複雜度要求：$O(NM)$的動態規劃
https://drive.google.com/file/d/1ECLkM85zf-TS8wMCWiqQP89PNK_b6JZQ/view

### 題解
貪心演算法 + 單調性分治 + 資料結構。
#### Naive greedy idea: 
枚舉$l, r$，並將$A_{l..r}$中的元素從小到大跟$B$從大到小的元素一個一個進行替換，直到總和不會變大為止。
這個想法複雜度是$O(N^2 \times (N + M))$，雖然不夠好，但這是一個可以做逐步優化的出發點。

#### 優化
$f(l, r)$ := 區間$[l, r]$經過操作後，$A_{l..r}$所能達到的總和。
$H(r)$ := 使得$f(l, r)$最大的$l$ ($1 \le l \le r)$。
對於每個$r$，如果我們知道$f(H(r), r)$，其實我們就解出這一題了。

首先我們先來考慮怎麼快速找出$f(l, r)$吧！
從上述的greedy可以發現我們把$B$從大到小排序肯定不虧，所以就先來排序吧！
對於找出$f(l, r)$，我們可以透過binary search找到最大的$k$，滿足$B_k \ge A_{l..r}$第$k$小的元素。而$B_{1..k}$和$A_{l..r}$前$k$小的元素進行交換後，即可得到$f(l, r)$，這部分可以簡單用可持久化線段樹在$O(lgN)$的時間內求出。

另一方面，不難發現 $H(r)$ 是有單調性的，也就是說$H(r) <= H(r + 1)$，因此我們可以用分治的技巧來找出所有的$H$，進而得出每個$f(H(r), r)$的結果，總時間複雜度 $O(N \times \log_2N \times \log_2N)$。