0%

SNOI2024 游记

进了就写,没进就不写。

Update:进了。

Day -2

得知考场在xgd,离家里挺近的,感觉这次 SN 的通知方式很感人,想进队得翻掉大概 3 到 4 个人。

考前模版训练。

Day -1

考前模版训练,看了看以前做过的题,感觉数学好难。没看 fhq 属于是伏笔了。

Day 1

昨晚睡得比较早,感觉早上精神状态很好,座位在一个靠墙的位置,教室里比外面暖和的多。

8:30 开考,开完压缩包先把所有题看了一遍,怎么三道题正解复杂度都保底 $O(n^2)$ 啊???

t1 感觉很神秘,计数+逆向推,debuff叠满了。

t2 感觉是什么矩阵相关的东西,一眼好像只会 $O(n^3)$ 。

t3 构造,不会构造。

仔细看了看 t1 ,发现好像 $f$ 相等的一定是个联通块,那只要考虑联通块之间交界的地方就行了,而 $n$ 只有 $3000$ ,感觉枚举每个点当当前联通块的关键点,判一下跟子树内不同颜色联通块关键点的距离,乘一下就好了,开始写,40min左右写完了,过了大样例,但是突然发现题目好像没有保证每个关键点都在 $f$ 里面出现过,也没说关键点能不能都是一个点,但是有一句 如果有多个满足的点,选取编号最小的点,更恶心的是大样例也没给这种情况,保险起见多花了 10min 判了一下。

此时大约 9:30 ,开始看 t2 ,盯了一个小时,从矩阵角度想了各种做法,甚至从暴力的 $O(n^3)$ 优化成了 $O(n^4)$ … 快 11 点的时候,突然感觉可以数据结构维护,每行每列单独维护,旋转操作就是交换那部分节点,然后可能还需要个区间翻转,这不直接 fhq 嘛!wc我好像不太打的出来,花了 15min 口胡了个 fhq ,手造了点数据试了一下好像是对的,码码码,大概 11:30 的时候写完了,一侧第二个样例都不对。

那会有点急了,先去把 t3 的性质和暴力写了,回来再看 t2 ,试图输出调试,但是 $10\times 10$ 的矩阵,每个位置上还可能是些很大的数,不太可行,瞪眼瞪了 30min 左右,突然发现初始构造 $a_{i,j}$ 的模数和最后算答案的模数不一样??!出题人,我***,改了之后样例过了,但是第三个和第四个样例跑了 $100$ 多秒,不太懂,$O(n^2\log n)$ 而且 $n$ 只有 $3000$ 为什么这么慢啊,但是算的都是对的,然后各种优化,longlong 改成 int,手动取模,但好像还是很慢,不管了,总比写个暴力好(最后事实证明不如暴力分高…)

最后剩 30min 就是各种检查,加头文件,建文件夹。

考完下来问最前面的大佬好像跟我写的东西差不多,t2 大样例也跑了 $100$ 多秒(然后大家就一起挂成 10 分啦),心安了很多,vv 好像没调出来 t1 。

下午开摆,晚上再看了看板子。

Day 2

早上坐在电动车上发现 d1t1 好像有的情况没考虑,差点给自己 hack 掉,最后发现好像是对的,d1t2 好像多维护了一些东西,但是问题应该不大。

8 点多先给了压缩包密码,打开数据一看,怎么有这么大的数???数了一下好像30多位,什么年代了不会还考高精吧?

8:30 打开 pdf,看了一遍题,很大的数是 t1 的,值域小的部分直接异或哈希一下就行,t2 是个 dp 状物,不是很会,t3 是个看起来很nb的串串题,稍微看了一眼,一个约束是在 fail 树的子树内,一个是对原树上 lca 深度的要求,应该可以 dfs 序一下,没细想。

然后先去看 t1 ,值域小的部分很快写完了,跑的飞快,但是这个 $10^{36}$ 的值域是个什么鬼啊??想到 10 点无果,感觉不会 t2 ,先去看 t3 。

t3 除了刚开始看的那两个约束,还有个 $a_i$ ,这玩意不太会搞,想了想好像会一个启发式合并+线段树+双指针的做法,复杂度大概是 $O((\sum dep_i+\sum siz_i)\log n)$ 的做法,码码码,大概 11:30 的时候过了样例以及二叉树的性质,决定先去看 t2 。

然后发现完全不会 dp,想了半天只写了个链的性质和 $n\le6$ 的暴力(考后测出来链的部分还假了),回来发现 t3 还有个链的性质,好像是要一个可以维护区间取 $\max$ ,前缀求和的线段树,但是时间已经不太够了,就没写。

然后就是加文件输入输出,建文件夹,检查。

考完和 vv 交流了一下,他好像最后 5min 才看见 t3 是多测,然后没调出来,出考场的时候 vv 说感觉我能翻进去,不懂。

下午和晚上开摆,但是第二天就得去 whk 了。

然而在晚上开摆的时候,zzt 突然给我发消息,说有人测出来我进了,但不确定是民间的还是官方的,当时整个人非常激动,但是有大佬 d1 丢代码了,很神秘,去问教练,教练也没有消息。

Day 6

教练来教室说进了,虽然是最后一名,发现前面有个更抽象的翻盘老哥,vv 退役了,悲。

Day ?

怎么这么久 SN 还没在官网公开省队名单啊。

后记

最神秘的一次省选