# AtCoder Beginner Contest 413
Unofficial Editorial
~~為了減少製作成本~~，以下不會幫你翻譯題目，也不會有實作的 code (因為我覺得要自己想過然後用自己的方式實做出來比較好，不要直接抄)。
如果想看 code ，可以去 submission 找，應該有更多實作比我好看的。
### A
(●'◡'●)
### B
:::spoiler 觀察
$N<=100$
$S_i<=10$
:::
:::spoiler 實作
暴力枚舉 $i$、$j$，把連起來的字串丟到 `set` 裡面
:::
### C
:::spoiler 觀察 1
很明顯是 `queue` 的操作，~~題目名字就有講了~~
:::
:::spoiler 觀察 2
type 1 的數字最多可能被複製 $1e9$ 次
不能暴力，不然會拿到 TLE + MLE
:::
:::spoiler 實作
開 `queue` ，裡面放 `pair` ，存 `{數字, 複製幾次}`
type 2 要拿 $k$ 個數字出來的時候，就先看 `queue` 的 `front` 那個數字夠不夠多，不夠就扣掉再繼續拿
:::
### D
:::spoiler 觀察 1
若公比是 1 或 -1，全部數字絕對值會一樣
公比是 -1 的話還要數負號是否是 $\lceil \frac{n}{2} \rceil$ 個或是 $\lfloor \frac{n}{2} \rfloor$ 個
:::
:::spoiler 觀察 2
若公比不是 1 或 -1 ，按照絕對值大小排序就可以判斷了 (公比是負的的話正負號會交錯出現)
:::
:::spoiler 觀察 2 的判斷方法
若 ${a_1, a_2, a_3}$ 是等比，那 $a_2 \times a_2 = a_1 \times a_3$
記得開 `long long`
:::
:::spoiler WA ?
$n=2$ 答案一定是 ||Yes||
:::
:::spoiler 複雜度
$O(nlogn)$ (因為要排序)
:::
### E
:::spoiler 觀察 1
陣列大小是 2 的冪次，操作也是 2 的冪次
畫圖 ?
:::
:::spoiler 觀察 2
要在同一個框框裡面才能 reverse
:::
:::spoiler 實作
遞迴，如果右子樹第一個元素比左子樹第一個元素小，就交換左子樹和右子樹，使整個樹的字典序盡可能小
:::
:::spoiler 複雜度
$O(nlogn)$
令 $n$ 表示陣列大小，樹的深度就是 $logn$
:::
### F
:::spoiler 觀察 1
如果沒有~~討厭的~~ Aoki 擋路，可以把全部的 goal 丟到 `queue` 裡面然後 BFS
:::
:::spoiler 觀察 2
對於一個答案未知的空格，如果他相鄰的格子有兩格以上是 goal，那不管 Aoki 擋哪邊，他都可以在 1 步內走到
推廣 ?
:::
:::spoiler 觀察 2 的推廣
對於一個答案未知的空格，如果他相鄰的格子有兩格答案被算出來了，他的答案就會是那兩格中答案比較大的再 $+1$ (因為 Aoki 會不讓你走步數比較少的那邊)
:::
:::spoiler 實作
BFS
:::
:::spoiler 複雜度
$O(HW)$，$H$ 和 $W$ 是長和寬
:::
### G
:::spoiler 觀察 1
$H, W<=2e5$ 不能直接 BFS
:::
:::spoiler 觀察 2
障礙最多只有 $2e5$ 個
可以從障礙物下手，怎樣會沒辦法走到
:::
:::spoiler 觀察 3
1. 同時碰到上面和下面
2. 同時碰到左邊和右邊
3. 同時碰到右邊和下面
4. 同時碰到上面和左邊
:::
:::spoiler 實作
對於一大塊連通的障礙物，若滿足上圖任一個條件就會把人和星星分開
DFS、BFS、DSU 都可以
這邊的連通是指||八個方向||
:::
:::spoiler 複雜度
$O(klogk)$ (因為 DFS 的時候用 `map` 存障礙物位置)
:::