夏天还不算开始...？

_fairytale_ · 2025-07-19 12:00:21 · 生活·游记

前言

本来打算跟省选一样直接不写游记的，毕竟也没啥意义了。

可是，也不能永远逃避下去啊。

所以，我在这里，把连同省选以及省选之后的，所有的故事全部写下来，以此和 OI 道别，然后就不要再见了，再也不要了。

我可能因为一些原因刻意没有写某些事情，希望发现了的朋友也不要提起哦。

盒子

以下是洛谷账号跟在本文里提到的人的映射（排名不分先后，随机排序）：

chb：@崔化博

syt：@syta

gwf：@KSCD_

马老师：@TomGreen

wlw：@KingPowers

蘑菇：@Drind

绝帆：@一只绝帆

iceturky：@iceturky

星洒：@__staring__

sk：@Starrykiller

lyx：@123886a123886

sca/scallion：@scallion

有些朋友可能没有出现，但是我会一直记得你们的，现在是，以后也是，谢谢你们。

可能这些友情是 OI 里唯一值得我留恋的东西了。

省选联考 2025

day 0

试机的时候发现电脑上有 lemon，和 chb 一起跟 gwf 学习怎么用。

然后和 chb 竞速写了后缀数组。

本来想看眼 PAM 的，觉得省选不可能考，遂摆。

day 1

绷不住了，怎么省选的时候举办学校里还有活动。

lucky 感觉是个简单题，怎么还是女主猜男主幸运数字，我真服了。然后就会了，通过了 lucky1，然后过不了 lucky2，调之，过不了 lucky3，调之，过不了 lucky4，调之。然后把 lucky234 都测了一遍，都过了。

遂看 recall。这不是我们 dag 可达性吗，有点恐怖，先写个暴力再说。

然后跑去看 graperm，感觉有点性质啊，但是省选 d1t3 真的会给人分吗？？？不做了，打完暴力就跑。

回来看 recall。首先考虑性质 AB 不带修改怎么做，直接整体二分，check 可以用 bitset 预处理，这不是对完了！发现空间 2G，完全够用！虽然只有四分但是我也不会别的了，开写！写完之后发现大样例怎么没有这个 sub 的？？？于是跟暴力拍，调过了，并且整体二分在区间长度较小的时候使用暴力的话会跑得非常快！

然后考虑带修怎么做，修改是单点修改，非常的弱，直接操作分块，每 B 个操作分一块，影响到的点只有 \mathcal O(B) 个！没被影响到的点可以直接套用上面的整体二分！！！心里突然特别激动，我也可以在省选场上会一个非暴力做法了吗？？？？预感到因为各种常数原因，理论计算块长已经没有用了，决定先取 B=\sqrt n，然后写完再调。虽然还没算复杂度，但是肯定比暴力优秀！于是开写，连写带调完竟然还剩近半个小时！看着 6k 的代码和屏幕上的“找不到差异”，我觉得这场省选已经圆满了。

剩下的时间我用来测试它在各种大样例下的效率和给它卡常，我发现它在 A 性质下跑得飞快，而在其他时候甚至连 60000 都不一定跑得过去，这是因为我只开了大小为 80000 的 bitset。最后没有来得及专门写一个 bitset 开 60000 的 sub 就结束了。

出场之后发现很多老哥 t2 的分数都比我低，感觉是不是要翻进队了，非常激动。下午在房间里睡觉，然后和 chb,wlw 等人一起打农，打完之后发现云斗和洛谷的民间数据造好了，决定光速写一个 t1 就去睡觉。

然后我发现我复现的代码无论如何都通过不了 lucky1，它跟我印象中赛场上的代码明明没什么不同，但是就是没法通过题面中的样例。我的脑海中突然闪现出一个不好的想法，我尝试测试了一下大样例，发现这份代码可以通过 lucky234。

...

我将它提交到云斗，获得了 100 分；提交到洛谷，获得了 80 分：只有前两个测试点没过。

“我好像，在考场上，就没测 lucky1？”

之前一切的激动都瞬间消散了，取而代之的是各种难受的情绪，我在此不再描写，但是那天晚上我给一些朋友，也在我的空间里发了很多东西，最后昏昏沉沉地睡着了。

day 2

先看 move，怎么 d2t1 也是简单题，写了一个 \mathcal O(n\log V) 的做法，然后发现大样例不满，自己造了一组满的，本地卡过去了。

然后就开始在 years 和 seal 之间来回转。我首先都编写了暴力。写了 years 的特殊性质 B，然后写了 seal 的某个 sub（这个并没有得到分数），然后想了一下 years 的特殊性质 C，发现需要做主旋律，但是我不会主旋律，然后就结束了。

出场之后发现好多人都会比我高的分数，还有人说 t3 爆搜有一堆分，太吓人了。但是我 d1t1 已经那样了，好像也没什么好说的。

day ???

中间听说绝帆 d2t1 民间数据被卡常了，但是已经回归 whk 的我也没有什么复现的想法，d1t1 d1t2 d2t1 都不知道能拿多少分，就算全都不挂也只是在省队边缘徘徊，然后也不抱什么希望了。感觉最大的俗手是忘记使用 lemon 测样例，虽然正式省选考场上应该是没有 lemon 和 selfeval 状物的。

最后在一个中午，起床后我收到了成绩表，翻到了我的那一行：

60+56+8+72+24+8。

确认了一遍之后，就出门骑上车去上学了。

我只记得那天晚自习我借着上厕所在外面发呆了好久，其实我常常这么干，晚上的风总是清凉温柔的，在安静的夜晚，靠在墙上吹着晚风，就好像可以永远停在那一刻了。

......

后来我只将 d1t1 代码中的一个 0 改成了 1 就获得了 100 分；d1t2 加上一个 bitset 开 60000 的 sub 就变成了 64 分，只需再微调一下数据点分治就变成了 68 分；d2t1 的 \mathcal O(n\log n) 做法并不困难，而 \mathcal O(n\log V) 做法也只需要写标记永久化就能通过，然而我在场上确实见到了我的程序在极限数据下跑进了时限内，从而没有卡常。加上我 noip t3 有一个地方没有取模挂掉的 12 分，这一切让我从省队线上挂到了一个甚至不如去年的分数。

挺搞笑的，不是吗？

省选就写到这里吧，之后有很多个晚上，可能是因为这个原因吗，我不知道，反正写了挺多小作文的。

其中一小段：

2025.4.20

...

其实我想做的很多很多事，梦想着要做的事，期盼了好久的事，到头来都让我十分失望。

只剩下那些错过了的，遗憾着的，还留在那里一闪一闪，并且时不时还要熄灭几个。

我真的累了。

我什么都做不到。

...

APIO 2025

day<=0

怎么撞月考了，牛牛牛。

怎么撞 MO 预赛了，牛牛牛。

无敌了。

跟 scallion 和两个 ytez 老哥分到了一个宿舍。

面到了蘑菇 lyx iceturky gwf chb sk 星洒等一众朋友。

sxz 怎么羽毛球馆不开放啊？？？？？

听了讲课，我竟然还能听懂一点，行。感觉博弈那个讲得很细致，几乎全都听懂了，而且很有意思，但是到最后快要忘完了，比如一个博弈 >0 是哪边必胜来着？？？

哇还有狼人杀环节，第一局作为最后的狼极限获胜，第二局又拿到狼，被前置位预言家发查杀，悍跳之后被我的金水发查杀，六百六十六这还怎么玩，直接自爆跑路。

和人打交的能力。

试机跟 sca 坐一起，然后在最后半分钟极限通过了 noip t4！看来我还没忘完。

day 1

什么叫题目顺序按照字典序排序？？？？

hash 看起来比较可做。考虑如果找到一对冲突的数，那么模数就一定在它们的差的约数之中，这部分不会花费太多次数，暴力枚举即可。问题变为怎么找到一对冲突的数，不难想到，我们要构造出一个尽可能小的集合，使得它们两两之差遍及 [2,10^9]，然后再对这个集合做二分状物不断缩小即可。首先一个观察是只需要遍及 [5\times 10^8+1,10^9]，因为前半段一定包含在后半段的约数中。然后到这里我不会构造了，于是我使用了随机化，根据生日悖论，只需期望 \mathcal O(\sqrt n) 个数就会有一对冲突。但是这里其实直接套用 bsgs 的构造，即构造 \{1\dots \sqrt V\}\cup \{\sqrt{V},2\sqrt V,\dots\} 就是一个确定性的，而且常数更小的算法，好像有 90+ 甚至 100？

发现分数在 60 左右均匀分布了，经过一些神秘的调整，我选择了一个 pretest 分数达到了 70+ 的随机种子。

permgame 是一个看起来需要观察性质的题，而 rotate 感觉不太会做，于是写完 rotate 的暴力就开始全力冲 permgame。

首先过了前两档分，然后观察到一个点的度数 >3 就完蛋了，于是 sub3 就是链，发现置换环是解题的关键，而 sub3 只需要把置换环嵌入链中即可。很快就写完了，但是一直没有通过 pretest，又没有大样例可以调，也没有暴力对拍，手造的数据都通过了，于是就一直瞪眼调到结束。。。

啥叫 rotate 是全场最简单的题？？？？？？

...

被字典序做局了。字典你赢了。

出分了，发现 t1 挂到了 50，于是分数变成了 50+12+16=78。差两分 Cu，唉唉。

晚上和 iceturky sca chb 以及 ytez 老哥打 uno。这里我必须要曝光 chb，已经不是人类了，干出了包括但不限于把非数字牌装在兜里，不管手里剩多少张都喊 uno，每次都拉一个老哥进行最终决斗等行为，666 演都不演了。

NOI 2025

day -1

到达绍兴！跟 sca 又分在了一个寝室。跟一众老哥画猜，然后晚上干啥了来着，应该是看了点题，主要是聊天。

day 0

dzd 讲话：《我认识鲁迅很早了》（记住这个）《剩饭扣一分》（也记住这个）

试机和笔试跟 chb 坐在一起。

笔试 ak 了。

晚上饭还有小龙虾的，但是懒得剥壳就没拿，好像大家都没拿。怎么绝帆全吃了。

晚上看了点题和自己之前的笔记就睡了。

day 1

坐在某省女队旁边。

密码是 noi45*45=2025!，一开始没打那个 !，绷不住了。

robot 看起来是个不太难的最短路题，但是我怎么只会 \sum indeg\times outdeg 的做法，先写一下。怎么过了 pretest？？？然后花了一会尝试证明它的正确性，证明失败后成功造出了卡掉它的数据。看了特殊性质 C 后尝试想根号分治，失败了。我感觉做法呼之欲出，但是此时突然浮现出一种难受的情绪，然后脑子里开始想结束之后的场景，“到时候我肯定做出来 t1 了吧，我到时候会跟周围的老哥讨论什么呢？”“诶，我有没有可能到结束也没做出来？？？”一语成谶。其实不只是这里，在各种大小考试里，如果我脑海里浮现出这种不好的念头，基本就注定我这次考试完蛋了。

不管了，先打了 sequence 的 28 分暴力，然后尝试想更多分，在这个过程中脑子里一直想着“我不会 d1t1”这件事，于是只好回来继续想，然后想到了 sequence 的很难写的优化，写了近 20min 之后发现还没打 tree 的暴力，于是先去写 tree 的爆搜，最终在考试结束前 1min 极限调好。

出场之后听到绝帆 208，听他讲了 t1 做法之后发现确实是简单题，而且是应该一眼秒掉的那种。又听到几乎所有人都会做 t1，而且 t2 有很多分，明白自己 day1 已经爆炸了，并且 d1t1 不会做的事实让我开始怀疑自己现在的实力是不是只配打铁。

查分发现 d1t1 怎么暴力过了？？？奇异搞笑。

100+28+8=136。在沙东也排到了倒数，而且我知道这只是 t1 数据水的结果。

不知道该怎么办了，只能一会看看题一会打舟一会聊天来分散注意力。我从未想过会是这样的结果。今天真的是人类坐在那里打比赛吗。

day 1.5

怎么中间还有一天啊。社会实践去了两个馆，还是速通，绷不住了。有个 AI 鲁迅，经过提问成功让他开始介绍 dzd，这下真认识很早了。

下午看电影没去，在宿舍睡觉。

然后发现了一件事：绝帆 d1 打了 208 是不是因为他把小龙虾全吃了啊？？？吃剩饭能加分，这招太狠了/ll

晚上打了后缀数组板子，睡得很早，但是躺在床上一直睡不着，于是又开始给人发东西，发了好多好多，到最后我也不知道在说什么了，半梦半醒地睡着了。晚上睡得也很不好，唉。

day 2

把 pdf 密码当成登录密码输了好多遍才发现/xk

ternary 看起来是个不太难的题，观察一下特殊性质发现只需要找最左的 110 和 101 就行了，线段树维护之，用了 1h 就通过了。

这个时候我感觉找到状态了，终于不像 day1 一样不是人了。

然后 set 是集合幂级数计数，我可能有点会又有点不会，想了近 45min 决定打完暴力就去做 defense。

defense 是三国杀题，首先 \mathcal O(nq\log n) 的暴力是容易的，交上去发现怎么有 40，折磨牛。那今天是不是又是一车 200+ 啊？？？但是此时还有三个多小时，优势在我！特殊性质数据随机有一堆分，观察到我们要处理一个某个数组的后缀最小值，那后缀最小值的段数应该不会很多！测量一下大样例发现不超过 10！也就是每次可以直接把每一段拿出来 check，然后每一段内是好（？）维护的，式子是一个 \lfloor\dfrac{i-l}{6}\rfloor+f(i)，其中 f(i) 是可以线段树维护的！而左边这一坨我直接开六棵线段树不就好了！

（我的做法是直接对着牌堆维护的，而这要做很多麻烦的奇偶讨论，但是我当时没有意识到对着每个回合维护是更简单好写的做法，从这里开始可能结局就注定了。）

（而且在这里，每次修改只会改 \mathcal O(1) 个段，也就是只有 \mathcal O(1) 个段的合法性会变动，于是直接对着这些段修改，同时维护答案就是正解了，而我也没有意识到这一点。）

这个时候我已经被兴奋冲昏了头脑，于是我做了本场比赛最错误的决策：我把可能要用到的数据结构先全部写好，然后试图直接将它们组装成正确的代码。这在所有的大码量题里都是大忌，因为一旦出现问题甚至都不知道该调哪里。正确的做法应该是从暴力开始，逐渐把暴力的每一块优化，这样出问题了也只需要调刚写的一部分。

我先花了近半个小时写我之后根本没有用到的珂朵莉树，因为后来我发现用珂朵莉树维护连续段非常难写，于是放弃了。总之经过很长时间的编写，我在还剩半个多小时的时候通过了编译。

剩下的半个小时如前面所说，我对着过不了样例的 300 多行代码不知所措，我确实调出来了许多问题，但是改完一个之后总会出现下一个，于是直到结束前的最后一秒，我也没有通过样例。

我以为像 recall 一样的奇迹会出现两次，但是到头来终究只是空想。已经快半年没有训 OI 的我又凭什么祈求奇迹降临呢。

中午和绝帆 sca 学习打乒乓球，好像有点会了吗。

查分。100+100+28+8+100+16+40=392，是一个看着就知道打不了银也打不了铁的分数。

晚上篝火晚会，我缺的蜂鸟这一块补上了，牛牛牛。放 lemon 的时候在下面和一堆沙东老哥唱中文版，最难绷。

然后是和绝帆 syt 进行了神秘小活动，还给马老师打了电话。

day 3

唱了《夏天还不算开始》，但是站在台上的时候浑身都在发抖，感觉整个身体已经全部拆开了，手是手，腿是腿，脑子是脑子，嗓子是嗓子这种感觉，希望大家轻点喷/kel

有一个难绷的事是唱春日影的时候 dzd 跑出去了。

绝帆的《希望有羽毛和翅膀》感觉非常牛！还有一个主唱特别拼命的节目，忘记是哪一首了，但是印象很深刻！感觉大家的节目都很厉害！

在 2202 看 chb 打三国杀，郭照怎么这么超模啊。