CSP-S 2025 挂分记

· · 生活·游记

省流： 100+80+0+0=180pts ，挂分挂飞了。

# DAY -25~0 呃呃呃，停课了。 停课期间一直在打模拟赛，最后的平均成绩为 $cw$ 初三第 $5$ 名，还算可以。 然后又抽空把之前学过的算法都给复习了一遍，还刷了很多《算法进阶指南》上的题，并给自己立了个 $S$ 组 $300pts$ 的目标。 赛前准备得还算充分。 # DAY 1 ## 上午 没报今年的 $J$ 组（~~因为已经有 J 组一等奖了~~），听同学说今年的 $J$ 组特别简单， [r**e_lcy](https://www.luogu.com.cn/user/711245) 大佬甚至只花 $40min$ 就 $AK$ 了，%%% 。 然后花了一些时间恶补了一下数论和排列组合。 ## 下午 提前 $40min$ 来到考场，并尝试在考前打出缺省源，但监考老师说考前不可以提前打代码，所以失败了。 考试开始了。 先看 $T1$ ，嗯，一道非常简单的贪心，$10min$ 切了。 非常正常的 $T1$ 难度。 看 $T2$ ，嗯，有点强度，让我看看可不可以把村庄的点权转化为边权来做。哎不对，怎么转化之后还是做不了。再想想，嗯，可以先暴力枚举每个村庄选与不选的情况，然后就变成了最小生成树的板子题。哎不对，时间复杂度爆炸了，得进行优化。再想想，嗯，可以先对原图跑一遍最小生成树，不在这棵树上的边一定用不到，然后预先把边排一遍序，这样在跑最小生成树时就可以用有序表合并的方法使把边排序的时间复杂度降到 $O(边的数量)$ ，再把并查集变成按秩合并的，总的时间复杂度就变为了 $O(m \ log \ m + kn \ log\ n + 2^k k n \alpha (n+k))$ ，问题应该不大。最终在 $16:00$ 切了 $T2$ 。 还算正常的 $T2$ 难度。 然后想了 $20min$ $T2$ 还能不能继续优化。 看 $T3$ ，嗯，一道字符串题，而且难度还不小。（想了一会）怎么感觉正解可能是 $AC$ 自动机，再想想？（又想了 $50min$ ）哎怎么还是没想出来正解？还好想到了一个 $50pts$ 的字符串哈希做法，先把这个给写了吧。（ $18:20$ ）哎完了，怎么还没调出来？不管了，只能看看能不能 $10min$ 极限敲出 $25pts$ 代码了。（ $18:29$ ）呃呃呃，完了，连样例都没调过去，看来只能带着 $200pts$ 遗憾离场了...... 不太正常的 $T3$ 难度。 $T4$ 没看。 ------ 最终只拿了 $100+100+0+0=200pts$ ，这是完全不应该的。分之所以这么低，是因为我的比赛策略出了问题，我根本就不该花接近 $1h$ 的时间来磕 $T3$ 的正解，如果老老实实地打部分分，我的分数会比现在的高得多（至少 $250pts$ ）。 但是现在后悔已经来不及了。 只能说我还是太菜了。