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$ 即可算出。