AA 競程 2023 TOI 模擬賽 初賽 II

子題 1

• \(H = M = 3\) 時，只有 \(9\) 種不同的詢問，可以手算答案。
• 說不定你能在手算答案的過程中觀察到一些事情

子題 2

• 此子題 \(H \le 24, M \le 60, Q \le 10\)
• 允許 \(O(HMQ)\) 時間複雜度的解，暴力模擬兩手錶一天內有多少分鐘是另一個手錶的重排列即可
• 據說 AA 競程 Level 1 入學測驗很多人寫不出關於時間計算的題，所以 dreamoon 才想到這題的 idea，測測看到底是全世界都不會寫，還是只有參加入學測驗的人才不會寫 :(

子題 3

• 觀察到就算兩組詢問裡詢問的時間組合不同，但只要兩個時間的「差」相同，答案就一樣，於是只需要暴力把 \(H \times M\) 種時間差的答案先算出來儲存起來，每個詢問 \(O(1)\) 回答即可解出此子題

子題 4

• 對於手錶 A 的每個顯示時間 ab:cde，至多只有 120 種合法的顯示時間是它的排列，所以可用 \(O(120HM)\) 的時間複雜度算出每個顯示時間在哪些「差」值對答案有貢獻
• 有上過 AA 競程 2022 秋季實作班的同學，可能會想起作業裡有若干題都是此技巧的練習題

• 令 \(s = \sum\limits_{i=1}^N a_i\), \(full\_cnt = \lfloor\frac{s}{C}\rfloor\), \(r = s - k \cdot C\)
• 要達成敘述裡的目標，必須恰有 \(full\_cnt\) 個箱子藥水是滿的，且若 \(r\) 不為 \(0\)，必須恰有一個箱子恰有 \(r\) 罐藥水

子題 1

• 利用貪心的概念即可解出

• 此子題 \(Q = r = 0\)，情況很單純，只要考慮哪些箱子是滿的，答案就是會 \(full\_cnt \times C\) 減去要放滿藥水的那些箱子原有的藥水總和，於是選藥水最多的 \(full\_cnt\) 個箱子放滿藥水即可

子題 2

• 仍然是貪心

• \(Q \le 10\) 允許每個詢問各自解決
• 仍然是原有藥水最多的那 \(full\_cnt\) 個箱子要放滿，其餘的箱子中，原有藥水數量最多的那個讓它邊為放 \(r\) 罐藥水是最佳解
• 要想清楚放 \(r\) 罐藥水的箱子原有的藥水數量對答案的影響

子題 3

• 雖然 \(Q\) 很大，但 \(C \le 100\)，所以允許使用 \(O(QC)\) 的時間複雜度解決
• 用 cnt[x] 儲存恰有 \(x\) 灌藥水的箱子有幾個，就可以 \(O(C)\) 計算藥水數量最多的 \(full\_cnt\) 個箱子的藥水總和，以及剩餘的最多藥水的箱子有多少藥水。

子題 4

• 此題是 STL 的經典題型
• 相信在競程圈打滾一年以上的人都做過相關題

• 什麼？你沒做過？

• 去刷 CSES 吧！
• 此題作法和 CSES1076 Sliding Median 和 CSES1077 Sliding Cost 一模一樣

• AA 競程 Level 1 有教一種 USACO GUIDE 裡也沒介紹的可解此類題型的特殊作法唷 ^.<

子題 1

• 枚舉唯一的一次紀錄是發生在第幾圈，可以 \(O(M)\) 的時間複雜度解出

子題 2

• 和子題 1 的差別是 \(M\) 很大
• 觀察到唯一一次的紀錄發生在第幾圈會是最佳解這件事可三分搜即可解出

子題 3

• \(N \le 50, M \le 500\)，允許時間複雜度 \(O(NM^2)\)
• 可使用 dp，狀態為 dp[i][j] 代表第 \(i\) 個紀錄是發生在第 \(j\) 圈的時候

子題 4

• 此題是二分搜+貪心經典題型
• 相信在競程圈打滾一年以上的人都做過相關題

• 什麼？你沒做過？
• 去刷 CSES 吧！

• 這題甚至連刷 APCS 考古題都能遇到兩題同概念的題目

1. APCS 2017 年 3 月 P4 基地台
2. APCS 2022 年 1 月 P4 牆上海報

你現在是不是在想：「這我也都知道，但就是 AC 不了 : (」

• 你並不孤單，驗題者也是全軍覆沒，回家多練練實作和 debug 吧 : )

子題 1

• 令 \(d_N = 0\), \(a_i = a_N + c_i \cdot d_i\)
• 若 \(a_i > a_N\) 那麼 \(c_i = 1\)，否則 \(c_i = -1\)
• 暴力枚舉 \(c_i = 1\ or\ -1\)，共有 \(2^N\) 種可能
• 於是我們就知道 \(N \times a_N + \sum\limits_{i=1}^{N} c_i \cdot d_i = S\)
• 解出 \(a_1 \sim a_N\) 後檢查是否每個數都是非負整數，若都滿足則找到一組解

子題 2

• 利用 \(d_i \le 500\)，可使用類似 01 背包的作法，對於相同的 \(\sum\limits_{i=1}^N c_i \cdot d_i\) 值，算出最大的 \(\min\limits_{i=1}^N c_i \cdot d_i\) 的值
• 時間複雜度為 \(O(N \times \sum\limits_{i=1}^Nd_i)\)

子題 3

• 此題記憶體限制和其他題不同就是此子題的提示
• 背包問題+更寬鬆的記憶體限制 => bitset 優化 (?)
• 但能用 bitset 優化的DP題儲存的值應該會是布林值呀

不防假設 \(d_N \le d_{N-1} \le \ldots \le d_1\)

• 枚舉序列 \(c_i\) 中滿足 \(c_j=-1\) 的最小的 \(j\)，即可知道 \(\min\limits_{i=1}^N c_i \cdot d_i = -c_j\)
• 枚舉到 \(j\) 時，若 \(\sum\limits_{i=1}^N c_i \cdot d_i\) 可能為 \(x\)，那麼轉移到 \(j-1\) 時，可選擇 \(c_j\) 維持在 \(-1\) 或變為 \(1\)，而 \(c_{j-1}\) 必須從 \(1\) 變為 \(-1\)，故 \(\sum\limits_{i=1}^N c_i \cdot d_i\) 的可能值有 \(x+2d_j-2d_{j-1}\) 或 \(x-2d_{j-1}\) 兩種。

子題 4

• \(d_i\) 的範圍這麼大，這不是背包可以解的吧 : (

回顧此題要滿足的兩個條件：

• \(N \times a_N + \sum\limits_{i=1}^{N} c_i \cdot d_i = S\)
• \(a_N + \min\limits_{i=1}^N c_i \cdot d_i \ge 0\)

移項得：

• \(a_N = \frac{S - \sum\limits_{i=1}^{N} c_i \cdot d_i}{N}\)
• \(a_N \ge -\min\limits_{i=1}^N c_i \cdot d_i\)
  \(\Rightarrow\)
  \(\frac{S - \sum\limits_{i=1}^{N} c_i \cdot d_i}{N} \ge -\min\limits_{i=1}^N c_i \cdot d_i\)

• 也就是說，我們是希望在 \(\sum\limits_{i=1}^{N} c_i \cdot d_i \equiv S \pmod N\) 的情況下，\(\sum\limits_{i=1}^{N} c_i \cdot d_i\) 的值盡可能小

• dp 狀態可改成 \(dp_j[r]\) 代表 \(\min\limits_{i=1}^N c_i \cdot d_i = -d_j\) 且 \(\sum\limits_{i=1}^{N} c_i \cdot d_i \equiv S \pmod N\) 時，\(\sum\limits_{i=1}^{N} c_i \cdot d_i\) 的最小值

再複習一次：

• 令 \(s = \sum\limits_{i=1}^N a_i\), \(full\_cnt = \lfloor\frac{s}{C}\rfloor\), \(r = s - k \cdot C\)
• 要達成敘述裡的目標，必須恰有 \(full\_cnt\) 個箱子藥水是滿的，且若 \(r\) 不為 \(0\)，必須恰有一個箱子恰有 \(r\) 罐藥水

子題 1

• 此題在 CSES 也有類似題

• 是這題：CSES1074 Stick Lengths
• 想像成每罐藥水所在箱子編號就是 CSES 此題中棍子的長度，題目變為要讓 \(s\) 根棍子在操作完後被分成 \(full\_cnt\) 組棍子，每組都是由 \(C\) 根長度一樣棍子組成，且 不同組棍子必須長度相異

• 最佳解會發生在由小到大每 \(s\) 根棍子一組的情形，且每組棍子的最終長度就是該組棍子的中位數
• \(C\) 是奇數時，每組的中位數值一定不同
• \(C\) 是偶數時，中位數全選長度第 \(\frac{C}{2}\) 小的那一個能保證不存在兩組棍子長度相同
• 證明留給大家 :P

• 此子題對應的棍子數很少，排序即可暴力解出

子題 2

• 此子題對應到棍子問題後，必須有某組棍子數恰為 \(r\) 根
• 最佳解中，一定存在某種中位數的取法能滿足每組棍子長度都相異
• 此子題測試資料範圍仍可排序後暴力枚舉 \(r\) 根棍子的那組是在哪後解出

子題 3

• 和子題 \(2\) 相比，棍子數變多，純用枚舉的會超時，但可發現枚舉那 \(r\) 根棍子的組合是在哪時，會有大量重複的計算
• 可用前綴 DP 及後綴 DP 解出。也就是說，使用 DP 計算出對於所有 \(i\)，最短/最長的 \(i \cdot C\) 根棍子恰都是連續 \(C\) 個一組時需要多少次操作

子題 4

• 此子題 \(C\) 的值變大了，無法每瓶藥水分開考慮，但用點數學仍可使用和子題 \(2\) 一樣的方法 \(O(N^2)\) 解出

子題 5

• 此子題不僅 \(C\) 變大，\(N\) 也變大了，但結合子題 3 和子題 4 的方法即可解出

• 這題可能對某些人來說不難猜到作法，但可能寫整整 \(3\) 小時都不一定寫得出來

• One More Time
• 回家多練練實作和 debug 吧 : )