# $\text{2019 NHSPC}$ 全國模擬賽 心得

[題目](https://brian.su/r/pre-nhspc2019-problems) $\mathcal{AND}$ [記分板](https://ranking.brian.su) $\mathcal{AND}$ [題解](https://hackmd.io/@briansu/BkAdtSP6B)

感謝籌備組的大家舉辦了這麼好的比賽 :heart:

先來說說結果吧：$\text{Rank 10/77, 3AC, 442.59/800}$

---

開場時按照之前定下的策略不從 $\texttt{pA}$ 開始，反而從 $\texttt{pD}$ 或 $\texttt{pE}$ 開始看，看到 $\texttt{pE}$ 叫做 AI-777 就嚇到了w，直接改成從 $\texttt{pD}$ 開始看。

$\texttt{pD}$ 是個互動題，看的出來是用二分搜做，不過賽前給自己的 SOP 是先拿部份分再去想滿分解，特別是這種容易錯的題目，就先交了暴力的 $14$ 分跟其中一維二分搜的 $34$ 分。在拿到 $48$ 分之後，把 $\texttt{subtask 2}$ 的作法直接搬到 $\texttt{subtask 3}$ 裡面，當時腦袋炸裂算不出來二分搜的次數還以為可以拿滿= =，最後只有 $54$ 分才發現詢問的次數比自己想的還多一倍。

- $\text{50 min passed, scored 54/800.}$

這時候已經過了 $50$ 分鐘，我卻還只有 $54$ 分，於是從這個時候開始就先做 $\texttt{pA}$, $\texttt{pB}$。
$\texttt{pA}$ 看到的時候想說應該是梗題，自己手算一下發現如果有 $a_{i,j}=a_{i+1,j-1}$ 就可以構造出一條路徑ww，$\texttt{pB}$ 看以來就是MST的裸題？總之交上去就都過了。這時已經過去 $68$ 分鐘，拿到了 $254$ 分。一邊想說這種進度太慢了一邊開 $\texttt{pC}$，結果發現自己想不到怎樣會有最佳解，慘。= =

$\texttt{pC}$ 先直接交了全輸出 $1$ 的程式拿了 $\texttt{subtask 2}$ 的一半分數，又跑回去看 $\texttt{pE}$，並把 $K=0$ 的子題拿了。

- $\text{90 min passed, scored 282/800.}$

又滾回去看 $\texttt{pC}$，並把 $\texttt{subtask 1&3}$ 用暴力把詢問為 $0$ 的區間做出來，寫著寫著就想到全部直接暴力 $\text{AND}$ 一定是合法解，丟上去 $\mathcal{O}(NQ) \approx 10^{10}$ 竟然拿到了 $40.5$ 分ww，本來已經做好準備全部 $\texttt{TLE}$ 的說ww

順便把 $\texttt{subtask 1}$ 的 $\mathcal{O}(2^N)$ 枚舉寫出來，又拿了 $8.5$ 分，認為自己已經沒救了，於是就往後去看 $\texttt{pF}$。

- $\text{124 min passed, scored 318/800.}$

看到 $\texttt{pF}$ 的題敘跟子題限制和配分，我瞬間感覺世界又亮了起來，並下定決心一定要拿到這 $57$ 分。其實做也很簡單，$\texttt{subtask 1}$ 是先 sort 完再 2-pointer，$\texttt{subtask 2}$，因為重量只有 $200$ 種，直接用個陣列存下來，每次修改再用 $\mathcal{O}(200)$ 查詢。

看完 $\texttt{pG}$ 完全沒想法，跟去年的題目一樣qaq，難道其實 $\texttt{pG}$ 才是最難拿分的題目？

$\texttt{pH}$ 也照往常只想的到 $\texttt{subtask 1}$ 的暴力，雖然題目有部份測資要求在線，但蒟蒻如我也想不到有什麼離線的解法，便撈完 $10$ 分就放棄了。

- $\text{180 min passed, scored 385/800.}$

我在賽中預測的分數線長這樣：
- TOP3. 580+
- TOP10. 460+
- TOP20. 375+
- TOP1/2 200+

雖然已經(應該)有三等獎了，但我覺得剩下的題目我都做不出來，只能慢慢等別人超越，半放棄般的重新審視題目，並決定應該放棄 $\texttt{pF, pG, pH}$。

接下來的一個小時都在鑽研 $\texttt{pC}$ 跟 $\texttt{pD}$，$\texttt{pD}$ 寫累了就去看看 $\texttt{pC}$。看配分可以發現最佳解只需要詢問 $60$ 次，也就是對其中兩邊二分搜，而我目前的作法是對四邊都二分搜，加上詢問面積總共 $121$ 次。在調整輸出時又思考到其實可以刪掉其中一邊的詢問，改用另一邊的長跟面積求出來，詢問次數可以降低到 $91$ 次。

想 $\texttt{pC}$ 的 $\texttt{subtask 2}$ 的時候發現其實就是常見的工作排程問題。
> 取最少的點使每個線段都至少覆蓋一個點

按右界排序放 $1$，再跟之前的暴力綜合下去，終於取得了分數上的進展。

- $\text{240 min passed, scored 404.59/800.}$

看著 $\texttt{pC}$ 的 $\texttt{subtask 3}$ 想到了一個極度麻煩的做法，先把所有必須是 $0$ 的點清掉，剩下的再去做工作排程。寫著寫著就想到其實正解應該就是重複做 $30$ 次所有的東西？

於是 $\texttt{pC}$ 就被我分成四個部份：
1. 對每個 bit 單獨判斷
2. 用差分+前綴和統計必須放 $0$ 的區間
3. 從前往後跟從後往前 $\mathcal{O}(N)$ 計算詢問需要改變到哪裡
4. 做排程並將答案 $\text{OR}$ 上 $2^i$

於是就開心 $\texttt{AC}$ 囉！

- $\text{262 min passed, scored 442.59/800.}$

剩下時間在用暴力思考 $\texttt{pE}$，想當然爾，已經做了四個半小時，精神不濟的我也沒辦法 de 出任何 bug 來owo

- $\text{Contest Ended, scored 442.59/800, Rank 10/77}$

---

最後看記分板的時候超緊張又刺激的，我先按 `pgdn` 滾到最下面才一個一個往上滑，看到 $20$ 名左右的分數突然從 $322$ 飆到 $377$，在往上看到第 $15$ 名 $392$，第 $14$ 名 $418$，第 $13$ 名 $432$，第 $12$ 名 $433$，第 $11$ 名 $437$，然後我在第 $10$ 名，超開心der

贏過了好多大神，也見識了劉澈超電的實力，國中就能拿到第 $8$ 名，到時候的選訓營一定能見到面吧～

---

事後看題解的感想：

$\texttt{pA, pB, pC}$ 果然是這樣做呢ww
$\texttt{pD}$ 求長跟寬明明可以詢問一次就好，我為什麼要二分搜找 $a$ qaq
$\texttt{pE}$ dp 式意外的超簡單，只不過賽中完全沒想過是 dp，看來是被前年的 AI-666 影響到了
$\texttt{pF}$ 用數據結構維護 $\texttt{subtask 2}$ 的作法可以到 $\mathcal{O}(Q \lg N)$，不過我還是沒想到？
$\texttt{pG}$ 蒟蒻如我仍然看不懂題解
$\texttt{pH}$ 竟然可以把詢問 $(l, r, L, R)$ 拆成 $(1, r, 1, R) - (1, r, 1, L-1) - (1, l-1, 1, R) + (1, l-1, 1, L-1)$ 來做莫隊，這個想法太精湛了吧 :astonished:

---

事後看別人心得文的感想：

到底為什麼品翔可以騙到 $\texttt{pG}$ 的 $45$ 分啦，把度數為 $1$ 的點拆掉再輸出所有度數 $\ge 4$ 的點是怎樣ww
$\color{purple}{\text{joylintp}}$ 有錄 screencast 喔，想去看的可以到 [他的 youtube](https://youtu.be/KNHQ9yw4Vc8) 觀看
還有紅黑大電神 $\text{t}\color{red}{\text{mwilliamlin168}}$ 的 screencast 喔 [去膜拜吧](https://www.facebook.com/tmwilliamlin168/posts/1045219255817229)

---


###### tags: `心得`