---
# System prepended metadata

title: 0x05 2021 花中一模 題解
tags: [Editorial]

---

---
title: 0x05 2021 花中一模 題解
tags: Editorial
slideOptions:        # 簡報相關的設定
  theme: solarized   # 顏色主題
  transition: 'fade' # 換頁動畫
  controls: false
---

## 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>

各位之後的區賽加油喵 >////<
希望大家都可以拿獎金回家 >////<
