2025 CSP-S 游寄

總體來說，我前半場(chǎng)的失誤都在可接受范圍內(nèi)，后半場(chǎng)因?yàn)樘澬?，著急，以及學(xué)知識(shí)學(xué)死了三個(gè)問題直接爆炸。估分 100 + 100 + 0 + 0 = 200

T1 我做得非常流暢，開考 20 分鐘就切了。

T2 我開始沒反應(yīng)過來 MST 后有用的變會(huì)變成 \(O(n)\) 條，就先跳過了。通讀完 T3 T4 后，發(fā)現(xiàn)還是 T2 最可做。

后來又yy認(rèn)為 \(n=1e5\)，以為 \(O(n2^k\alpha(n))\) 過不了，卡了一會(huì)，不過及時(shí)反應(yīng)過來并且寫了這個(gè)題。

因?yàn)榇a范了少量糖市錯(cuò)誤，大概在開考 1 小時(shí) 50 分鐘的時(shí)候過了大樣例。

前半場(chǎng)范的錯(cuò)，都是可接受的失誤，所以寫完 T2 我的心態(tài)非常好，但接下來的決策可謂是一錯(cuò)到底。

首先我發(fā)現(xiàn)之前 T3 讀錯(cuò)題了，我之前以為可以進(jìn)行多次替換，所以覺得這個(gè)題不可做，但實(shí)則不然。讀對(duì)題意后我又覺得這題非常非常可做（感覺這個(gè)題確實(shí)容易給人這樣的錯(cuò)覺呀）。我又盲目自信地認(rèn)為我字符串學(xué)的比較好，就想著一定要寫 T3 正解。但事實(shí)上我只對(duì) SAM 比較熟悉。這就是我范的最大的決策錯(cuò)誤。

因?yàn)檫@個(gè)題和字符串匹配有關(guān)，我就下意識(shí)的認(rèn)為此題可以被 SAM 水掉。于是我先畫了大概 15 分鐘回憶 SAM 并且打了個(gè)板子。這也導(dǎo)致我思維被固化，是學(xué)知識(shí)學(xué)得太死了導(dǎo)致的。

我大概想了 30 分鐘，想到了一個(gè)可能正確但是復(fù)雜度是 \(O(|L1|+|L2|\log^3n)\) 的超級(jí)麻煩做法，預(yù)估可能需要 2~3 小時(shí)才能寫+調(diào)出來，于是放棄了。我有花了大概 10 分鐘想了個(gè) \(O(|L2|+q|L1|)\) 的做法，大概有 50 分，這就好寫多了，但是我估計(jì)還是要個(gè) 1.5 個(gè)小時(shí)才能寫+調(diào)出來。

這時(shí)候只有一個(gè)小時(shí)多一點(diǎn)了，我想著 T4 暴力還沒打，必須先想一下 T4，這個(gè)決策算是比較正確的了。

開始因?yàn)闆]看到 \(c_i\) 可以等于 0，以為性質(zhì) A 只需要輸出 \(n!\) ，浪費(fèi)了少量時(shí)間。我繼續(xù)思考性質(zhì) A 如何做，比較自然地想到了一個(gè) \(O(2^n\operatorname{poly(n)})\) 的 dp 做法，發(fā)現(xiàn)可以得 0 分。然后我發(fā)現(xiàn)這個(gè)做法稍加拓展就不依賴性質(zhì) A，于是可以得 20 分。于是我就開始寫了。寫完了還調(diào)了巨久，大概離考試結(jié)束 30 分鐘的時(shí)候調(diào)出來了。

我又想到了 A 性質(zhì)是可以 \(O(\operatorname{ploy(n)})\) dp 做的，具體來說就是把原本記錄“每個(gè)點(diǎn)是否被選的這一維狀態(tài)”改成“還剩多少個(gè)人的 C 大于當(dāng)前未錄用的人數(shù)”即可。但是這個(gè)做法其實(shí)沒有想的非常清楚，并且我覺得我再 T3 投入的沉默成本很高，必須要得點(diǎn)分，于是去寫 T3 的 \(O(|L2|+q|L1|)\) 的寫法?，F(xiàn)在復(fù)盤的時(shí)候發(fā)現(xiàn)這是一個(gè)非常錯(cuò)誤的決策。原因是時(shí)間太少導(dǎo)致我有點(diǎn)失去理智了，整個(gè)人都非常急。

最后的一點(diǎn)點(diǎn)時(shí)間，我當(dāng)然也沒有把 T3 暴力寫完。

考試結(jié)束的時(shí)候，我驚奇的發(fā)現(xiàn)我 T4 的暴力交成了 T2 的代碼。我當(dāng)時(shí)整個(gè)人都懵逼了！然后我光速回憶了一下，想起來我當(dāng)時(shí)是復(fù)制了虛擬機(jī)里面的代碼，然后因?yàn)樾募保阃?strong>虛擬機(jī)的剪貼板和外部環(huán)境的剪貼板不互通！于是直接復(fù)制成了 T2 的代碼，導(dǎo)致 20 分暴力直接蒸發(fā)掉了！血的教訓(xùn)，警示后人：無論如何都要檢查一遍交的代碼是否正確。

這就是我后兩個(gè)小時(shí)得到了 0 分的全部過程。最本質(zhì)的原因是因?yàn)槲以谥坝?xùn)練賽的時(shí)候老是想去沖正解，之后最后不到 5 場(chǎng)比賽我才去想辦法打了暴力，導(dǎo)致我在處理暴力分的經(jīng)驗(yàn)還比不上很多同學(xué)，導(dǎo)致痛失了很多分。這次汲取了經(jīng)驗(yàn)教訓(xùn)，在后期的訓(xùn)練中我會(huì)注重暴力分，希望在 NOIP 能取得好成績(jī)。