# AA 競程 2022 TOI 模擬賽第二場 --- * 賽前難易度猜測 E < B < C < A < D (~~其實老師覺得後三題難度差不多~~) * 實際每題 AC 人數 A：10 人 B：14 人 C：6 人 D：6 人 E：9 人 --- * 每題的部分分都是經典題 A, 子題 1：set 操作,子題 2：裸並查集 B, 子題 1：三角形面積計算,子題 3：凸包+多邊形面積計算 C, 子題 1~3：經典二分搜+折半枚舉題 D, 子題 2：最短路問題 E, 本身就是經典線段數問題 --- ## B. 第 K 小簡單多邊形 ### 首殺： hank55663 (35 分鐘) ---- * 考察知識點：全排列枚舉+計算幾何各種基礎操作 ---- * $N$ 那麼小，意圖讓大家暴力枚舉 * 暴力枚舉然後判斷是否是簡單多邊形，再把所有事簡單多邊形的面積排序取第 $k$ 小即可 * [參考程式碼](https://gist.github.com/dreamoon4/3ec550a336e0b1969e3c77f7c931c1df) --- ## A. 歷史模擬器 ### 首殺： hank55663 (15 分鐘) ---- * 考察知識點：並查集 ---- * 怎麼看都是個並查集問題，尤其是子題二 * 實際上所有操作都可以靠並查集解決 * 有一個點脫離的時候，直接把它當作新的點即可。 * [參考程式碼](https://gist.github.com/dreamoon4/44fc416d5c3b395654909635f3db41c6) --- ## E. 日式燒肉店 ### 首殺： abc864197532 (24 分鐘) ---- * 考察知識點：線段樹+掃描線 ---- * 就是個經典的線段樹+掃描線練習題 * 先做座標轉換：$(x, y) -> (x + y, x - y)$ * 問題變為邊長不超過 2k 平行於 xy 軸的正方形裡至多有幾個點 * [參考程式碼](https://gist.github.com/dreamoon4/a96848fdd538a14805cbe3edae2bc05d) --- ## C. 子集問題 ### 首殺： hank55663 (56 分鐘) ---- * 考察知識點：折半枚舉+二分搜+細心 ---- * $N \le 42$，意圖讓大家使用折半枚舉 * $L = R$ 是折半枚舉經典題，而 $R - L < 10^5$ 就讓大家八仙過海了 * [參考程式碼](https://gist.github.com/dreamoon4/85b5793bddece68315943bbefcc9d197) --- ## D. 賴床極限 ### 首殺： 8e7 (69 分鐘) ---- * 考察知識點：最短路 ---- * 誰說一定要從起點走到終點，我偏要從終點走回起點！ ---- * 每條邊的 cost 必須走到該點時再計算，可使用二分搜計算比較無腦 * [使用二分搜的參考程式碼](https://gist.github.com/dreamoon4/545f37acba5c70d97d540a1a2dbac514) * [沒使用二分搜的參考程式碼](https://gist.github.com/dreamoon4/9afd3c7acc53d1562d737672c007a250)