MOIC 2025 簡要題解

DengDuck · 2025-04-05 16:42:24 · 个人记录

難度：藍藍紫，綠黃藍。

Day 1 T1

題意

• 給你 n 個數字，生成對應的 BST。
• 求這個 BST 的最大對稱二叉樹。

解法

• 排序之後直接建立笛卡爾樹。
• 實際數據弱，可以暴力插入，或者 DS+分治。
• 等價於 NOIP 的對稱二叉樹，哈希或者 Manacher 解決。

Day 1 T2

題意

• 有一個數軸。
• 有 n 個人，第 i 個人希望 S_i\to T_i，滿足 S_i\leq T_i。
• 有一輛從左往右開的公交車，請問最少要有多少位置才能滿足 k 個人的需求。

解法

• 二分答案是顯然的。
• 每個人上車之後，我們只關心什麼時候下車。
• 反悔貪心秒殺。

Day 1 T3

題意

• CF818G Four Melodies.

解法

• 考慮費用流，給源點一個大小為 4 的流量即可。
• 直接建圖會超時，考慮優化建圖。
• 建立多個虛點，高速公路。
• 之後邊數數量變為 \mathcal O(n)，可通過。

  Day 2 T1

題意

• 交互題，有 n 個長度為 8 的八進制數字，有兩種操作：
  • 查詢兩個數字的同一位的大小關係（大於小於等於）。
  • 交換兩個數字。
• 在 k 次操作內把這個數組排好序。
• n\leq 800,k\leq 60 n

解法

• 樸素快排和歸併沒有卡。
• 如果知道了大小排名，可以在 n 步內排好序，沒必要邊排序邊交換。
• 考慮排序一個區間，隨機選一個數字，然後跟所有數字比較，看 LCP 和 大小關係，可以分出 15 種類型。
• 分治下去，可以證明時間複雜度。

Day 2 T2

題意

• 給你一個長度為 n 的數組 A，有 Q 個操作，分為三種：

  • 給出 L,R 查詢區間 [L,R] 的 \sum A_i 和 \sum [A_i>0]。
  • ### 解法

• 主席樹板子。

• 離散化也行。

  Day 2 T3

題意

• 有 n 個方格，每個方格有一個分數，然後有 k 只小青蛙，一開始他們在 [1,k],你希望他們跳到 [n-k+1,n]。

• 每次你操控最左邊的青蛙跳 i\in [1,S] 步，要求必須跳到空方格上，然後你獲得方格的分數並獲得一個跳躍的分數 B_i。

• 求最小分數。

• ### 解法

• 注意到青蛙之間的距離不會超過 8，所以我們考慮狀壓，設 F_{i,j} 表示最左邊的青蛙在 i，然後 [i,i+7] 的方格佔領情況。

• 無腦轉移做完了，如果被卡常可以考慮預處理有效的狀態。