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)。
• 參考代碼