CSP2026 游记

· · 生活·游记

标题编不出来东西了。

JS-S01036。

初赛

怎么有点计算,我喜欢。希望大家记得我 25 年出的 SCP-S 模拟也有点(存疑)计算(

怎么还有两边不相等的递归,这不是我们 Akra-Bazzi 定理吗。没想到两年前随便写的东西(第 8 题)居然有点押中题了。

总而言之是全对了。

复赛

说起来国庆的时候出去讲课了来着。现在来考这个 CSP 能保证打过学生吗。

好挤啊。CSP 就是人多。

进去开考前好像发现没啥想在注释里打的歌词,于是写了点神秘玩意,有兴趣可以去迷惑行为大赏里面找。

听说上午 J 组的密码是 trick||treat 之类的东西,这次的密码。

先浏览一遍吧。看起来题目就是正常的 CSP。

先口胡一下。T1 简单。T2 题意啥意思来着,画一下,哦原来是这样的。Floyd 一下。哦这边复杂度是 O(md) 不是 O(md^2),那更对了。

T3 咋做啊。两边贪一下,啊只能差一个对吧,而且还只能是 i+1 和 i。两边独立了?那看起来就是对每个算一遍。咋算啊。稍微刻画一会儿吧。一步是好算的。两步以上的话……好像是先用集合哈希算一下倍增二分一下最多能到哪然后求一些和?不是很懂。但是看起来只能写了吧,空间刚好够的。

写了一会儿突然意识到这不就是个递推求和吗,好像想复杂了。但是好像这个时候电脑变得极卡,找了监考重启一下。还好想出了个好写的东西。总之是通过了 T3。大概还有 2h~2.5h。

来看看 T4 吧。先看看暴力咋打。分成两边之后……以直径中点为根 dp?哦看起来有一些更对的东西,从叶子往里取 \max BFS。这样看起来有 50 分……应该平方是好写的吧。这个标号看起来是自然的啊,能解决这个问题吗?二分答案的话,选一条边,往两边扩展。看起来是所在二度链的长度减去些东西?不对不对,链外的结点贡献还是可以存在,不能视作 0……好像不是很懂,作为相邻的次大值和最大值都感觉很难处理。

思考未果,事已至此,打暴力吧。(不过事后看来好像挺接近正解了……?还没尝试去理解场上到底做出了什么和没搞懂什么。)还有个 k=2 的 10 分可以拿,还调试了一小会儿。总共看起来就是 100+100+100+60=\boxed{360} 了。

没有 AK,自然也没来得及对拍。听说样例很弱啊,吓人。好像离上一次 OI-like 比赛过的时间已经不早了呢。

……出分了。确实没有挂分也没有反向挂分的。

听说爆好多大的了啊。什么叫民间查出来好多疑似作弊。什么叫时间复杂度 O(md^2) 被识别成暴戾语言了。什么叫 T3 输出大样例有分。什么叫 T4 std qoj 上被 hack TLE 了。

神秘。不过 CSP 打多少分对我来说也不太重要了吧。

(才不是这样的。)