AA 競程 2023 TOI 模擬賽初賽 I

# AA 競程 2023 TOI 模擬賽初賽 I --- * 賽前難易度猜測 A < E < D < C 子題 1 & 2 參考做法 * 維護以下兩個資料結構： 1. 每個人當前被多少間學校錄取並且尚未放棄 2. 記錄每間學校當前的錄取名單 * while 至少有一個人被兩間以上學校錄取，then 讓其中編號最小的學生放棄並模擬 * 時間複雜度 $O(N^2)$ ---- #### 滿分解 * ~~我就是不要放最直覺的 priority_queue 解 :(~~ * 維護一個變數 x 代表編號小於 x 的人目前都沒有同時錄取兩間學校 * 若編號 x 錄取兩間學校，模擬他放棄一間學校後，遞迴檢查遞補的人是否同時錄取兩間學校，並分兩種情況： 1. 遞補的人編號比 x 小，下一個放棄的人就是這個遞補的人，並再遞補一個人地會做下去 2. 遞補的人編號比 x 大，那就不理他，因為之後會再檢查到他 ---- * 時間複雜度：$O(N)$ * [參考程式碼](https://gist.github.com/dreamoon4/21ff2b288d25de37d3ca4bb47e89df6a) --- E. 大聲說討厭的勇氣首殺： chrislaiisme (32 min) ---- * ~~dreamoon 沒有說他討厭的東西是 Leetcode~~ ---- #### 子題 1 * 選擇一：動手暴力構造所有 $y \le 8$ 的測試資料 * 選擇二：枚舉 $2^y$ 種可能的 1 和 null 的序列 ---- #### 子題 2 * ~~雖然覺得多數人會做子題 2 就會做子題 3，但還是設了這個子題~~ * 可把 null 想像成是一個沒有子節點的節點，數字 1 是有兩個子節點的節點 * 可想像依序檢查每個節點時就是一個 bfs 拜訪二元樹每個節點的過程，最初先 push 樹根進 queue，接著每拿一個節點，就把它的子節點也 push 進 queue 裡 ---- * 可能的DP作法：令 dp[i][j] 儲存一個布林值，代表只考慮到從 queue 中拿出第 i 個節點時並 push 它的子節點之後，queue 裡是否有可能恰有 $j$ 個節點 * 轉移就是枚舉拿出的節點是數字 1 還是 null 兩種情形 * 若 dp[x-1][y-x] 是 true，就代表節點 x 的左子節點可以是 y ---- #### 子題 3 * 觀察到拿出的節點是 1，queue 裡節點數會增加 1，拿出的節點是 null，queue 裡節點數就會減少 1 * 這和括號匹配的概念好像啊！ * 我們只在乎節點 x 之前有幾個 1，幾個 null。 * 可暴力枚舉 x 之前有幾個 1，知道幾個 1 後，可 O(1) 計算 x 的左子節點編號 * x 之前 1 的數量不可少於 null 數量 --- D. 天下沒有不散的宴席首殺： becaido (24 min) ---- #### 子題 1 * 會每個詢問暴力做就可能分，相信寫得出 [CSES1192 Counting](https://cses.fi/problemset/task/1192) Rooms 的人都寫得出來(~~會不會寫出 bug 檢查很久我就不知道了~~) ---- #### 子題 2 * 相信資深競程選手看到每次修改一點並回答的問題，直覺反射就是把操作倒回來考慮 * 在今年 ioicamp 講義裡稱之為「時光倒流」 * 於是可以使用 DSU 維護每個學生屬於哪個連通元件，每個詢問暴力計算每個連通塊度數乘積 * 預期時間複雜度 $O(N^2 \alpha(N))$ ---- #### 子題 3 * 重要觀察：每個學生至多只有 ${20 \choose 1}+{20 \choose 2}=210$ 個朋友，且可以快速算出他的朋友的所有可能個性。 * 不重要的觀察：維護答案的過程需要計算乘法反元素，但可發現我們只會用到 $1 \sim 210$ 的乘法反元素，預處理後，使用這些直只需要 O(1) * 令 $B=20$ 代表 $a_i$ 位元數，時間複雜度為 $O(B^2N\alpha(N))$ --- C. 圓桌舞事首殺： Fysty (172 min) ---- #### 子題 1 * 由於沒有其他人和第 $n$ 個人同學校，我們可以把第 $n$ 個人忽略，就不再是環狀了 * 設計 dp 狀態 dp[i] 代表只考慮前 $i$ 個人，且第 $i$ 個人是他所在的學校坐最右邊的人的方法數 --- * 轉移式為: $dp[i]=\sum\limits_{j=0}^{i-1}dp[j] \cdot [ 區間 [j+1,i] 的學生可以是同個學校]$ * 暴力 $O(N^2)$ 轉移，總時間複雜度 $O(N^3)$ 即可通過 ---- #### 子題 2 case 1: 存在至少一個 $a_i \ne 0$ * 找到任一個滿足 $a_j \ne 0$ 的 $j$ * 枚舉第 $j$ 個人和哪個人些人同所學校，至多有 $n$ 種情形，枚舉完後，就變成子題 1 的情形了。 * 但要小心有些序列會被重複算到，但可證明重複算到的只有 $a$ 全是同一個數字(令其為 $t$)的情形，且恰重複算到 $t-1$ 次 * 改用 $O(N^2)$ 計算子題 1，此題可用時間複雜度 $O(N^3)$ 解出 ---- case 2: $a$ 全部都是 $0$ * 考慮兩個學生是不是不同學校的分界，共有 $2^n-n$ 種 * 再扣掉每位學生的回答都一樣時多算的數量 ---- #### 子題 3 子題 1 的 DP 可利用前綴和優化為 $O(N)$，故可用總時間複雜度 $O(N^2)$ 解出此題 --- B. 青椒大戰 2 - 惡夢再臨首殺： alvingogo (171 min) ---- #### 子題 1 * 參考作法：暴力遞迴模擬，每進入一次函式時，枚舉錄取兩間學校的編號最小的那個人要放棄哪間學校，時間複雜度為 $O(2^N)$。 ---- #### 子題 2 * $O(N^4)$ 複雜度即可通過 * 相信有無數種做法 * dreamoon 想到的作法是使用 dp，狀態設計為： * dp[i][j][k] 代表在清大錄取名單裡排名最後的是第 $i$ 名，在交大錄取名單裡排名最後的是第 $j$ 名，並且目前恰有 $k$ 個人同時出現在兩所學校的錄取名單中 ---- #### 子題 3 * 存在 $O(N^2)$ 的 DP 解或枚舉兩個學校最終錄取名單的最後一個人是誰的數學解可解這題 * 但這裡篇幅太小了，我寫不下 ---- #### 子題 4 * 子題 3 枚舉兩個學校最終錄取名單的最後一個人是誰的數學解可以用雙指標優化，做到 $O(N)$ * ~~雖然這裡篇幅夠大，但我懶得寫了~~ * 直接參考 [此連節](https://hackmd.io/@aacp/rJpe6kHai)，包含完整證明