AA 競程 2022 TOI 模擬賽第一場

賽前難易度猜測
D < C < A < E < B
實際每題 AC 人數

A：20 人
B：1 人
C：21 人
D：38 人
E：0 人

D. 最大巔峰數量

首殺：EJam (11 分鐘)

子題 1 參考做法：
暴力枚舉哪個數被移除
參考代碼

滿分參考作法：
觀察到只有移除「達到巔峰」的比賽紀錄能改變「達到巔峰」的次數，且移除後，可能產生新的「達到巔峰」的數量不會太多。
參考代碼

這麼簡單題題為什麼自己怎麼寫卻一分都拿不到！？
- 可以使用暴力對拍找自己會錯的測試資料，找到後就很容易找出 Bug 了

C. 排隊

首殺：alvingogo (24 分鐘)

子題 1 參考做法：
定義什麼是「合法的前綴」
從前面枚舉每個位置，再由編號小至大枚舉每個位置要站誰，看看是不是個合法前綴
這是多數「字典序最大/小」相關問題通用解法

滿分參考做法：
和子題 1 類似，一樣要枚舉每個位置，但想辦法優化決定每個位置能站的人的最大編號的時間。
觀察到沒舉過位置程中，一個人一但可以被選擇後，之後的位置也一定能被選擇。
可做到 \(O(n log n)\)
參考代碼

A. Functional Graph

首殺：syl123456 (16 分鐘)

子題 1, 2 參考做法：
暴力枚舉每條鞭的方向，在檢查是不是一個 functional graph 即可。
時間複雜度為 \(O(2^n)\)。
子題 1 是用來讓大家方便檢查自己是不是錯在無解的 Case。
參考代碼

滿分參考做法：
觀察到若一個點度數只有 1，我們就能知道該點連出去的那條邊方向必須向外，於是給定完方向後就可以把這條邊移除。
類似於 BFS 類型的拓撲排序做法。
當不存在度數為 1 的邊時，理應每個點度數都是 2，也就是很多 Cycle。
每個 Cycle 的邊的方向只有兩種選擇，選字典序比較小的那個即可。
參考代碼

推薦拓撲排序學習資源：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) 參考代碼
怕細節太複雜，可以用 BIT 輔助，得到一個時間複雜度 \(O(n log n)\) 的作法，仍可拿滿。
子題 2, 3 只是唬人用的。

B. 飛行遊戲

首殺：syl123456 (172 分鐘)

子題 1 參考作法：
基礎 dp 題，狀態是三維 \(O(n^3)\)， dp[pos][h][k] 代表在座標 pos、高度為 h、血量剩 k 時最高得分。
轉移 O(1)。
要小心高度可能達到範圍的兩倍
參考代碼

滿分解參考作法：
用貪心的概念，可改寫狀態量為 \(O(n^2)\)，定義 dp[i][k] 代表在第 i 個位置的裝置時剛好在該裝置高度，且生命值剩 \(k\) 時最高得分。
轉移 O(n)。
參考代碼

AA 競程 2022 TOI 模擬賽第一場

{"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}]"}

changed 2 months ago 466 views
owned this note