# AA 競程 2022 TOI 模擬賽第一場
---
* 賽前難易度猜測
D < C < A < E < B
* 實際每題 AC 人數
A：20 人
B：1 人
C：21 人
D：38 人
E：0 人
---
## D. 最大巔峰數量
### 首殺：EJam (11 分鐘)
----
* 子題 1 參考做法：
* 暴力枚舉哪個數被移除
* [參考代碼](https://gist.github.com/dreamoon4/21b4caeceeb30501a260fedb714b5f36)
----
* 滿分參考作法：
* 觀察到只有移除「達到巔峰」的比賽紀錄能改變「達到巔峰」的次數，且移除後，可能產生新的「達到巔峰」的數量不會太多。
* [參考代碼](https://gist.github.com/dreamoon4/c20312e39b402acc810be55ff72cc9a3)
----
* 這麼簡單題題為什麼自己怎麼寫卻一分都拿不到！？
* 可以使用暴力對拍找自己會錯的測試資料，找到後就很容易找出 Bug 了
---
## C. 排隊
### 首殺：alvingogo (24 分鐘)
----
* 子題 1 參考做法：
* 定義什麼是「合法的前綴」
* 從前面枚舉每個位置，再由編號小至大枚舉每個位置要站誰，看看是不是個合法前綴
* 這是多數「字典序最大/小」相關問題通用解法
----
* 滿分參考做法：
* 和子題 1 類似，一樣要枚舉每個位置，但想辦法優化決定每個位置能站的人的最大編號的時間。
* 觀察到沒舉過位置程中，一個人一但可以被選擇後，之後的位置也一定能被選擇。
* 可做到 $O(n log n)$
* [參考代碼](https://gist.github.com/dreamoon4/53103b37d0d2d0625501378d0fcb4fc1)
---
## A. Functional Graph
### 首殺：syl123456 (16 分鐘)
----
* 子題 1, 2 參考做法：
* 暴力枚舉每條鞭的方向，在檢查是不是一個 functional graph 即可。
* 時間複雜度為 $O(2^n)$。
* 子題 1 是用來讓大家方便檢查自己是不是錯在無解的 Case。
* [參考代碼](https://gist.github.com/dreamoon4/c65e69fec82fc34290775cd0fb833f50)
----
* 滿分參考做法：
* 觀察到若一個點度數只有 1，我們就能知道該點連出去的那條邊方向必須向外，於是給定完方向後就可以把這條邊移除。
* 類似於 BFS 類型的拓撲排序做法。
* 當不存在度數為 1 的邊時，理應每個點度數都是 2，也就是很多 Cycle。
* 每個 Cycle 的邊的方向只有兩種選擇，選字典序比較小的那個即可。
* [參考代碼](https://gist.github.com/dreamoon4/49dfc89d6851af1407ad28bfd2d5f797)
----
* 推薦拓撲排序學習資源：https://csacademy.com/lesson/topological_sorting
---
## E. 圓桌遊戲
### 首位拿到最高分(50 分)：WiwiHo (121 分鐘)
----
* 總之題意就是要把一個環狀數列分成三個區間，滿足題目所說所有條件
----
* 子題 1 參考作法：
* 用雙指針預處理每個位置當區間左界及右界時，另一界最遠能到哪。
* 接著我們只要枚舉三個區間中的一個區間(共 O(n^2) 個)，就可以 O(1) 計算剩下兩個區間有幾種選擇。
* 每個組合會算到三次，所以答案除以 3。
* 推薦雙指針學習資源：https://codeforces.com/edu/course/2/lesson/9
----
* 滿分解參考作法：
* 再套一層雙指針，可壓到 O(n)。
* O(n) [參考代碼](https://gist.github.com/dreamoon4/13ce2bffe54e67d7ca3c58d2aa75ab16)
* 怕細節太複雜，可以用 BIT 輔助，得到一個時間複雜度 $O(n log n)$ 的作法，仍可拿滿。
* 子題 2, 3 只是唬人用的。
---
## B. 飛行遊戲
### 首殺：syl123456 (172 分鐘)
----
* 子題 1 參考作法：
* 基礎 dp 題，狀態是三維 $O(n^3)$， dp[pos][h][k] 代表在座標 pos、高度為 h、血量剩 k 時最高得分。
* 轉移 O(1)。
* 要小心高度可能達到範圍的兩倍
* [參考代碼](https://gist.github.com/dreamoon4/d98af4540a8bfd9dabc75664208aa977)
----
* 滿分解參考作法：
* 用貪心的概念，可改寫狀態量為 $O(n^2)$，定義 dp[i][k] 代表在第 i 個位置的裝置時剛好在該裝置高度，且生命值剩 $k$ 時最高得分。
* 轉移 O(n)。
* [參考代碼](https://gist.github.com/dreamoon4/5c1433d805dbd9df1dcfb31a3ce6afdf)
{"metaMigratedAt":"2023-06-16T19:53:58.084Z","metaMigratedFrom":"YAML","title":"AA 競程 2022 TOI 模擬賽第一場","breaks":true,"slideOptions":"{\"transition\":\"fade\",\"parallaxBackgroundImage\":\"https://i.imgur.com/jtMhsLP.png\",\"parallaxBackgroundHorizontal\":200,\"parallaxBackgroundVertical\":200}","description":"賽前難易度猜測D < C < A < E < B","contributors":"[{\"id\":\"ec58fb73-fce8-4e38-b318-d00e84653449\",\"add\":2490,\"del\":8}]"}