# AA 競程 2022 TOI 模擬賽第三場 --- * 賽前難易度猜測 C < B < D < A < E * 實際每題 AC 人數 A：7 人 B：5 人 C：29 人 D：21 人 E：2 人 --- ## C. 小 AA 與多重集 ### 首殺： abc864197532 (11 分鐘) ---- * 相信很多電神看到這題最直覺的作法是持久化資料結構 * 但請注意，此題沒有任何強制在線的條件 * 使用離線作法，就變成一個簡單的 dfs 題了 ---- * [子題 2 參考程式碼](https://gist.github.com/dreamoon4/b9cdf47a501be3d73fba36bb5350a705) * [完整作法參考程式碼](https://gist.github.com/dreamoon4/b120b0d72364b87b716357c080a2337e) --- ## D. 又双叒叕一個區間詢問問題 ### 首殺： Fysty (34 分鐘) ---- * 經典問題 [CSES 1734 Distinct Values Queries](https://cses.fi/problemset/task/1734) 的變形 * 用莫隊算法能拿到 50 分 ---- * [子題 1, 2 參考程式碼](https://gist.github.com/dreamoon4/a3a22384dbba24b915a920e0ef2db8ba) * [完整作法參考程式碼](https://gist.github.com/dreamoon4/39355f479ca59ea875ed0eb45e25b898) --- ## A. 小 AA 的當兵體驗 ### 首殺： fr1234 (62 分鐘) ---- * 一看就知道是中國剩餘定理的相關問題 ---- * [子題 1 參考程式碼](https://gist.github.com/dreamoon4/208c8af2d57d7ecdbb6bc3086afa2963) * [完整作法參考程式碼](https://gist.github.com/dreamoon4/0e8721003acb7a7bb6530055ae512c46) --- ## B. 空襲警報 ### 首殺： syl123456 (69 分鐘) ---- * 子題 1 參考作法：類似背包的作法 ---- * 子題 2 參考作法：數線上的 DP * dp 的狀態設計為：已決定好前 i 個建築物各有幾個人要避難，原本在前 i 個建築物的人還有 k 個人尚未避難/還需 k 個人往前 i 個建築物避難，儲存的值為最小花費。 ---- * 把子題 2 的概念轉乘樹上的 dp 就行了。 ---- * [完整作法參考程式碼](https://gist.github.com/dreamoon4/41f80b4120b52958465b74c864acb3f7) --- ## E. 又一個計算幾何題 ### 首殺： hank55663 (136 分鐘) --- * 真的就只是個極角排序問題，沒什麼困難技巧 ---- * [完整作法參考程式碼](https://gist.github.com/dreamoon4/8d2344700a9057f5d0cb79c6a29a3299) ---- * 附贈 --- 雖然是 $O(N^3)$ 暴力，但也可以在 Codeforces 上拿到 AC 的[參考程式碼](https://gist.github.com/dreamoon4/e59f965f8a7e6bb25f1f3474befc9775) --- # TOI 模擬賽前三名 ---- 1. abc864197532 1233 分 2. Ji_Kuai 1144 分 3. syl123456 1106 分