NOIP 2024 游寄:别样的唐唐诗大战

· · 生活·游记

这次真是最后一次去沟槽的杭师大仓前了。算上这次已经去过 8 次了。

虽然早就退役了,不过这次才是真的最后一次打 OI 比赛。

听说今年评奖规则有变,算省一分数线不再去掉往年省一了。这下我们 OI 的省一终于有一点含金量了。此时心想终于可以证明含金量的我不会想到一年没动过 OI 的自己即将上演怎样精彩的小丑表演。

进入考场,输入熟悉的 123456

提一句,在今年的 CSP 中,我的电脑似乎受到了宇宙射线的影响,日期在中途突然变为 2085 年 12 月 31 日(为什么正好是 2085 年——啊🤪~啊🤪~啊咦😬啊咦😬啊→啊↑啊↓😨啊😰~嗯💥哎哎🤗哎哦哎嗯😋~哦哎🥳爱爱爱爱爱😍)。如果你将 CSP ZJ 公开的代码中所有文件按时间排序就可以找到我的神秘未来代码(其中有神秘彩蛋)。

因此在 NOIP 中我想复刻一下,尝试把日期修改为 2012 年 7 月 20 日,不过发现需要管理员密码,遂放弃。

压缩包解压密码是 Forget#2501,忘记 25 年一月,估计是省选,反正我参加不了,确实应该忘记。

试题解压密码好像是 memory#2107,本来尝试猜密码,不过首字母小写和神秘日期 2107 确实猜不到。21 年七月,那时我似乎还在写 LCA 和 ST 表。

开考了。瞬间键盘声不绝于耳。对面老哥的键盘声尤其迅猛,每次敲代码时都是光速的啪嗒啪嗒加上大气磅礴的回车,真可谓大珠小珠落玉盘。我左边甚至时不时传来哼歌的声音,总之整场比赛就没怎么安宁过。

不说这个,总之我的小丑表演正式开幕了。

先看 T1,我测这么复杂吗。于是看 T2,还是不会。

于是回来看 T1,想了不知道多久想到了解法。于是开写。写到后面越发不知道自己写的是一坨什么玩意——抽象变量名以及抽象操作,实在低俗不堪——不过我还是硬着头皮写下去了。

写完发现第一个样例过了之后的完全不对,经检查发现了本次比赛的第二唐诗操作:字符串从 0 开始读的,但我当成从 1 开始了。由于忘记可以 scanf("%s", s+1),我之后使用了更为唐诗的解决方法:传参直接传 s-1

然后发现连样例都过不了。于是我破防了,全部删掉重写。重写发现写不出来,只能用原来的写法,于是狂按 ctrl+Z,恢复到删掉之前。经过如此唐诗操作,比赛已经过去一小时。

之后,我细致地进行 debug,在发现了 3 处唐诗的变量打错了之后,终于调好了。虽然似乎对了,但我仍然怀疑这个抽象代码可能哪里会有小问题。

总之继续想 T2。有一点思路,但想了好久也不会。这题怎么这么难。

怀疑我看错题了,于是细致地重新读了一遍题。我去,还真是。本次比赛第一唐诗操作:T2 完全理解错了,花了将近半小时思考一道不存在的题。

发现读错题了之后感觉 T2 甚至比 T1 还简单,于是一顿操作。不过在对拍的时候发现了奇异的现象:其它答案全对,唯独只有第二个样例的其中一个有问题。我百思不得其解,决定放弃寻找之后会发现的第三唐诗操作,先看 T3 和 T4。

T3 似乎不难,但不会。T4 特殊性质好骗,一眼 ST 表 + LCA,而且整整 32 分,直接开写。

虽然有点生疏,但刻在 DNA 里的代码还是轻松写出来了。此时的我还没有意识到事情的严重性,没有意识到这段基因已经突变了。

经过我耐心细致的 debug,修改了包括但不限于递归没写退出条件、dfs 没判儿子不是父亲、没遍历过树直接用 LCA、ST 表初始化顺序错了的大大小小的各种唐诗问题,少说我也花了半个小时。此时我终于懂得了试题解压密码的含义——事实证明我并没有 2107 写 LCA 和 ST 表的 memory

不过更令人蛋疼的是,根本没有特殊性质的样例,于是只能人肉对了一下第一个样例就过了。

于是回来看 T2。T2 我想了多组数据没清空、取模不积极等各种可能的问题就是没搞懂。终于,在我把 gdb 都干冒烟的时候突然灵光一现,发现了本次比赛第三唐诗操作:我把指数给取模了。改好 T2,只剩下不到一小时了。

我妄想复刻一下 CSP 里极限过 T3(由于光顾着发电,我在 CSP 里做 T3 时已经没时间了,不过凭借着我超绝的运气在只剩下 2 分钟的时候写好了正解),想着就算状态转移写错了特殊性质的情况下应该也是对的。不过事实证明我输麻了,最后我慌的不行大脑已经不能正常思考了。考试结束,T3 直接爆 0。

乐观估计本次 100 + 100 + 0 + 32 = 232,悲观估计当然是 0。可能有省一,但有省一有点不可能。

没想到赛后还有追加唐诗操作。本来我想着在赛后调一下 T3 的,结果越做越红温。我推导出的状态转移方程如下:

f_u = (\textit{cnt}_u)!\prod_{v\in\textit{son}_u} f_v \\ g_u = f_u\sum_{v\in\textit{son}_u} \frac{g_v}{f_v} - \frac{f_u}{\textit{cnt}_u}\sum_{v,w\in\textit{son}_u,\,v\ne w} \frac{h_vh_w}{f_vf_w} + [s_u]\frac{f_u}{\textit{cnt}_u}\sum_{v\in\textit{son}_u}\frac{f_v-h_v}{f_v} \\ h_u = \frac{f_u}{\textit{cnt}_u}\sum_{v\in\textit{son}_u} \frac{g_v}{f_v} + [s_u]\frac{f_u}{\textit{cnt}_u}\sum_{v\in\textit{son}_u}\frac{f_v-h_v}{f_v} \\ g_u = [s_u]\quad(\textit{cnt}_u=0) \\ h_u = [s_u]\quad(\textit{cnt}_u=0) \\ f_1 = (\textit{cnt}_u-1)!\prod_{v\in\textit{son}_u} f_v\\ g_1 = f_1\sum_{v\in\textit{son}_1} \frac{g_v}{f_v} - \frac{f_1}{\textit{cnt}_1-1}\sum_{v,w\in\textit{son}_1,\,v\ne w} \frac{h_vh_w}{f_vf_w} \\

不知道为什么,只能过 k=1 的点。人肉对拍了好久也没发现问题在哪。

之后看到题解区简洁的做法,我不禁感到怀疑人生。

然后我发现有 k=1 的点。赛时我一直觉得 k=1 算特殊性质,在特殊性质里没找到,于是就认为没有。

总之现在我已经与 OI 永别了。照理来说我应该会放机房的各种走马灯,但可惜我记忆力衰弱想不起来什么东西。明明这次 NOIP 一点用也没有,可我还是很失落。大概是因为没有给我的 OI 生涯一个完美的收尾吧。但说到底我也不知道完美的收尾有啥用就是了。

回顾我漫长的 OI 生涯——都说了回忆不起来。我校大佬陈立杰曾言:『自己选择的路,跪着也要走完。』可惜别说跪着了,对于我来说哪怕遁地都走不过去。不过我是否选择了 OI 这条路也颇具争议,毕竟我学 OI 的时间根本不及学 whk 的时间(包括上课睡觉的时间)的一根。

说了这么多我也不知道要表达的中心主旨是啥。总之这篇文章就要像我的 OI 生涯一样草草收尾了。最后,祝你度过美好的每一天。(说实话,我不太相信会有人看到这里。不过一样祝愿没看到这里的人。)