CSP-S 2025 總結(jié)

中午沒(méi)有睡著，但是影響不大。

前兩題 50 分鐘過(guò)完，T2 寫(xiě)了一個(gè) \(O(2^Kn(\log n+\alpha(n))\) 的做法，賽后發(fā)現(xiàn)可以歸并把排序的 log 去掉。

然后先想 T3，考慮對(duì) \(s_1,s_2\) 建 AC 自動(dòng)機(jī)，然后枚舉 \(t\) 中替換的右端點(diǎn)，假設(shè)這個(gè)前綴匹配到了點(diǎn) \(x,y\)，那么要求 \(x,y\) 分別在 \(s_1,s_2\) fail 樹(shù)上的子樹(shù)內(nèi)，除此之外還有一個(gè) \(|s_1|\) 的限制。轉(zhuǎn)化為三維偏序問(wèn)題，做到 \(O(L\log ^2L)\)，不知道能拿多少分，但是大樣例貌似跑得比較快。

還剩一個(gè)半小時(shí)做 T4，想到假如確定了哪些位置被錄取，那么容易算出往這些位置填入 \(c\) 的方案數(shù)，倒著填即可。然后我就根據(jù)這個(gè)寫(xiě)了一個(gè) \(O(n^3)\) 的 DP，然而我想當(dāng)然覺(jué)得這個(gè) DP 應(yīng)該是對(duì)的，就沒(méi)有考慮到?jīng)]被錄取的位置應(yīng)該怎么填，所以答案就錯(cuò)了。最后想不到怎么修改這個(gè) DP，所以到最后二十分鐘寫(xiě)了 \(O(n!)\) 暴力。感覺(jué)我這個(gè)方向就不是很正確，應(yīng)該要往其他方向想。

出賽場(chǎng)得知一堆人覺(jué)得 T4 比 T3 簡(jiǎn)單所以過(guò)了 T4，還有一堆人 T3 寫(xiě)了一個(gè) log 的做法甚至寫(xiě)了線性做法。而我屬于兩者都不占。

得分大概是 100+100+(>50)+8。

這次比賽在時(shí)間分配和策略上沒(méi)有問(wèn)題，但是感覺(jué)這次比賽有點(diǎn) DFS 式想題而沒(méi)有 BFS 想題，想到了一個(gè)有點(diǎn)正確方向的就沒(méi)有往其他方向想。

upd: 100+80+80+8。T2 應(yīng)該是因?yàn)闆](méi)有按秩合并（這會(huì)帶 log）或者是因?yàn)榕判蚨鄮б粋€(gè) log 被卡了。