CSP2026游记

· · 生活·游记

BJ初二生。去年JS两个二等唐完了

初赛

上午J组随便写完直接发呆,S组靠GESP八级免了。

J组初赛84.5,没想到几乎一年没写过初赛的题还能这么高.

复赛

J组

t1直接秒了,凭借多次乘坐高铁的经验成功注意到没有E座。

t2一眼双指针,感觉实现细节有点多,不管了,直接写。经过20min调试成功通过所有大样例。

t3怎么这么简单,5min看出按位贪心,10min写完代码,一次通过所有样例。

这时候心里已经很高兴了,300分肯定能一等了,就想着t4随便写点暴力。先写了个O(n^3)做法,本来打算睡觉的,结果发现还有1个多小时,这不冲个正解?

发现可以通过跳next做到O(n^2),接着注意到有很多重复计算的部分,直接建个图做完了。距离结束还有10min时写完提交

估分:100+100+100+100=400

S组

t1一开始以为要对最后变成的数二分,然后发现不对,接着想到排序后二分的做法。但是一直过不了样例,觉得可能是没实现好(其实是因为我先做的前缀和后排的序),换了个双指针写法,还是不对。终于在开考后40min检查出问题,改完就过了

t2题面怎么这么长。幸好我阅读理解还行,成功理解题意,并且没有被样例解释误导。一开始以为d<=20是分层图,然后就不会做了。

思考了一会,想到n一般代表点数,由此发现可以用地铁路线当点,加上Floyd就行,时间复杂度O(md^2+n^3+qd^2)

t3一开始直接读错题了,以为路径至少两条即可。以为想出了O(n^2)做法,但仔细看了题才发现有问题。然后想到可以O(n^3)dp,遂写代码。觉得这时候单调队列优化一下就能O(n^2),但是不知道怎么在单调队列优化的时候维护方案数,于是放弃了。

t4再次读错题,没看到两个连通块,以为二分之后直接剥叶子即可O(nk\log n)

写完之后才发现看错题了,重新思考,发现k=2时就相当于没有两个连通块的限制,再拼上一个子集枚举,获得30分

估分:100+100+24+30=254

出分

很幸运的是这次居然一分没挂,J400S254,拿下两个一等