---
tags: TOI 模擬賽
---

# AA 競程 2023 TOI 模擬賽(初賽 I) B 題完整題解

#### **重要觀察：若一個組合成立，假設一所學校最後一個被錄取的人是第一所學校的第 $p_1$ 順位($p_1$ 必 $\ge x$)，第二所學校最後一個被錄取的人是 $p_2$ 順位($p_2$ 必 $\ge y$)。且第一所學校前 $p1$ 順位和第二所學校前 $p2$ 順位共通的人數必是 $p1+p2-x-y$(令其為 $K$)。**

----

**引裡 1**: 把遞補學生當成是有序的事件，最後被遞補的人假設是第 $i$ 所學校的第 $p_i$ 順位，那麼它不可能在另外一所學校的前 $p_{3-i}$ 順位。

**證明**：假設最後錄取學校的人是第 $1$ 所學校第 $p_1$ 順位的人，那麼他被錄取時，肯定是同時有兩所學校的資格的，因為他在第 $2$ 所學校不會無緣無故地放棄，得到矛盾。

---

**引裡 2**：不妨假設最後一個被錄取的人是第 $1$ 所學校第 $p_1$ 順位的人，那麼，$p_2$ 可能的範圍和滿足第 $1$ 所學校前 $p_1 - 1$ 個人和第二所學校前 $j$ 個人中恰有 $x+y-1$ 個不重複的人的 $j$ 的範圍是相等的。

**證明**：
**step 1**: 假設現在已經遞補到第 1 所學校第 t1 個人，以及第 2 所學校第 t2 個人，如果 t1 < p1 - 1 且 t2 < p2 那麼，一定有一個人存在某個人同時被兩間學校錄取且還沒放棄，那就任選一人放棄，直到 t1 = p1 - 1 或 t2 = p2。
**step 2**: 如果現在 t1 = p1 - 1 但 t2 < p2，此時仍至少存在某個人同時被兩間學校錄取且還沒放棄，不可能所有滿足這樣條件的人的都是選擇第 2 間學校，如果是的話，就代表最終第 2 間學校錄取的所有人都在前 t2 順位，這與我們假設矛盾。
**step 3**: 如果現在 t2 = p2 但 t1 < p1，那麼肯定存放棄的人都是第一間學校的人，可以一直放棄。

----

**解題演算法**：對於可能的 (p1, p2) 組合分三種情況：
1. 最終被錄取的不可能是 $p_2$
2. 最終被錄取的不可能是 $p_1$
3. 最終被錄取的可能是 $p_1$ 或 $p_2$

可使用雙指針，對於所有 $p_1$，找到最大及最小的 $j$ 滿足第 $1$ 間學校的前 $p_1 - 1$ 順位的人和第二間學校的前 $j$ 個人去重後人數為 $x+y-1$，令其為 $j_s$ 和 $j_b$，若第 $1$ 間學校第 $p_1$ 順位的人 在第二間學校順位 $\le j_b$ ，略過不考慮， 否則，當 $p2 = j_s + 1 \sim j_b$ 時，是第 $1$ 種 case，$p_2=j_s$ 時是第 2 種 case，每個 $p_2$ 的可能值都可以預處理組合數 O(1) 計算出方法數，且需要枚舉的 $p_2$ 值不超過 $O(n)$，這樣子就能分別算出前兩種情況的總數量，第三種的數量只要改成枚舉 $p_2$ 即可算出。
>