## 0x05 <br> 2021 花中一模 <br> 題解
----
### 大綱
- pA - 尋蛋 101 (Egg)
- pB - 繪畫教室 (Painting)
- pC - 再教育 (Education)
- pD - 音遊創作者 (Rhythm)
- pE - 遊園車 (Cart)
- pF - 雙人迷宮 (Maze)
---
<!-- .slide: data-background="https://i.imgur.com/TIotK53.jpg" -->
### <font color="black"><b> 尋蛋 101 (Egg) </b></font>
----
#### 尋蛋 101
- 你要輸出 $1000$ 個介於 $[1, 10^4]$ 的 **相異** 正整數
- 定義「蛋」的數量是數字裡「$\texttt{0}$」的個數
- 你要讓「蛋」的數量剛好是 $101k + 100$ 的形式
----
#### 尋蛋 101 -- 隨便做做
- 先按照範例輸出做一遍?
$\color{orange}{\mbox{Partial Correct}}\ 44/100$
- 或是直接輸出 $1 \sim 1000$?
$\color{orange}{\mbox{Partial Correct}}\ 91/100$
----
#### 尋蛋 101 -- Solution 1
- 實測發現 $1 \sim 1000$ 可以拿 $91$ 分
- 那麼就想辦法讓他再多 $9$ 個 $\texttt{0}$ 就好!
- 把 $\{1, 2, 3\}$ 換成 $\{2000, 3000, 4000\}$!
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 尋蛋 101 -- Solution 2
- 找出每個數字各有幾個 $\texttt{0}$
- 可以用 `std::vector` 存下來
- 最後輸出 $100$ 個只有一個 $\texttt{0}$ 的跟 $900$ 個沒有 $\texttt{0}$ 的
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
<!-- .slide: data-background="https://i.imgur.com/UqUBRAv.png" -->
### <font color="black"><b> 繪畫教室 (Painting) </b></font>
----
#### 繪畫教室
- 給你 $N$ 張有 $M$ 個欄位的表格 $\small(N \le 200; M \le 30)$
![](https://i.imgur.com/bu1NVCQ.png)
----
#### 繪畫教室 -- 簡化題敘
- <font color="blue">幽靈表格</font>:所有欄位的個位數都跟十位數相同
- <font color="red">幽靈欄位</font>:所有不是「<font color="blue">幽靈表格</font>」的表格該欄位都是 $0$
- <font color="purple">還需加強的方向</font>:不是「<font color="red">幽靈欄位</font>」,且在排除「<font color="blue">幽靈表格</font>」之後沒有滿分
- <font color="lime">最需要加強的方向</font>:「<font color="purple">還需加強的方向</font>」裡,排除「<font color="blue">幽靈表格</font>」之後,打分最高 $\frac{1}{5}$(向上取整)的表格的平均分數最低
- 你要找出所有「<font color="purple">還需加強的方向</font>」以及「<font color="lime">最需要加強的方向</font>」
----
#### 繪畫教室 -- Subtasks
- $[31]$ 不存在「<font color="blue">幽靈表格</font>」以及「<font color="red">幽靈欄位</font>」
- $[\hphantom{0}6]$ 不存在「<font color="blue">幽靈表格</font>」、$N$ 是 $5$ 的倍數
- $[11]$ 不存在「<font color="blue">幽靈表格</font>」
- $[26]$ 不存在「<font color="red">幽靈欄位</font>」
- $[26]$ 「<font color="blue">幽靈表格</font>」及「<font color="red">幽靈欄位</font>」都可能存在
----
#### 繪畫教室 -- Subtask 2
- 沒有「<font color="blue">幽靈表格</font>」跟「<font color="red">幽靈欄位</font>」耶
- 還需加強的方向
- ~~不是「<font color="red">幽靈欄位</font>」,且在排除「<font color="blue">幽靈表格</font>」之後沒有滿分~~
- 沒有滿分
- 直接乾脆的對所有欄位的分數排序!
- 可以用 `std::sort`,不過任何 $O(n^2)$ 的 sort 也可以
----
#### 繪畫教室 -- Subtask 2(續)
- 如果最高分是 $100$ 就不處理他
- 不然就對每個欄位取前 $\frac{1}{5}$ 向上取整的分數「的平均值」
- 你真的需要計算平均值嗎?
- 大家的分母都是一樣的 $\rightarrow$ 只需要計算和!
----
#### 繪畫教室 -- Subtask 2(續)
- C++ 的除法是向下取整的,所以我們需要一個計算向上取整的方法
- $$\left\lceil\frac{x}{5}\right\rceil = \begin{cases}
\lfloor\frac{x}{5}\rfloor, & \textbf{if } \text{$N$ 是 $5$ 的倍數} \\
\lfloor\frac{x}{5}\rfloor + 1, & \textbf{if } \text{$N$ 不是 $5$ 的倍數} \\
\end{cases}$$
- 最後就只要把前 $\left\lceil\frac{N}{5}\right\rceil$ 的分數加總比大小就可以了!
$\color{red}{\mbox{Wrong Answer}}\ 31/100$
----
#### 繪畫教室 -- Subtask 3+4
- 現在可能會有「<font color="red">幽靈欄位</font>」出現
- <font color="red">幽靈欄位</font>的特性:所有分數都是 $0$
- 只要多判斷「第一名也是 $0$ 分就不管」就能拿到這個部份分了!
$\color{red}{\mbox{Wrong Answer}}\ 48/100$
----
#### 繪畫教室 -- Solution
- 會有「<font color="blue">幽靈表格</font>」,也會有「<font color="red">幽靈欄位</font>」
- <font color="blue">幽靈表格</font>的特性:所有分數的十位數跟個位數皆相同
- 個位數:`x % 10`
- 十位數:`(x / 10) % 10`
----
#### 繪畫教室 -- Solution(續)
- <font color="blue">幽靈表格</font>:所有欄位的個位數都跟十位數相同
- 幽靈欄位:所有<font color="blue">不是「幽靈表格」的表格</font>該欄位都是 $0$
- 還需加強的方向:不是「幽靈欄位」,且在<font color="blue">排除「幽靈表格」之後</font>沒有滿分
- 最需要加強的方向:「還需加強的方向」裡,<font color="blue">排除「幽靈表格」之後</font>,打分最高 $\frac{1}{5}$(向上取整)的表格的平均分數最低
----
#### 繪畫教室 -- Solution(續)
- 大家好像都不喜歡<font color="blue">幽靈表格</font>
- 你希望可以先把<font color="blue">幽靈表格</font>們丟掉
- 怎麼丟?
----
**開一個新的陣列存!**
```cpp=
int tmp[N+1][M+1], score[N+1][M+1];
int real_N = 0; /// 記錄正常表格的數量
for (int i = 1; i <= N; ++i) {
int flag = 0; /// 記錄有沒有個位數不等於十位數
for (int j = 1; j <= M; ++j) {
cin >> tmp[i][j];
if (tmp[i][j] % 10 != (tmp[i][j] / 10) % 10)
flag = 1;
}
if (flag == 1) {
/// 正常表格 ///
++real_N;
for (int j = 1; j <= M; ++j)
score[real_N][j] = tmp[i][j];
}
}
```
----
#### 繪畫教室 -- Solution(續)
- 記得要記錄真正的表格數量 $N_\text{real}$
- 現在已經沒有「<font color="blue">幽靈表格</font>」了,只剩下「<font color="red">幽靈欄位</font>」
- 相當於 Subtask 4
- 於是只要再跑 Subtask 4 有<font color="red">幽靈欄位</font>的做法
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
<!-- .slide: data-background="https://i.imgur.com/DUFli4C.jpg" -->
### <font color="black"><b> 再教育 (Education) </b></font>
----
#### 再教育
- 給一個長度為 $N$ $\small(N \le 1.4 \times 10^6)$ 的 $\texttt{ox}$-字串,接下來每一單位時間依序會:
1. 計算 $v_i$:第 $i$ 單位時間 $\texttt{'x'}$ 的數量
2. 把第 $v_i$ 個字元翻轉($\texttt{'o'} \leftrightarrow \texttt{'x'}$)
- 接著有 $Q$ $\small(Q \le 2 \times 10^5)$ 次詢問,給你 $t_i$ $\small(t_i \le 10^{18})$,請求出 $v_{t_i}$。
----
#### 再教育 -- Subtasks
- $[12]$ $N \le 2\,000$、$Q \le 500$、$t_i \le 10^4$
- $[21]$ $N \le 1\,386\,575$、$Q \le 2 \times 10^5$、$t_i \le 10^6$
- $[48]$ $N \le 10^5$、$Q \le 500$、$t_i \le 10^{18}$
- $[19]$ $N \le 1\,386\,575$、$Q \le 2 \times 10^5$、$t_i \le 10^{18}$
----
#### 再教育 -- Subtask 2
- 先計算出在 $1 \sim 10^4$ 單位時間時的答案
- 每次遍歷一遍字串找出有幾個 $\texttt{'x'}$
- 最後對於詢問都可以 $O(1)$ 求出
- 時間複雜度是 $O(NT+Q)$
$\color{red}{\mbox{Wrong Answer}}\ 12/100$
----
#### 再教育 -- Subtask 3
- 每次改一個位置的字元,只會讓 $v_i$ 變成 $v_{i-1} \pm 1$
- 修改的位置可以 $O(1)$ 遞推得到!
- 時間複雜度是 $O(N+T+Q)$
$\color{red}{\mbox{Wrong Answer}}\ 33/100$
----
#### 再教育 -- Subtask 4
**觀察**
- $\texttt{oxxxo}\color{red}{\overset{\longrightarrow}{\texttt{ooo}}}\texttt{xoxx} \Rightarrow \texttt{oxxxoxxxxoxx}$
- $\texttt{oxxxo}\color{red}{\overset{\longleftarrow}{\texttt{xxxx}}}\texttt{oxx} \Rightarrow \texttt{oxxxooooooxx}$
- $\texttt{oxxx}\color{red}{\overset{\longrightarrow}{\texttt{oooooo}}}\texttt{xx} \Rightarrow \texttt{oxxxxxxxxxxx}$
- $\texttt{o}\color{red}{\overset{\longleftarrow}{\texttt{xxxxxxxxxx}}}\texttt{x} \Rightarrow \texttt{ooooooooooox}$
- $\color{red}{\overset{\longrightarrow}{\texttt{ooooooooooo}}}\texttt{x} \Rightarrow \texttt{xxxxxxxxxxxx}$
- $\color{red}{\overset{\longleftarrow}{\texttt{xxxxxxxxxxxx}}} \Rightarrow \texttt{oooooooooooo}$
----
#### 再教育 -- Subtask 4(續)
- 如果一開始戳到的是 $\texttt{'o'}$,那麼他會先一直往右修改,直到遇到第一個 $\texttt{'x'}$
- 接著從那個 $\texttt{'x'}$ 開始連續往左修改直到遇到 $\texttt{'o'}$
- 一直重複上面兩件事情直到所有字元都變成 $\texttt{'o'}$
- 每次都至少可以再多修改一個字元
----
#### 再教育 -- Subtask 4(續)
- 每次都至少可以再多修改一個字元
- 只要把全部的區間處理出來就能比較方便的處理每次詢問了!
- 因為每次左或右界都一定會往外擴,這樣的區間最多只會有 $O(N)$ 個
- 可以使用 two-pointer 維護當前的左右界
- 每次詢問都在那些區間裡找「這段區間對應到的修改時間有沒有包含查詢的時間」
- 暴力尋找的複雜度是 $O(QN)$
$\color{blue}{\mbox{Time Limit Exceeded}}\ 81/100$
----
#### 再教育 -- Solution
- 注意到「那些區間」的修改時間是遞增的
- 可以使用「二分搜」來尋找答案在哪個區間內
- 時間複雜度是 $O(N + Q \lg N)$
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
<!-- .slide: data-background="https://i.imgur.com/xo9ifkN.jpg" -->
### <font color="black"><b> 音遊創作者 (Rhythm) </b></font>
----
#### 音遊創作者
- 有一棵以 $1$ 為根的 $N$ $\small(N \le 2 \times 10^5)$ 個節點的樹
- 你要在上面填 $[1, N]$ 的數字各一次
- 小孩的值要大於父親
- 求每個數字可以填進的「位置」編號的最小值及最大值
----
#### 音遊創作者 -- Subtasks
- $[\hphantom{0}6]$ 樹是一條 $1-2-\dots-N$ 的鏈
- $[26]$ $N \le 10$
- $[51]$ $N \le 2\,000$
- $[17]$ $N \le 2 \times 10^5$
----
#### 音遊創作者 -- Subtask 2
**這是範例二**
![](https://i.imgur.com/MnOaloN.png) ![](https://i.imgur.com/GrUZ32h.png) ![](https://i.imgur.com/Gb62c2d.png)
- 有沒有什麼感覺了?
----
#### 音遊創作者 -- Subtask 2(續)
- 對,沒錯!
- 輸出 $(1, 1) \sim (N, N)$ 就可以了
$\color{red}{\mbox{Wrong Answer}}\ 6/100$
- 因為打完一首只會解鎖下一首,而且難度要遞增
----
#### 音遊創作者 -- Subtask 3
- $N \le 10$ 可以做全排列枚舉
- 枚舉出每個難度放的位置,再去檢查合不合理
- 合理的話就更新答案
- 複雜度是 $O(N \times N!)$
$\color{blue}{\mbox{Time Limit Exceeded}}\ 26/100$
----
#### 音遊創作者 -- Subtask 4
- 反過來想想,不要考慮一個難度能放的位置,考慮一個位置能放的難度
- 一個位置<font color="red">最簡單</font>能放多簡單的歌?
- 一個位置<font color="blue">最難</font>能放多難的歌?
----
#### 音遊創作者 -- Subtask 4(續)
![](https://i.imgur.com/O5d3XIz.png)
----
#### 音遊創作者 -- Subtask 4(續)
![](https://i.imgur.com/2CYNtTv.png)
----
#### 音遊創作者 -- Subtask 4(續)
- 而<font color="red">上面的點數</font>跟<font color="blue">下面的點數</font>實際上就是<font color="lime">一個點</font>的「<font color="red">深度</font>」以及「<font color="blue">子樹大小</font>」
- 都可以由一次 DFS 得到
----
**求<font color="red">深度</font>跟<font color="blue">子樹大小</font>的程式碼**
```cpp=
vector<int> adj[N]; /// adj[i] 裡面存 i 可以到達的所有點
int depth[N], subsize[N];
void dfs(int now, int lst) {
subsize[now] = 1; /// 自己
for (int x : adj[i]) { /// 遍歷所有相鄰的點
if (x == lst) continue; /// 如果跟來的點(父親)相同就繼續
depth[x] = depth[now] + 1; /// 孩子的深度會 + 1
dfs(x, now);
subsize[now] += subsize[x]; /// 加上孩子的大小
}
}
```
- 接著,只要呼叫 `dfs(1, -1)` 就可以得到所有位置的「<font color="red">深度</font>」跟「<font color="blue">子樹大小</font>」了
----
#### 音遊創作者 -- Subtask 4(續)
- 證明一下中間的所有其他難度也能放在<font color="lime">這裡</font>:
- 首先,放難度的順序可視為一種走訪的順序
- 如果從根一路往<font color="lime">該點</font>走則可以有<font color="red">最小值 $\texttt{minval}$</font>
- 如果把<font color="lime">該點</font>留到沒有其他路可以走再走會有<font color="blue">最大值 $\texttt{maxval}$</font>
- 如果先一路往<font color="lime">該點</font>移動,但是先不要拜訪<font color="lime">他</font>,先去拜訪其他 $x$ 個節點之後再拜訪<font color="lime">他</font>,則<font color="lime">他</font>會是第 $\color{red}{\texttt{minval}} + x$ 個被拜訪的位置
----
#### 音遊創作者 -- Subtask 4(續)
- 現在你知道每個位置可以放哪些難度了
- 接著就只要把它們填回去就可以了!
- 複雜度是 $O(N)$ DFS + $O(N^2)$ 填回去
$\color{blue}{\mbox{Time Limit Exceeded}}\ 83/100$
----
#### 音遊創作者 -- Solution 1
- 其實也只有填回去的部分會超時而已
- 考慮該如何加速這部分
- 第一種暴力做法是利用一種叫做「線段樹」的常見資料結構
- 需要支援「區間修改」以及「單點查詢」的操作
- 時間複雜度是 $O(N \lg N)$
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 音遊創作者 -- Solution 2
- 另外一種方法是使用 $\texttt{std::set}$ 一個集合來維護
- 依序對難度遍歷,在 $L_i$ 把 $i$ 加進去,在 $R_i$ 把 $i$ erase 掉
- 難度 $x$ 的答案就是在遍歷到 $x$ 時集合內的最小最大值
- 時間複雜度是 $O(N \lg N)$
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 音遊創作者 -- Solution 3
- 如果依序看位置 $1 \sim N$ 的區間,會發現
- $\bigcup\limits_{i=1}^{n}{[L_i, R_i]} = [1, \max\limits_{1 \le i \le n}\{R_i\}]$
- 證明:令裡面使 $R_i$ 最大的 $i = k$
- 把 $1$ 到 $k$ 路徑上的所有位置的區間拿出來會發現他包含了所有 $L_i$(深度)在 $1 \sim L_k$ 的值
- 也就是說所有 $1 \sim L_k$ 都會存在,且 $L_k \sim R_k$ 也會存在
- 也就是說難度越大的歌可以放的最大位置只會遞增!
----
#### 音遊創作者 -- Solution 2(續)
- 同理可證難度越小的歌可以放的最小位置只會遞減
- 所以要找最大值,只要維護每個位置的 $R_i$ 有沒有增加
- 如果最大值從 $R_i$ 變成 $R_j$,那就更新 $[R_i + 1, R_j]$ 裡所有難度的最大位置
- 最小值就是相反的作法
- 時間複雜度只要 $O(N)$!
$\color{lime}{\mbox{Accepted}}\ 100/100$
---
<!-- ![](https://i.imgur.com/sALpfWZ.jpg) -->
<!-- .slide: data-background="https://i.imgur.com/RVTEByH.jpg" -->
### <font color="black"><b> 遊園車 (Cart) </b></font>
----
#### 遊園車
- 給你一個長度為 $N$ $\small(N \le 10^5)$ 的陣列 $g$ 以及一個長度為 $K$ $\small(K \le 100)$ 的權重陣列 $r$
- 你要求出所有可能的平移狀態下的最大連續和
- 選出一個連續子區間使裡面的元素和最大
----
#### 遊園車 -- Subtasks
- $[23]$ $N \le 2\,000$、所有權重都是 $1$
- $[29]$ $N \le 10^5$、所有權重都是 $1$
- $[20]$ $N \le 2\,000$、$K \le 100$
- $[24]$ $N \le 10^5$、$K = 1$
- $[\hphantom{0}4]$ $N \le 10^5$、$K \le 100$
----
#### 遊園車 -- Subtask 2
- 「每個車廂都有一個擬真度,普通席的擬真度皆為 $1$,而特等席各有一個擬真度 $r_1, r_2, \dots, r_K$。」
- 注意到 $K = 1$ 且 $r_1 = 1$ 相當於所有席次都可以當作普通席
- 也就是說所有平移的狀況都跟原本一樣
- 使用雙層 $\texttt{for}$ 迴圈來回答陣列中的最大連續和
----
**暴力作法**
```cpp=
int max_sum = -1000000; /// 要設定一個足夠小的數字當最大值
for (int i = 1; i <= N; ++i) {
int sum = 0; /// 計算從 g[i] 開始的和
for (int j = i; j <= N; ++j) {
sum += g[j]; /// 計算 g[i..j] 的和
max_sum = max(max_sum, sum); /// 更新最大值
}
}
```
$\color{red}{\mbox{Wrong Answer}}\ 23/100$
----
#### 遊園車 -- Subtask 3
- 這個子題就是經典的最大連續和問題
- 主要的解法有兩種
- 維護前綴最小值
- Kadane's algorithm
----
#### 遊園車 -- Subtask 3(續)
**維護前綴最小值**
- 假設現在固定右界 $R$,要怎麼求出<font color="red">以位置 $R$ 結尾</font>的最大連續和?
- 先觀察區間和的算式
- $\sum\limits_{i=l}^{r}{a_i} = \color{red}{\sum\limits_{i=1}^{r}{a_i}} - \color{blue}{\sum\limits_{i=1}^{l-1}{a_i}}$
- <font color="red">第一項</font>只跟右界有關
- <font color="blue">第二項</font>只跟左界有關
----
#### 遊園車 -- Subtask 3(續)
**維護前綴最小值**
- 先假設你已經計算出所有前綴和 $S_n = \sum\limits_{i=1}^{n}{a_i}$
- 那麼<font color="red">以位置 $R$ 結尾</font>的最大連續和就是 $\color{red}{S_R} - \color{blue}{\min\{0, S_1, S_2, \dots S_{R-1}\}}$
- $S_n$ 跟 $\color{blue}{\min\{0, S_1, S_2, \dots S_{R-1}\}}$ 都可以一邊計算答案一邊維護
----
**維護前綴最小值**
```cpp=
int max_sum = -1000000;
int prefix_sum = 0, min_prefix_sum = 0; /// 記錄前綴和
for (int i = 1; i <= N; ++i) {
prefix_sum += g[i];
max_sum = max(max_sum, prefix_sum - min_prefix_sum);
min_prefix_sum = min(min_prefix_sum, prefix_sum);
}
```
$\color{red}{\mbox{Wrong Answer}}\ 52/100$
----
**Kadane's algorithm**
- 實際上找最大連續和有一個很簡單的 greedy 作法
```cpp=
int max_sum = -1000000, sum = 0;
for (int i = 1; i <= N; ++i) {
sum += g[i];
// if (sum < 0) sum = 0;
max_sum = max(max_sum, sum);
if (sum < 0) sum = 0;
}
```
- 每次維護當前前綴的最大後綴和
- 只要 $> 0$,繼續加下去一定會更好
- 只要 $< 0$,全部都丟掉一定會更好
- 根據 $\texttt{if (sum < 0) sum = 0;}$ 的位置可以調整能不能取空區間
----
#### 遊園車 -- Subtask 4
- 總共有幾種可能的平移方式呢?
- $N + K$ 種
- 考慮 $r_1 \sim r_K$ 對到 $g_N$
- 接著 $r_K$ 對到 $g_{N-1} \sim g_1$
- 還有一種是完全沒蓋到的
- 直接暴力平移,配上剛剛 $O(N)$ 的最大連續和
- 總複雜度是 $O(N^2 + NK)$
$\color{blue}{\mbox{Time Limit Exceeded}}\ 76/100$
----
**平移實作**
```cpp=
/// 先令星街列車在 [-(K-1), 0] 的位置 ///
/// 接著每一單位時間往右移動直到完全離開 ///
for (int L = -K+1, R = 0; L <= N; ++L, ++R) {
vector<int> tmp_g = g; /// 複製一份原本的陣列
for (int i = max(L, (int)1); i <= min(R, N); ++i)
tmp_g[i] *= r[i-L]; /// 對他加權
int sum = 0; /// 使用 Kadane's Algorithm 計算最大連續和
for (auto x : tmp_g) {
sum += x;
mss = max(mss, sum);
sum = max(sum, 0);
}
}
```
----
#### 遊園車 -- Subtask 5
- 只有一個位置會被修改 $\rightarrow$ 把陣列切成修改的位置<font color="red">前</font><font color="blue">後</font>兩半
- 注意到<font color="red">正著做</font>跟<font color="blue">反著做</font>會得到一樣的答案
- 先當作陣列空了一個位置,求出<font color="red">前綴</font>跟<font color="blue">後綴</font>的答案
- 合併<font color="red">前綴</font>、<font color="lime">修改處</font>、<font color="blue">後綴</font>的答案
----
#### 遊園車 -- Subtask 5(續)
- 具體來說,單純求最大連續和的作法基本上都是求出「以當前位置 **結尾** 的最大連續和」
- 不過,只要也考慮到「以當前位置 **開頭** 的最大連續和」
- 就是反過來做一遍
- 就能輕鬆處理只有一個位置被改變的答案了!
----
#### 遊園車 -- Subtask 5(續)
- 合併之後會有幾種新的值?
- <font color="lime">修改處</font>
- <font color="red">前綴的最大後綴</font> + <font color="lime">修改處</font>
- <font color="lime">修改處</font> + <font color="blue">後綴的最大前綴</font>
- <font color="red">前綴的最大後綴</font> + <font color="lime">修改處</font> + <font color="blue">後綴的最大前綴</font>
- 好好維護就能拿到這分數
$\color{red}{\mbox{Wrong Answer}}\ (76 + 20)/100$
----
#### 遊園車 -- Solution 1
- 首先,先來加速平移陣列的速度
- 每次平移都只會影響到至多 $K+1$ 個數字
- 那麼其實就可以 $O(K)$ 做到!
- 其實,只要在需要使用 $g_p$ 的時候查詢他對應到的 $r_{id}$ 就好了
----
#### 遊園車 -- Solution 1(續)
- 一樣,考慮合併之後會出現幾種新的答案
- <font color="lime">修改處的最大連續和</font>
- <font color="red">前綴的最大後綴</font> + <font color="lime">修改處的最大前綴</font>
- <font color="lime">修改處的最大後綴</font> + <font color="blue">後綴的最大前綴</font>
- <font color="red">前綴的最大後綴</font> + <font color="lime">修改處的和</font> + <font color="blue">後綴的最大前綴</font>
- 這個沒有很好寫,所以它只有 $4$ 分
- 好好維護才能拿到這分數
$\color{lime}{\mbox{Accepted}}\ 100/100$
<!--
----
#### 遊園車 -- Solution 2
- DP
-->
----
#### 遊園車 -- 額外注意事項
- 記得要開 $\texttt{long long}$
- 在對陣列加權時不能直接乘上去除回來
- 遇到 $r_i = 0$ 就會吃 $\color{orange}{\mbox{Runtime Error}}$
- 選取的區間要非空,不要先把答案歸 $0$ 再取 $\max$
---
<!-- .slide: data-background="https://i.imgur.com/H3GxylM.jpg" -->
### <font color="black"><b> 雙人迷宮 (Maze) </b></font>
----
#### 雙人迷宮
- 有一張 $R \times C$ $\small(R, C \le 30)$ 的地圖 $M$,有些格子有障礙物
- 一開始 A 跟 B 分別站在 $(1, 1)$ 跟 $(R, C)$ 的位置,接著你會下一連串的指令:
- 從 $(i, j)$ 移到 $(i \pm 1, j)$ 或 $(i, j \pm 1)$
- A 會按照你的指令移動,而 B 每次都會朝著你的指令的 **相反方向** 移動
- 如果任何人無法跟著指令移動,就會待在原地
- 求出最短的移動指令使 A 跟 B 站在同一個格子裡
----
#### 雙人迷宮 -- Subtasks
- $[20]$ 地圖旋轉對稱
- $[10]$ $R = 1$
- $[15]$ $R = 2$
- $[20]$ $R, C \le 4$
- $[35]$ $R, C \le 30$
- 只輸出步數能拿到 $40\%$ 分數
----
#### 雙人迷宮 -- Subtask 2
- A 跟 B 的行動方式是顛倒過來的
- 旋轉對稱 $\rightarrow$ 不會有下某個指令後只有一人能行動的狀況出現
- 相遇的點一定是在正中間
- 如果 $R$ 跟 $C$ 不都是奇數則無解
----
#### 雙人迷宮 -- Subtask 2(續)
- 找到一條從 $(1, 1)$ 通往中間 $(\frac{R+1}{2}, \frac{C+1}{2})$ 的道路
- BFS
- BFS 的同時記得紀錄「是誰走到我的」,最後才能回朔解
$\color{red}{\mbox{Wrong Answer}}\ 20/100$
----
#### 雙人迷宮 -- Subtask 3
- $R = 1$ $\rightarrow$ 只需要下「往右走」的指令
- 如果兩人中間有障礙物那他們一定跨不過去
- $\texttt{ooooo}\color{red}{\texttt{x}}\texttt{ooo}$
- 如果 $C$ 是偶數那他們也遇不到
- 錯身而過不算遇到
- 簡單的 $\texttt{if-else}$ 判斷
$\color{red}{\mbox{Wrong Answer}}\ (10 + 20)/100$
----
#### 雙人迷宮 -- Subtask 5
- 範圍看起來夠小,可以試試看暴搜所有答案
- 枚舉長度為 $1, 2, \dots$ 的所有指令
- 實際上因為答案必定 $\le 9$ 所以可以通過
$\color{blue}{\mbox{Time Limit Exceeded}}\ (20 + 30)/100$
----
#### 雙人迷宮 -- Solution
- 兩個人看起來很不好想耶
- 那先來看看真正有什麼狀態吧!
- 只有 A 跟 B 的移動會改變狀態
- 狀態:A 在 $(r_A, c_A)$ 且 B 在 $(r_B, c_B)$
- 總共有 $(RC)^2$ 種狀態
----
#### 雙人迷宮 -- Solution(續)
- 一開始的起點在 $(1, 1, R, C)$
- 所有 $(r, c, r, c)$ 的狀態都是終點
- 站在同一個格子裡
- 一個狀態會有四種可能的變化
- $\texttt{'N'}$、$\texttt{'S'}$、$\texttt{'E'}$、$\texttt{'W'}$
- 建四條邊出去指向那四種狀態
- 求從起點到任意一個終點的最短距離
- 一樣是 BFS!
$\color{lime}{\mbox{Accepted}}\ 100/100$
----
#### 雙人迷宮 -- 額外注意事項
- 如果 judge 比較慢可能用遞迴會導致 $\color{blue}{\mbox{TLE}}$
- 可以用 queue 就盡量用 queue 吧~
---
### 總覽
- pA - 送分題
- pB - 簡單實作題
- pC - 觀察 + 二分搜
- pD - DFS +(觀察/線段樹)
- pE - 經典題 + 前後綴預處理
- pF - 觀察 + BFS + 輸出解
----
### 總覽
**以下是只用「暴力」實作可以得到的分數**
- pA:$\color{lime}{100}$
- pB:$\color{lime}{31}\ /\ \color{lime}{6}\ /\ \color{lime}{11}\ /\ \color{lime}{26}\ /\ \color{lime}{26}$
- pC:$\color{lime}{12}\ /\ \color{lime}{21}\ /\ \color{red}{48}\ /\ \color{red}{19}$
- pD:$\color{lime}{6}\ /\ \color{lime}{26}\ /\ \color{red}{51}\ /\ \color{red}{17}$
- pE:$\color{lime}{23}\ /\ \color{red}{29}\ /\ \color{red}{20}\ /\ \color{red}{24}\ /\ \color{red}{4}$
- pF:$\color{lime}{20}\ /\ \color{lime}{10}\ /\ \color{red}{20}\ /\ \color{lime}{20}\ /\ \color{red}{35}$
- 總共是 $100 + 100 + 33 + 32 + 23 + 50 = 338$
---
## 謝謝收看 peko
<!-- [計分板](https://sorahisa.github.io/0x00/Scoreboard/0x04/Ranking.html)以外的東西都在[這裡](https://drive.google.com/drive/folders/1M9b5ppgllP5Rv3rI3pGm1RaM8EOkuSNR)了!-->
<p style="font-size:18px">(10/27 04:00 之前會把標程、測資等等的東西都放上去<a href="https://drive.google.com/drive/folders/1NTTVK25dS4qCMIBEACSu3Xm6YSdhaALB">這裡</a>)</p>
各位之後的區賽加油喵 >////<
希望大家都可以拿獎金回家 >////<
{"metaMigratedAt":"2023-06-16T12:58:59.887Z","metaMigratedFrom":"YAML","title":"0x05 2021 花中一模 題解","breaks":true,"slideOptions":"{\"theme\":\"solarized\",\"transition\":\"fade\",\"controls\":false}","contributors":"[{\"id\":\"e573a1ba-d69b-44a7-a0d5-9d817fb786cc\",\"add\":30117,\"del\":11987}]"}