暑假集訓(xùn)CSP提高模擬7

1. T1 Permutations & Primes

   考慮只有包含 \(1\) 的區(qū)間有用。

   因為 \(2,3\) 都是質(zhì)數(shù)，考慮將其放在兩邊，就一定可以將除了整個排列以外所有區(qū)間都是 \(2\) 或 \(3\)。

   我 SB 粘錯代碼狂掛 \(100pts\) 不止。

2. T2 樹上游戲

   眾所周知，可以二分答案。

   二分完自底向上判斷貪心即可。

   賽時狂調(diào)兩小時不止。

3. T3 Ball Collector

   首先考慮對 \(a_i,b_i\) 建邊。

   考慮每個連通塊，設(shè)其節(jié)點數(shù)為 \(s\)，當(dāng)其是一顆樹時最多選 \(x-1\) 個，否則是 \(x\) 個。

   考慮有回溯，可撤銷并查集維護(hù)即可。

4. T4 滿穗

   設(shè) \(q_i\) 表示負(fù)數(shù)前綴和，\(p_i\) 表示正數(shù)前綴和。

   首先推式子：

   \[i<j,s_i<s_j\Leftrightarrow\tfrac{p_i}{P} - \tfrac{q_i}{Q} < \tfrac{p_j}{P} - \tfrac{q_j}{Q}\Leftrightarrow\tfrac{Q}{P} < \tfrac{q_i - q_j}{p_i - p_j} \]

   發(fā)現(xiàn)最后是斜率形式，可以直接建出上凸包二分。

   因為有修改，不能直接建凸包，可以分塊，考慮修改一個點，這個點前面的塊不會變，后邊的斜率也不變，只是會平移，不影響二分，只有塊內(nèi)要改。

   直接暴力重構(gòu)，最后對所有塊取 \(\max\) 即可。