CSP-S 2025 唐詩赤石記

Day ?

這學期處于半停課狀態，開學以來就沒怎么停過課，已經預料到了會考得很差了

Day -1 - 0

做了一些模板題，找了下手感，不過其實找到了 \(eps\) 的手感。

Day 1

過去上了個廁所后直接進入機房，我是303的29號，旁邊是蘇玫二，真的難泵。

然后就是打開了系統并打開了虛擬機，由于前一天學習了 NOI Linux 快捷編譯的方式，所以 Windows 和 Linux 對我來說就差別不大了，考慮到 Linux 環境下編譯的各種優點，所以全程使用了虛擬機。

迅速地敲了板子，在老師提醒不能提前敲代碼之前把板子打完了。

\(14:30\) 準時開始。

A 第一眼就是 DP，然后想了一下可不可能是貪心，感覺不太像于是果斷推 DP 獅子，現在回想起來我真的是唐詩。本來設計的狀態是 \(dp_{i, j, k}\) 表示前 \(i\) 人 \(j\) 個選第一種，\(k\) 個選第二種的最大價值，但是大樣例掛了，看了很久沒找到哪有問題所以最后換成了 \(dp_{i, j, k}\) 表示 \(i\) 個人第一種，\(j\) 個人第二種，\(k\) 個人第三種，然后把 \(n \le 200\) 的樣例通過了。

在此之前，也就是剛開考的時候，我隔壁的隔壁的那個兄臺敲代碼聲音實在是太大了，這里也是給予譴責。

然后就在想怎么優化，發現這個玩意卡得很滿，于是考場上的我在 “這玩意怎么可能能夠優化，但是也不可能是貪心啊” 的心態中熬到了考試結束。

B 上來分別考慮了 最小生成樹 最短路 網絡流，然后最終肯定是 最小生成樹，先把 A 性質的分全打了，然后考慮到了一個 \(\mathcal{O}(2^k m \log m)\)，這里我其實并不了解 MST 的性質，加之考前我沒有停課錯過了這一塊的講解，所以最終寫了個很唐詩的 \(m\) 級別的算法，后來我考完研究我的代碼時發現我似乎僅僅只需要再插入一個 Kruskal(n) 在主函數就可以把復雜度降至 \(\mathcal{O}(2^k n \log n)\)，不說滿分也至少 \(80pts\)，所以我在干什么呢？

C 字符串題我的弱項，看了一下大概像是多模式串匹配的樣子，先是想到了 ACAM，但其實我并不會這玩意（至少不是很熟），所以最后把這道題放了。

D 計數題，感覺這個前 \(i\) 個人里放棄的人跟自己放不放棄有關系非常惡心，本來是想拿一些特殊性質的，結果發現就算 \(\forall s_i = 1\)，但是數據中那些 \(c_i=0\) 的人仍然非常惡心。。。

估計：\(55 + 56 + [0, 10] + 8 \approx 120\)

總之就是感覺還沒去年考得好，客觀原因可能是環境太差了（膜拜鍵盤俠），停課時間少等，主觀原因可能就是我還是太頹廢了，并沒有把很多基本的東西整好，還有就是一些 \(trick\) 的積累不夠（例如 T2 的 MST？）。

還好是 CSP-S， 就當是為 NOIP 積攢 RP 了吧。

T1寄了：\(0 + 56 + 0 + 8 = 64\)

我必須承認的是我毫無實力可言，就算我是一個廢物也不應該只考這個分數，T1這種唐詩貪心如果放去年說不定我都能做出來，顯然的是我今年的思維方式反而更加死板，T2這種 MST 的結論題我沒能第一時間想到它的性質也是毫無實力可言，如果我就只有如今這個實力的話我還是盡早退役吧。