[TOI] 2022 初選
這篇拖稿很久了，想說因為明天就是選訓營所以來寫個初選檢討，
看看去年的我跟今年的我，這一年來到底成長了多少。
想試試看用不同的格式檢討 ><
賽前
在坐捷運去考場的時候，緊張到手一直瘋狂冒汗，
到的時候還是很緊張，很害怕會跟去年全國賽一樣燒雞，
後來去 7-11 買了巧克力補充血糖，結果還是沒有用，
後來是進了考場才開始安頓下來，深呼吸想自己的策略，專注在比賽上。
賽前給自己的策略：
- 讀好題，想不到就重讀題，實作前重讀題，題敘很長要自己簡化題敘。
- 注意時間，發現在乾燒就
- 重讀題（你可能看錯了）
- 上廁所（整理心態、思緒）
- 跳題
- 不要怕實作出來 WA 而跳題，時間花太久總是該跳
- OI 制的秘訣就是分數高的贏，分數低的輸，沒有其他原因。
賽中
進場登入就花了我有夠長的時間，結果是自己打錯= =
開場先讀 A
- A entrance
給你 $n$ 個格子點，問有多少格子點以他為中心畫半徑為 $r$ 的圓涵蓋到奇數個給定的點。
$1 \leq n \leq 2500,\, 1 \leq r \leq 10$
[26] $n = 1$
[36] 座標絕對值不超過 $100$
[38] 無額外限制
看了之後我覺得他是簽到題，只要把點換圓、圓換點就可以直接暴力 $O(nr^2 \log nr)$ 用 map 做掉，
寫上去就過了，
00:14 A 100
$\newline$
寫完之後繼續把題目讀完，
- B keyboard
給你一個鍵盤的圖跟移動規則，你有兩隻手指頭在F跟J，在 1 單位時間只能移動一根手指頭 1 單位距離的條件下，打出給定字串 $S$ 需要多久。
$1 \leq |S| \leq 10^4$
[29] $|S| \leq 20$
[30] 所有字母都在中間的橫排
[41] 無額外限制
初步的想法就是這題是水 DP，然後比較麻煩的是怎麼建出鍵盤這件事。
- C bike
給你一棵邊帶正權的樹，有 $n$ 個節點，每個節點上有 $w_i$ 台腳踏車，你想要讓所有點都變剛好 $k$ 台，問最小達成目標的總腳踏車移動距離。
$1 \leq n \leq 10^5,\, 1 \leq k \leq 10,\, \sum w_i = nk$
[10] $n \leq 10$
[11] $w_i > k$ 的只有一個
[17] 給定的樹是一條鍊
[62] 無額外限制
大概就是樹上 DP 之類的，但仔細想過根本就是 greedy 的做就好了。
- D 2022
定義一個合法的數字是- 由 $n_0$ 個 0 以及 $n_2$ 個 2 組成，可以有前導 0。
- 是 $22$ 的倍數
- 問滿足條件第二大及第二小的。
$1 \leq n_0,\,n_2 \leq 10^5$
[8] $n_0,\,n_2 \leq 10$
[7] $n_0,\,n_2 \leq 30$
[14] $n_0,\,n_2 \leq 300$
[24] $n_2$ 是偶數
[44] 無額外限制
剛看到這題的時候以為是簡單題，但稍微想過之後就發現沒這麼單純。
- E spy
給定 $n \times m$ 的網格圖，輸出一個（或決定沒有）環狀路徑使得沒有相鄰兩項連線的方位角是 $45^\circ$ 的倍數。
$2 \leq n,\,m \leq 1000,\, 4 \leq nm \leq 2000$
[7] $nm \leq 16$
[35] $n = 2$ 或 $m = 2$
[47] $12 \leq n,\,m$
[11] 無額外限制
看完的時候就覺得這是怪題絕對不是因為我想出類似的題目，決定最後做。
接下來開題順序大概就是 $B \rightarrow C \rightarrow D \rightarrow E$，
B 花比較多時間在想要怎麼建鍵盤，後來是直接把鍵盤刷上去然後用位置的規律建邊跑 Floyd-Warshall，
DP 的部分反而仔細把轉移式寫出來就很簡單了，傳上去
00:37 B 0
$\newline$
結果是忘記把相同的距離設成 0，我是智障吧。
00:39 B 100
$\newline$
C 樹上 greedy 很水就不多說了，直接開寫。
00:50 C 100
$\newline$
到這裡我決定先看 D，因為 E 大概不是隨機就是找規律得怪題目，
稍微想了一些我目前有想到的構造方法，現在還以為最小就是最大 reverse 的假解，
之後傳上去
01:02 D 0
$\newline$
看了一下子題結果，發現連偶數都沒過，應該就是這部分一定有判爛，
暴力驗了一下偶數的小測資發現自己漏了一些 case，傳上去
01:09 D 32
$\newline$
也就是說連 10 的那個子題都過了，跟我一開始想的一樣：奇數的 case 在 10 以下是沒有作用的，
繼續把奇數修好之後，不斷傳但都只有
01:20 D 24
01:21 D 32
這時候決定再給自己一些時間想，如果下個沒做出來就先跳題，結果判了之後
01:24 D 32
$\newline$
這時候我應該要跳了，但突然想到我新判的這個 case 其實會作用到更多的地方，當下我就想大概沒有其他的 case 了，因為我能想出來的策略都被這些全部涵蓋掉了，所以判完之後終於
01:29 D 100
$\newline$
這時候場外我好像是第一個 4
還有一個半小時可以做怪題 E，再讀了一次題目發現什麼都沒幫助，決定先開始撈子題。
長寬都是 2 的在紙上稍微畫一畫就做完了，做出來之後傳上去
01:45 E 0
$\newline$
沒過之後開始 debug，可是怎麼看都沒有找到，再傳一次之後還是
01:48 E 0
$\newline$
這時候決定重看題目看看我是不是看錯了，看完之後發現題目的輸出格式是
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_{nm}\ y_{nm}$
$x_1\ y_1$
有夠雷= =
改完之後傳上去就拿到分數了。
01:53 E 35
$\newline$
這時候有點猶豫要開始寫暴力還是開始寫隨機，
這時候的敗筆應該是先開始寫暴力才對，但我卻是開始寫了我不確定的隨機。
這裡就不詳細寫隨機是怎麼隨機的，大概就跟 Knight Tour 的隨機很像。
但是實作出來卻屢屢在本機做不出來，傳上去只有
02:16 E 0
02:19 E 35
02:24 E 0
02:27 E 0
02:28 E 0
02:45 E 0
02:47 E 0
$\newline$
意識到時間根本就不夠寫暴力了，在最後打表壓秒傳上去
02:58 E 0
應該是有一個 case 寫爛了，沒過。
出場
一開始我以為今年簡單很多，線會是 400 + E 決勝負之類的，有點怕因為自己暴力沒過所以就下去。
結果聽到 wcwu 300, victor.gao 329, amano_hina 326 之後發現好像跟我預估的差很多，
最後看板發現跟一堆人並列 Rk. 2，
還有南部只有我進 qwq，
個人覺得 victor.gao 跟 amano_hina 都差一點點，而且差 A 很可惜 qwq
今年突然跑出一堆人，感覺選訓要被揍爛了。
檢討
基本上前面都算打的很好，但 E 簡直是我整場的敗筆。
賽後出來發現寬度是 3 的隨便構都有規律，然後隨機的時候應該多多嘗試不同的辦法，
總之最後打得真的有夠爛= =，甚至沒有留時間做暴力／DFS 剪枝。
希望我可以對於這種沒有特定主題的東西有多一點想法，
還有就是希望今年選訓可以超過我去年的表現，
目標：
- 進 2!（但我感覺機會渺茫 qwq）
- 一天一 OI 跟 Blog 檢討
各位加油 ><