CSP-J/S 2025 游记

· · 生活·游记

CSP-J

6:40 起床，7:00 吃饭，7:35出发。

8:28 看了 T1 T2，都是火题。T3 好像不会。

8:48 过了 T1 T2，开始做 T3。想到前缀异或和，想到 dp，f_i = \max \{f_j + [s_j \oplus s_i = k]\}。写完暴力过了大样例。

马上想到优化：从最近的满足条件的 j 转移，用 set 维护 s_j \oplus k。

调了一会，9:10 过了。

看 T4。怎么又是 dp？一会后想到排序，然后跑类似背包的东西，O(n^2 \max a_i)。

然后似乎就推不动了。

盯着转移突然想到容斥，求不合法方案数即可。

10:20 过 T4。

AK 了？还挺顺利的。

开摆，写游记。

橙橙黄绿？

中午 12:40 回到酒店，干饭。

13:00 吃完饭收东西，突然发现准考证不见了，吓哭了。仔细回想记得上车有拿着 J 的准考证，应该在车上。

13:06 勇闯校车夺回准考证。

15 min 睡觉，如何呢？

CSP-S

13:30 起床，13:35 出发。

到考点拍完照准备拿准考证，又不见了？？？这回真是吓哭了。

还好来得算早还有时间破案。立刻想到又放车上了，火速找老师联系司机。

13:50 勇闯校车夺回准考证。

14:28 看 T1，好像会了，写写写，过了。

14:40 开 T2，好像是困难题。

想想想

想想想……

想到啦！考虑?$&"/),@,'

好难写……

写完啦！

假啦！

40 min 过去我才意识到假了。又忘记了之前的教训，没有检查正确性就开写。

最终决定先写个 O(2^k kn \log kn)，20 min 写完了，大样例才跑 0.4s？虽然没给满但还是有点意外。

此时还有 2h，熔断 T2，开 T3。

想了一会发现可以预处理初始串对中，包含所有两串不同位的最小子串，查询用同样方式处理，用哈希搞一搞就有 O(nq)。

经过一些波折写完了，此时还有 1h，看 T4，果然是不可做题，先写了个阶乘暴力。

找能做的特殊性质，发现都不会。

回滚 T2，没有进展。

回滚 T3，没有进展。

此时还剩 0.5h。

最后发现 T4 m=n 简单做，写完摆了。

没状态啥都不想想了，把代码扔到 linux 上过编就等结束了。

黄 蓝 蓝/紫 [?]

100 + 60 + 50 + 12

有什么竞争力呢？

不过我也就这个水平了吧。算是尽力了？

自我安慰罢了。

回去的路上心情没什么波澜，也许真的被模拟赛麻木了吧。

失败了太多次，习惯了。

Upd 2025/11/2 08:30：昨晚想到我的 T2 复杂度好像是对的。做法是把所有 m + nk 条边扔进来排个序，枚举选取集合跑 Kruskal。

看上去总边数是 m + nk，但是由于跑生成树时边数达到点数 -1 就会跳出，而原图中 m 条边只有最小生成树上的 n-1 条边可能被选中，于是内层选边复杂度是 O(nk) 的，总复杂度 O(2^k nk \cdot \alpha(n) + m \log m)。

因为赛场道心破碎没有加优化（可以把每个镇分别排序做类似归并的合并，而不是扔到一起排，否则可能跑得比较满（不过好像比较难写））常数较大，洛谷最大点跑了 1.4s。

会赢吗？ccf 少爷机我相信你。

Upd 2025/11/2 09:10：上面那一坨又假了。见 https://www.luogu.com.cn/discuss/1189041