CSP-S 2026游记

· · 生活·游记

训练的时候教练让我们写总结,要求至少写满1张A4纸,写详细了.我写完了就给总结扔上来了

坐标BJ,考点rdfz南科研楼

shsbnu同款dell键盘好评. 手感+10

考前

考前坐在机器上,由于自己不会写平衡树,所以高度依赖pbds.但是我忘记pbds咋写了.然后就出去拿手机打开自己的博客复习了以下模板,考试开始后迅速的敲出来.

考试开始

显然,我是先把pbds的模板敲了出来.

然后我把我自己的缺省源敲了出来.

然后我解压输入了解压密码.一次就输对了.

然后我就开题了.

通读题面

先看了一下第一页的题目信息.没什么可以注意到的.

先看了T1,看上去非常简单.然后就没有继续读了,去干T1了.

第一题

看到了,我们在脑子里思考一个柱状图表示每个值的初始值和增加值.然后我们就可以显然出来最终的值是数列中已有的值是不劣的.

然后我们就可以考虑枚举最终的值.

然后显然,我们比当前枚举的值还要大的值是不可能为当前的枚举贡献答案的.所以我们可以先排序一下.

然后我们考虑对于当前枚举的值怎么计算答案.

然后我们可以注意到,优先选择距离当前枚举的值差值小的.

然后由于我们已经排序了,所以相当于从当前枚举的位置从右往左选择.

然后这个显然单调性,然后想到二分答案+前缀和优化.

思路意义上干掉了T1

然后是代码实现.

代码实现没有一次写对,二分的变量写错了.调试了以下就好了.

对拍大样例,全过了.

截至当前考试开始10~15min.

第二题

读题目读了3遍,然后读懂了.

然后我们显然可以发现可以先给出入地铁口的路径长度单独拿出来算,因为你最多在进入地铁和出地铁系统的时候走一下地铁口,而且走的地铁口是已知的.

同时,我们发现坐地铁本是是不消耗时间的,因此每个线路在图上可以只存在一个点.

然后我们看一下询问的范围,我们可以注意到询问次数非常大,这意味着我们必须利用提前预处理的信息来处理询问.我们不可以每次都跑最短路.

然后我们很容易注意到线路的最大值至多500,立马想到500^3,然后想到弗洛伊德.

然后我们要处理线路之间的移动,我们显然可以直接枚举每个站点,然后站点之间的线路两两连接边.

然后现在从任意一个线路到另外一个线路的最短路我们就知道了.

然后我们就可以枚举一下最先坐那个线路,最后坐那个线路.然后直接求解即可.

大数据一遍就过了

截至当前考试开始50~60min

第三题

看到第三题,立马想到n^3的暴力.

然后我就去想正解了

然后很容易注意到如果两个最短路线之间存在对应点a,b使得存在点c满足a<c<b,那么这个点对必然不满足要求.

然后想了半天没啥想法.

考试大概过了2.5h

最后把n^3的枚举起点暴力写了出来,考试结束前30min注意到可以线段树优化转移,然后就给优化到了n^2log_2n

第四题

显然我们可以2^n直接枚举点的选择.

然后我们就有了2^nn的暴力做法.

然后我就去推特殊形状的式子,然后得到了一个看上去好像对的式子,然后改了半天没什么思路.

然后就去给我的2^nn优化.然后我就可以显然出当n=k的时候,答案为0,然后我就写了下面那个东西

//读n,k....
if(n==k) {
    puts("0");
    return;
}
//读边

然后我这个优化就直接给后面的读边跳过了,大样例也没测出来.20pts->5pts

最后总分

100+100+40+5=245

总算是能拿下S 1=了