GDOI2026 游记

· · 生活·游记

尝试写一个正经游记。

Day -1

中午到达珠海北站宝龙城亚朵酒店。女队提议第二天要拉同学去旅游，然后一堆人在酒店大堂的地图研究了好久，还没讨论出去哪玩。

试机，发现键盘很阴间，反斜杠在最上面，Backspace 键宽为 1。不过反映后重新试机发现全部换成正常的键盘了。

食用 58 元酒店自助晚餐，这性价比也太高了。

晚上已经完全不想复习了，在酒店随机摆烂，看电视，发现三个动画台两个奶龙一个熊出没，感觉奶龙的宋的程度有点超标了。

Day 1

开题。一上来看到 T1 是计数还求期望还是有点震撼的。不过想了一会想到可以转置，50min 过了。

T2 看着有点复杂啊。好像我可以建一个自动机然后 DP，如果自动机结点不是很多那这题差不多就做完了。

写一下，发现所有样例的自动机结点数都不超过 2n + 1，很好。

但是一开始比较宋搞了个 O(len^2 \times nk) 的做法，后面才慢慢优化到 O(len \times nk)。

观察大样例，我声称 len = O(n + \sqrt k + \frac{k}{n - 1})，那么复杂度就是 O(nk (n + \sqrt k) + k^2)。

写了好久又调了好久，总算把正确性调对了。发现最后一个大样例要跑 4s，把最大那组拉出来复制 5 遍要跑 7s。但是此时我认为肯定是考场机子太慢了，于是就没管。此时大概 11:20。赶紧写了个拍，然后 all in T3。

T3 感觉毫无思路。先写了前面三个点，然后打个表看看。大概看出来 B 性质的一些规律，打算先猜然后再对拍验证下。m \le 2 暂时没看出来。还发现 n \le 50 状态数不太多，但是鉴于 1s 的时限应该暴力只能跑 2m \ge n。

现在还剩 45min。打算先写个能过第 17 \sim 19 个点的暴力，再研究下 B 性质。好的写完了，只剩 5min 了？？很仓促地乱拼了一个 B 性质的 O(n^4) 判定，然后比赛结束了。

最好情况估分：100 + 100 + 30。

由于 T3 还剩一堆分没时间搞了，出考场就破防了。但是看起来同校的更爆，也不知道说什么了。

比赛归比赛，旅游还是要去的。

:::info[旅游过程] 集合了一下发现有 9 个人，打算打三辆车去淇澳岛，在那租几辆单车或电动车。

我们 15:40 出发的，不过由于大家意见不是很统一，导致 16:40 才租到两辆（前面和后面加起来最多坐六个人的）电动车，约定 19:00 还车。有点爆，因为酒店的自助餐是 17:30 ~ 19:00 开放，我们赶不上自助餐了。但是因为大家急切地想玩所以拖了一会才向教练报备。

说是电动车，但是有方向盘油门刹车还有后视镜，整的跟个小车一样。第一次在路上开这种车，还是比较害怕，只敢开人行道，也不敢超车。不过 hwy 开的时候就直接冲到机动车道上了，看着大货车呼啸着从旁边驶过还是有点吓人的（

先去了红树林，见到了一些比较奇特的生物，感觉比较牛。不过走的整条栈道都是几乎相同的景致，走到后面也看腻了。

然后去海边的沙滩，一群人尝试用鞋子或树枝写字，但是我写的刚写完就被浪冲掉了。好像有人的手机可以拍到港珠澳大桥，我尝试肉眼极力观察了一下只能看到若隐若现的轮廓。

最后女队要找路人给我们拍照，9 个人在岸边的石头上站成了一竖排。站在石头上感觉随时会摔下去，浪不停地拍着感觉都要冲到脚下了，再加上 hd 说快要涨潮了，于是匆匆拍完就走了。然后发现拍的五张照片没有一张是 9 个人全部眼睛正常看着镜头的（

还完车后 hd 收到了 xp 的电话，好像 xp 因为我们擅自出去玩还不及时报备生气了，最后发现是因为酒店的自助餐退不了然后 xp 投诉到总部了，有点爆，不过无所谓。

最后找了一个用了券后人均 18r 的排骨饭店，感觉我们吃饭这块是会省钱的。 :::

回到酒店已经 21:30 了，看了会电视就收拾行李洗洗睡了。

Day 2

开题。一上来看到两个交互一个 19 个大样例的大 DS，直接被震撼了。

尝试思考 T1，发现这不是经典 trick 吗，但是由于没想清楚就开始乱写代码，调了好久才调过大样例。

此时我造了 n \le 8 的全排列测了一下，发现每几组就要挂一组。尝试调试，发现我之前写的东西完全没有道理，改了一个写法之后才过。此时已经过去快 1h，浪费的时间有点多。赶紧写了个拍去看 T2。

T2 怎么是道包装成交互的构造题。看了一会会 k = 3 了，尝试猜一下答案，发现大样例 k \bmod 4 = 1 的点过不了，并且都是比答案大 \le 3。猜测可能要在度数限制的基础上做一些调整，但是努力思考了一下感觉完全不知道怎么调整。

此时总共过去 2h，但是 T2 只有 12 分。我急急急。开 T3，这前两个点把我看笑了。想了一下发现可以 O(\sum deg^2) 求出每个子树和子树补的排名，这样第 3 \sim 11 个点都是简单的。我写写写，但是由于自己太宋了调了好久。

写完后感受了一下 o_x = 0, o_y = 1 可以在求出排名的基础上在链上二分，但是对应的点没有随机性质，不太确定 O(\sum deg^2) 能不能过但还是写了。o_x = 1, o_y = 0 好像也是在链上二分，但是还要写个主席树感觉有点麻烦，再加上也不确定 O(\sum deg^2) 能不能过就没写。

此时我终于想起前面求排名的部分用 CF2135F To the Infinity 的做法改改就可以做到 O(n \log^2 n)，但是现在只剩 1h 了显然没时间了，赶紧回去搞 T2。

结果是对着 n = 7, k = 5 的表瞪了好久也没看出答案的规律，最后 10min 匆忙写了一个 O(2^{\binom{n}{2}}) 发现 n = 8 根本跑不动，于是 T2 还是只有 12 分。

最好情况估分：100 + 12 + 56。

出考场，发现 hd 会 T2 求答案并且声称 T2 很简单，我直接破防了。

回家复现代码，D1T2 QOJ TLE 90，原来再加上 bitset 才能通过。D1T3 我场上乱写的 B 性质判定没分。更破防了。

不过后来了解了一下同省高手的情况，发现我这个估分还不算很低。开始幻想能不能进 A 队，但是我觉得这点分是远远不够的。

Day 3 \sim 5

周一晚上回学校上 whk 了。感觉上课有一半的时间完全在神游，仍然想着省选，根本不在状态。

Day 6

这天上午出成绩了。得知自己没有别的挂分，最终成绩就是：

348 + (100 + 90 + 24 + 100 + 12 + 56) = 348 + 382

发现我居然是 A4？什么叫 OIerDB rk7 队线外第四？感觉发生的事情有点超出我的认知了。一代人有一代人的过河卒，OI 赛制害死人啊。

（如果最后省队名单没有变动的话）同校的 ljy A5，hd B12，恭喜。广附连续两年占领省队 B12，并且都和省队外一名差 \sim 0.1 折算分。从这点上看广附运气还挺好的。

出分前一直觉得我不太有希望进 A 队，所以取得这样的结果挺惊喜的。当然运气成分也很大，其他人不挂那么多分我就没机会了。

连续三年分别以 E、B、A 的队伍类型进入省队，也算是实现了我的一个心愿吧。

这次省选 D1T3 和 D2T2 的得分不太理想，之后可能得加训一下这类神秘性质 DP 和构造，但是暂时不知道怎么加训。

感觉这次省选的题目风格相比往年有较大变化，区分题不再是 DS 或者计数，并且加入了交互，说明 CNOI 可能要逐渐向 IOI 靠拢了，也说明现在的 CNOI 对选手要求越来越高了，省选和 NOI 就是一个本质抽奖的过程，省选还能指望别人挂分把自己送进队，NOI 就不行了。所以还是要努力加训！

祝需要 C 类名额的都能买到 C，退役的选手高考顺利，进队的选手都能在 NOI 取得理想的成绩。