GDOI 2026 游记

· · 生活·游记

强行撑着被 Noiplus 2025 创飞的身子来参加今年的 GDOI 2026 了，被 NOIP 支配的恐惧依然笼罩在我这个小小蒟蒻的 \mathcal Oier 的心头。

今年的省选打得好不好呢？我感觉是还行，意料之中，没有对赛时的自己责备，也没有对赛时自己的钦佩。

Day -7

省选的一周前我们就开学了，我们同一届的几位大巨都选择停课一周冲省选。反正是开学前的一周，停了也没多大问题。但我一点都不想停，主要是想起去年联赛前大胆停课两个月，结果只拿了个二等奖不说，文化课落下了一大截，那段时间补文化课补得我是相当痛苦。

所以这次我就没停课，都随缘了。停课集训固然可以提升自己的水平，但我觉得大赛时的心态可能也是很重要的一个部分，我决定先调整一下心态先。腐一下文化课，端正自己态度先。

不知道这会不会有什么影响，有影响我也心甘情愿。

Day 0

腐了一周文化课，省选前一天还是在教练的指导下停了一下午的课。反正也没什么重要的主修科目，停了就停了。

停课过来敲了几下板子，随了几道题，跟同学聊聊天，还试了一下机，一下午就过去了，时间真的过得挺快的，尤其在搞腐的时候。

晚上过来学了一下树哈希，感觉挺巧妙的，不知道怎么分析冲突概率，根本没有想过什么时候会用上，但看到这个东西我之前看过几眼但我一直没有系统的学一学，再加上这个晚上我真的不知道干什么，所以就给它敲了。

然后开始学习使用 visual Studio Code。没办法，真的没事干，找个有意义的事腐朽。最后拿它敲了一份 A+B problem。算是入门了，最后败在了不会调试，不会配 json 文件。

晚上回宿舍，即使路上灯光并不亮，但我依然没有数到几颗星星。明天就是省选了，为什么我一点也不急呢？

Day 1

在考场门口见到了几个有一段时间没见的朋友，聊起来还是没什么隔阂的，挺开心的。

早上没做题，腐了一会别人的考场小技巧，腐了一会别人的游记，就进考场了。

进考场后就静候考试开始了。

考试开始，解压密码有个 SX_Day1 我当时没绷住笑了，什么神秘的解压密码。

配 Sublime，打试机代码，打快读，这些我早已轻车熟路。

唯一不熟的，是每次比赛，不同的难题。

开题！！！

T1 recollector，我没意识到神秘的 recoll- 前缀，但是还是觉得这很 recall。题意还算简单明了，根据经验立刻想到是对于每条边，统计它作为轻边的概率和。这一步转换还是很好想到的，然后就自然的想到设一个 f_{i,j} 表示考虑到以 i 为根节点的子树且以 i 节点为一条长度为 j 的重链的一端的概率和是多少，感觉这很对啊！

手玩一下样例以防止出现 CSP 2025 S T4 的悲剧 ，发现确实没有问题，直接开打，先不管多少分啦！反正肯定有分！

最后在 40 分钟时打完了代码，开始调代码。我记得第一个样例的第二个答案好像是一个以 \textcolor{red}{8} 开头的数字，为什么我的代码跑出来是 549034400 呢？快调快调！调了半个小时，手算几个 dp 值发现好像都没有什么问题，那到底是哪里出了问题呢？回去重新手玩一下小样例，算到一半突然发现好像我把答案记错了。我直接被我自己蠢笑了。关键是我刚刚好像改了几处地方，算了不管了，第一个样例过了，看第二个样例，第二个样例错飞啦！！！

调了 5 分钟，发现枚举范围枚举小了，改大一点，直接过了。看第三个样例……

发现样例过完了，十分高兴，最大的数据只跑了 600ms！不对，我感觉有问题。以往 CCF 办省选从来不会给你最强的大样例，今年它肯定也不会给满的大样例！！！

其实是我注意到它大样例的第一组数据是一个链状物，所以数据肯定没造满，打了一个深搜发现树的高度都非常高，意味着其实就是常数条链拼在一起。观察代码，发现我的代码好像是个 \mathcal O(n^3) 的东西，但是树上背包有个很小的常数，我还打了几个剪枝，看上去应该只有菊花图才能卡满复杂度吧！

造了几组菊花图，发现 900ms 跑了过去。emm……算了，保底有个 48 分，先开后面的题吧。

没错，一个半小时过去了，我还没有看后面两道题，属于是我背水一战了，如果这道题和 NOIP 2025 T2 一样，那么我就重蹈覆辙了。

但好在似乎没有，我们还有三个半小时可以扣剩下两道对于我来说不可做题的部分分。

T2 是字符串题，好不容易读懂题意，发现有点晕。但好在它给了 O(2^n) 的暴力分，先打了先。

想了一会，发现好像会了特殊性质 B，简单实现了一下，发现假了，假完之后发现稍微改一下就真了，但是原来代码不能要了，重打了一遍，调样例的时候发现我打得极其复杂，而且我少考虑了好几种情况（埋下伏笔），又重构了一份代码才把大样例过掉。

T3 的题意也是比较好懂的，属于游戏类题型，这边建议可以学习一下 CF，搞一个小程序，让选手直观的模拟一下操作后序列的改变 （消磨选手的时间）。简单打了指数级暴力，就开始想有没有别的分可以拿。发现有一档特殊性质 m=1，简单，随手拿下 4 分。发现特殊性质 A 有点没明白有什么意义，但是特殊性质 B 好像有点眉目了。

我的想法是：观察到这 3 个 1 肯定是一直在左边的，不会去操作。然后手玩一下猜测我们可以通过若干次操作将 4n+3 个数给异或起来并放在同一侧，好像是对的吧，不管了，先继续看。手玩样例的时候发现前面结论好像有点问题，应该是 4+3n 个，改了过来，这次应该是没问题。

既然如此，那么我就设了一个 f_{i,j} 表示考虑已经考虑完 A 序列的后 i 个和 B 序列的后 j 个，这个状态是否可以被构造出来。然后这个东西是 \mathcal O(n^3) 的，能过，十分高兴，大样例也是成功过完。

最后在想是该打 T2 的 C 性质还是写 T3 的 m\le 2。

在纠结中发现自己什么也想不到，算了，不管了。

最后 25 分钟检查一遍代码，顺便胡思乱想一下，突然想到了 T3 的另外一种情况，就是其实我是可以操作最左边的 3 个 1 以直接删掉若干个数字的！（伏笔收回）完了，还有 25 分钟，打得完吗？

不管了，先打着，打到最后 8 分钟，也没调过样例，不敢打了，赶紧 ctrl + z 撤回，没错，我没保存原来的代码！我当时发现反例后直接急坏了，直接在原来代码上改了。

幸好 Sublime 不吃代码，成功找回以前的代码。

静等考试结束。

在考试结束前 3 分钟内，我们把小恐龙打到了 1000 多分，第一次感觉小恐龙这么好玩。

预估：[48,100] + 30 + [12,32] = [90,162]
实际：

出来发现一车人的 T1 都没跑过大样例，但是我跑过去啦！哈哈。

但依然有人强如怪物怒切 T2，好像也有一部分人有 200+ 的分数。我并不眼红，因为我已经算是尽力了。

凡事尽力而为，而后顺其自然；放下的越多，拥有的越多。

下午快乐打球！

但在开大会的时候，教练发表了神秘言论，例如在提醒我们运动不要太剧烈了的时候，他是这么说的：

“不要故意在今天说我要挑战 wmd_125 或者一定要大帽 2021cyq 啊。”

神秘。

下午打球贼准，也是没有吃过帽好吧，哈哈。

晚上依旧调教 VS code。

Day 2

早上也是睡的很晚起，但是好在没有迟到，依然在 7:40 前赶到机房。

看到 Day 2 的解压密码里面依然有个 SX_Day2，这时的我开始思考这 SX 是否有别的意思。

但这不重要，重要的是我一开 T1，首先看到的是：

现在的省选也要和 IOI 接轨了吗？那今天将会是我第一次在考场上打交互题。

今天我们先看题再开打，读题的时候感觉 T2 很像之前做过的某场 AGC 的感觉。T3 是今天唯一的传统题，题意也很像某场 CF 的 F 好像是。当然这里说的是题意，赛后找了一下这两道题发现好像题意还是有点不太一样了。

感觉了一下难度，发现好像还是 T1 最可做，于是决定猛冲 T1。

先感受题意，感觉 0 的位置十分重要，因为如果询问的区间没有包括 0 的话，那么 query 的结果就一定是零，没有任何有用的信息。

然后很快想到了一个查询次数 \mathcal O(\log n) 的方法查到 0 的位置，然后……，然后就不知道怎么办了。

正所谓：“不知道怎么做就看特殊性质！”

观察到 A 性质是让我们不用找 0 的位置，而且零在一边，那么相当于我们每次查询的左端点就一定是 1 了。然后我们暴力扫一下右端点可以用 \mathcal O(n) 次查询确定一些位置，然后发现那些不确定的数的限制不是很紧，随便填一下就做完了。

再看到 B 性质，看了近半个小时也没有想到怎么做，而且不知不觉就开始想一般情况怎么做了。

然后发现好像我会做了？查询次数算一下是 \mathcal O(n+\log n) 的，这只 \log 怎么去呢？头疼。

本来想 T1 就打这个算了，结果一算得分：75？！

有点低于预期了，那就再想想。

又想了半个小时，发现干脆不找 0 的位置了，从整个区间往里缩就可以了。

我甚至做到了询问次数 n-1？问号。

大样例也是直接过了，然后发现 grader 的检查构造是否合法是 \mathcal O(n^3) 的，怎么如此低效！？

手造几个样例也都过了，还行，现在只过去了两个小时。

然后去打后面的题，T2 发现当 k=3 时好像有神秘结论算答案，但是我不会构造方案啊！

然后发现 T2 我连 n\le 8 的暴力都不会打，什么鬼啊？

算了，去看 T3 吧，T3 的排序方式我用了很久才理解，感觉是个很神秘的 dp？发现菊花图和 r=1 都是很好做的，一个大力分讨，一个简单判断就做完了，然后发现 r=2 不会做，然后去看暴力档，发现想到了个 \mathcal O(n^3) 的神秘状物，根本不会优化。

其实刚开始是想拿 o_x=0,o_y=0 的部分分的，但是想了大半个小时都不会做。

然后就什么都不会做了，但还有 40 多分钟才考试结束。

然后就开始玩小恐龙，甚至一度打到了 2000 多分，但是死因是下落时尾巴碰到大仙人掌了，悲伤。

发呆发呆发呆……

考试终于结束了。

预估： 100 + 3 + 16 = 119
实际：

就这样了，感觉正常发挥。

下午也是爽打球然后回去上文化课了，感觉这省选跟做梦一样一晃就过去了。

总而言之

做得好的地方：

做得不好的地方：

总而言之，还行吧，省选算是正常发挥，这应该是我这个赛季的最后一场比赛了。

感觉这个赛季像梦一样，但现在，梦该醒了。