2025CSPS 游记

· · 生活·游记

2025 CSP-S 游记

DAY 1

14:15 进场

14:27 开始

14:30 阅读完T1 club 题面，观察到非常典型的每组不超过 的限制，先是思考枚举超出限制的组然后容斥，随后反应过来每个元素产生贡献的只可能是最大和次大值，先默认取最大，再按差排序后贪心的做调整即可。

14:40 开始写T1 club 代码。

14:55 完成T1 club 代码并通过所有大样例，发现极限数据本地跑了 3s ,遂进行卡常。

15:00 开下一题，因为鼠标的翻页设置有点问题(?)直接翻到了T3 replace 还没发现，把 T3 当成了 T2 。

15:15 想到T3的一个转化是把x+y+z -> x+y+z 这样的一组转换变成x+y+y+z，尝试使用字典树将 y+`y 插入字典树然后记录一些前后缀信息，思考近1h无果，在查看题目时空限制是猛然发现这是T3，于是回头去看T2。

16:15 看到T2 N=1e4 与 K=10，猜测复杂度瓶颈与这两个有关，一定存在一组最优解仅用到原图的 MST 上的边与新点的边，想到先跑一遍 kruskal,将用到的边全部加入边集合。然后 2^K 枚举建的新点，将枚举到的点的新边全部加入边集，最后再跑 kruskal 尝试更新答案。复杂度应该是 O(M\log M + 2^K*KN \log KN)，大概是 2e9 左右，考虑优化，发现将 kn 条新边和原 mst 上的 n-1 条边预排序就可以少一个 \log 最终复杂度 O(M\log M + 2^K*KN)。

17:15 写完 T2，测大样例时发现第三个大样例 road3.in 居然要跑 14s ？？？ road4.in 更是完全跑不出来了？？？
难以置信的反复算了好几遍复杂度，反复看了好几遍题目，确认无误后继续思考优化，无果，拿下一些性质分和暴力分。

17:30 - 18:27 再次思考T3，发现了ACAM做法，但是仅剩余 20min，害怕打不出来，在T4混了几个测试点的性质分，结束了。

DAY 3

复盘发现 T2 复杂度是对的，只是因为考场机器太烂，但是那个做法最后没交，唉。

感觉打成这个样子，挺对不起自己这一个月的努力的。

希望能去NOIP，希望NOIP能有一等然后能去省选。