CSP2025-S 墜機記

省流：未能完成 AK 的心愿。

初賽隨便考的，94 分。

復賽依然是在七高，成功在 14:20 抵達教室，發現我所在的機房電腦性能要爛一些，然而鍵盤要好一些，應該是好事。位置是靠窗，比較好，開考前準備寫板子，但是被制止了。

開考，然后大概看了一眼四個題，發現壓軸題是計數！非常激動。

然后想 T1，我認為這是反悔貪心的狀物，然后就直接往這方面想了，想了一會兒發現不太對勁。這個時候再看時間，發現我已經對著 T1 瞪了幾乎半個小時了，就開始有點慌了，最后直接來了個比較暴力的做法，先欽定全選 A 然后進行調整，又寫了大概半個小時。寫完才意識到我好像把問題加強了（可以把 \(\frac n 2\) 改成任何數），此時已經過去 1h 了，但事已至此，只能繼續做后面的題了。

T2 一開始覺得是建圖然后可以直接跑最小生成樹，然后感覺不太對，發現這個應該能歸約到最小斯坦納樹，所以直接 \(2^k\) 枚舉，其他邊在一開始排序就可以做到 \(\mathcal{O}(m\log m+nk2^k)\)，通過了大樣例但發現大樣例數據規模比較小，就想著先去看后面的題最后再來造極限數據。這個時候大概是 16:00。

T3 幾乎一眼，去掉左右相同的部分，劃分為若干等價類，然后對兩邊建 trie 樹，最后跑二維數點，可能是所有題中思考時間最少的。但是這個東西是很多部分拼起來，代碼很長，所以寫了將近半個小時，寫了大概 3k，然后發現一直通不過第 \(3\) 個大樣例，然后我心態比較炸，就沒想去寫對拍。最后瞪了好久發現有個地方把 \(l\) 寫成 \(l+1\) 了，事實上我只需要造個小樣例就可以發現錯誤。調完之后是 17:00 左右。

最后一題，讀完題沒看到是之前放棄的和沒通過的加起來要小于限制，以為是只看沒通過的，然后就認為是唐題，結果寫完發現一直過不了第二個大樣例，又調了好久才發現是題讀錯了，然而此時已經 17:40 了。

這個時候我就變得比較絕望了，但是又很快冷靜下來，因為計數是我的強項，應該有機會做出來。我發現可以設 \(f_{i,j,k}\) 表示前 \(i\) 個人，沒過的有 \(j\) 個，\(\le j\) 的用了 \(k\) 個的方案數，那這個轉移不就和前幾周打過的 ARC207A 一模一樣了？并且復雜度是 \(\mathcal{O}(n^3)\)，非常勝利。然后一直寫到 18:10，開始變得比較激動，但最后關鍵那一行的式子我推錯了，并且我發現我又是沒通過第二個樣例，這個時候就真的冷靜不下來了，我嘗試造小數據驗證，但是已經來不及了...

最終只交了個暴力上去，估分 100+100+100+8=308。并且 T2 有可能會被卡常。

出來后和機房其他同學一起準備去吃火鍋，路上發現 T1 非常簡單，不知道我為什么做了個加強版，并且這個題耗時比 T2T3 都多。但是做出 T3 的同學好像不多，怎么回事呢？路上的心情一直很不好，因為我錯過了最后一次可以 AK CSP-S 的機會，并且還是死在了最擅長的計數題上。后面和同學吃了火鍋，又去打了臺球，基本上緩過來了。

第二天起床準備再看下 T4，在比較冷靜的情況下立刻發現哪推出問題了，然后花 10min 寫完代碼在洛谷上通過了。又寫了 T2 代碼發現可以輕松通過。這個時候徹底繃不住了，因為我只需要在考場上改一行代碼就可以 AK，所以 T1 想太久、T3 調太久、T4 讀錯題，只要任何一個環節沒出問題都能讓我寫出 T4。但是現實沒這么多如果，沒有調出 T4 就是事實。

總結：這次考試有很多失誤的地方，因為一開始我就奔著 AK 的目標去做，然后 T1 花太長時間就讓我心態受了些影響，后面只想快點做完所有題，所以有很多失誤。這和去年考 CSP-S 非常相似，也是以為要 AK 了很激動最后就炸了。此后的考試一定要注意，不要讓心態受到影響，一定要冷靜下來想所有題目，并且要提高思考中等難度題目的速度。

這次 CSP 是非常遺憾的，但好在這個分數不是很重要，就當成給 NOIP 攢 rp 了，希望能在 NOIP2025 中考出一個好成績吧！