0x05 2021 花中一模題解

## 0x05 2021 花中一模 題解 ---- ### 大綱 - pA - 尋蛋 101 (Egg) - pB - 繪畫教室 (Painting) - pC - 再教育 (Education) - pD - 音遊創作者 (Rhythm) - pE - 遊園車 (Cart) - pF - 雙人迷宮 (Maze) ---  ### 尋蛋 101 (Egg) ---- #### 尋蛋 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$ ---  ### 繪畫教室 (Painting) ---- #### 繪畫教室 - 給你 $N$ 張有 $M$ 個欄位的表格 $\small(N \le 200; M \le 30)$ ![](https://i.imgur.com/bu1NVCQ.png) ---- #### 繪畫教室 -- 簡化題敘 - 幽靈表格：所有欄位的個位數都跟十位數相同 - 幽靈欄位：所有不是「幽靈表格」的表格該欄位都是 $0$ - 還需加強的方向：不是「幽靈欄位」，且在排除「幽靈表格」之後沒有滿分 - 最需要加強的方向：「還需加強的方向」裡，排除「幽靈表格」之後，打分最高 $\frac{1}{5}$（向上取整）的表格的平均分數最低 - 你要找出所有「還需加強的方向」以及「最需要加強的方向」 ---- #### 繪畫教室 -- Subtasks - $[31]$ 不存在「幽靈表格」以及「幽靈欄位」 - $[\hphantom{0}6]$ 不存在「幽靈表格」、$N$ 是 $5$ 的倍數 - $[11]$ 不存在「幽靈表格」 - $[26]$ 不存在「幽靈欄位」 - $[26]$ 「幽靈表格」及「幽靈欄位」都可能存在 ---- #### 繪畫教室 -- Subtask 2 - 沒有「幽靈表格」跟「幽靈欄位」耶 - 還需加強的方向 - ~~不是「幽靈欄位」，且在排除「幽靈表格」之後沒有滿分~~ - 沒有滿分 - 直接乾脆的對所有欄位的分數排序！ - 可以用 `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 - 現在可能會有「幽靈欄位」出現 - 幽靈欄位的特性：所有分數都是 $0$ - 只要多判斷「第一名也是 $0$ 分就不管」就能拿到這個部份分了！ $\color{red}{\mbox{Wrong Answer}}\ 48/100$ ---- #### 繪畫教室 -- Solution - 會有「幽靈表格」，也會有「幽靈欄位」 - 幽靈表格的特性：所有分數的十位數跟個位數皆相同 - 個位數：`x % 10` - 十位數：`(x / 10) % 10` ---- #### 繪畫教室 -- Solution（續） - 幽靈表格：所有欄位的個位數都跟十位數相同 - 幽靈欄位：所有不是「幽靈表格」的表格該欄位都是 $0$ - 還需加強的方向：不是「幽靈欄位」，且在排除「幽靈表格」之後沒有滿分 - 最需要加強的方向：「還需加強的方向」裡，排除「幽靈表格」之後，打分最高 $\frac{1}{5}$（向上取整）的表格的平均分數最低 ---- #### 繪畫教室 -- Solution（續） - 大家好像都不喜歡幽靈表格 - 你希望可以先把幽靈表格們丟掉 - 怎麼丟？ ---- **開一個新的陣列存！** ```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}$ - 現在已經沒有「幽靈表格」了，只剩下「幽靈欄位」 - 相當於 Subtask 4 - 於是只要再跑 Subtask 4 有幽靈欄位的做法 $\color{lime}{\mbox{Accepted}}\ 100/100$ ---  ### 再教育 (Education) ---- #### 再教育 - 給一個長度為 $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$ ---  ### 音遊創作者 (Rhythm) ---- #### 音遊創作者 - 有一棵以 $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 - 反過來想想，不要考慮一個難度能放的位置，考慮一個位置能放的難度 - 一個位置最簡單能放多簡單的歌？ - 一個位置最難能放多難的歌？ ---- #### 音遊創作者 -- Subtask 4（續） ![](https://i.imgur.com/O5d3XIz.png) ---- #### 音遊創作者 -- Subtask 4（續） ![](https://i.imgur.com/2CYNtTv.png) ---- #### 音遊創作者 -- Subtask 4（續） - 而上面的點數跟下面的點數實際上就是一個點的「深度」以及「子樹大小」 - 都可以由一次 DFS 得到 ---- **求深度跟子樹大小的程式碼** ```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)` 就可以得到所有位置的「深度」跟「子樹大小」了 ---- #### 音遊創作者 -- Subtask 4（續） - 證明一下中間的所有其他難度也能放在這裡： - 首先，放難度的順序可視為一種走訪的順序 - 如果從根一路往該點走則可以有最小值 $\texttt{minval}$ - 如果把該點留到沒有其他路可以走再走會有最大值 $\texttt{maxval}$ - 如果先一路往該點移動，但是先不要拜訪他，先去拜訪其他 $x$ 個節點之後再拜訪他，則他會是第 $\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$ ---   ### 遊園車 (Cart) ---- #### 遊園車 - 給你一個長度為 $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$，要怎麼求出以位置 $R$ 結尾的最大連續和？ - 先觀察區間和的算式 - $\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}}$ - 第一項只跟右界有關 - 第二項只跟左界有關 ---- #### 遊園車 -- Subtask 3（續） **維護前綴最小值** - 先假設你已經計算出所有前綴和 $S_n = \sum\limits_{i=1}^{n}{a_i}$ - 那麼以位置 $R$ 結尾的最大連續和就是 $\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$ 把陣列切成修改的位置前後兩半 - 注意到正著做跟反著做會得到一樣的答案 - 先當作陣列空了一個位置，求出前綴跟後綴的答案 - 合併前綴、修改處、後綴的答案 ---- #### 遊園車 -- Subtask 5（續） - 具體來說，單純求最大連續和的作法基本上都是求出「以當前位置 **結尾** 的最大連續和」 - 不過，只要也考慮到「以當前位置 **開頭** 的最大連續和」 - 就是反過來做一遍 - 就能輕鬆處理只有一個位置被改變的答案了！ ---- #### 遊園車 -- Subtask 5（續） - 合併之後會有幾種新的值？ - 修改處 - 前綴的最大後綴 + 修改處 - 修改處 + 後綴的最大前綴 - 前綴的最大後綴 + 修改處 + 後綴的最大前綴 - 好好維護就能拿到這分數 $\color{red}{\mbox{Wrong Answer}}\ (76 + 20)/100$ ---- #### 遊園車 -- Solution 1 - 首先，先來加速平移陣列的速度 - 每次平移都只會影響到至多 $K+1$ 個數字 - 那麼其實就可以 $O(K)$ 做到！ - 其實，只要在需要使用 $g_p$ 的時候查詢他對應到的 $r_{id}$ 就好了 ---- #### 遊園車 -- Solution 1（續） - 一樣，考慮合併之後會出現幾種新的答案 - 修改處的最大連續和 - 前綴的最大後綴 + 修改處的最大前綴 - 修改處的最大後綴 + 後綴的最大前綴 - 前綴的最大後綴 + 修改處的和 + 後綴的最大前綴 - 這個沒有很好寫，所以它只有 $4$ 分 - 好好維護才能拿到這分數 $\color{lime}{\mbox{Accepted}}\ 100/100$  ---- #### 遊園車 -- 額外注意事項 - 記得要開 $\texttt{long long}$ - 在對陣列加權時不能直接乘上去除回來 - 遇到 $r_i = 0$ 就會吃 $\color{orange}{\mbox{Runtime Error}}$ - 選取的區間要非空，不要先把答案歸 $0$ 再取 $\max$ ---  ### 雙人迷宮 (Maze) ---- #### 雙人迷宮 - 有一張 $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  （10/27 04:00 之前會把標程、測資等等的東西都放上去<a href="https://drive.google.com/drive/folders/1NTTVK25dS4qCMIBEACSu3Xm6YSdhaALB">這裡</a>） 各位之後的區賽加油喵 >////< 希望大家都可以拿獎金回家 >////<