從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)$。