APIO 2025 游记（待更新）

irris · 2025-05-21 00:02:18 · 生活·游记

所有在 NOI 2025 后加入的文字以斜体标出。

负二

Don't you get there？It calls, It calls
仰いだ空が色を変えるから
My naked heart can hear echoes, echoes
識らず求めた Avidity

Whisper your name again
Then restart it right away
Oh my bitter color ardor wander
Gotta feel it undercover
行方も知らない　あの日の群青

86 -不存在的战区- 非常好看。

但是为啥动漫只改编了三卷，轻小说写了十三卷还没完结啊。剩下的十卷的主题真的能比现在的三卷深刻吗。感觉要加入 todo list 了，

哦，败犬第八卷也很牛。但是感觉剧透党闹麻了。

负一

幽默的事实：现在有一张二分图，左部点为手机充电线，电脑充电线，右部点为手机、电脑，已知电脑充电线与电脑之间无边，手机充电线与电脑之间的权值为负数。求电脑的最大续航时间。

然而回到家里发现电脑充电线是好的。所以也许是因为 Emperror 的神秘接线盒子再连接我的插线板之后，电脑充电线的电功率爆掉了。谁知道呢。不过这也成为了鸽子 APIO 游记的原因。

总之我的青春恋爱物语一定有问题。

零

身边没有有趣的选手。因为不能提前登录，所以罚坐了十分钟。感觉厕所牌的打印十分粗制滥造啊，像是义务教育阶段的印刷课本。好像发了盒饼干，但是这真的是午餐吗。

先读了一遍题，感觉中文 pdf 的风格透露着一股幽默的气息。发现自己会了 T1 的 8 分，然后思考了一下会了 25 分。然后第三个 Subtask 怎么满分只有 k = 1.1 \cdot 10^5，这真的能做吗，感觉 \frac{k^2}{2} 就不大了。T2 感觉是一道很难的题，差点没看懂。T3 很有感觉，尤其是这个 2\cdot 10^6 看起来就是启发式合并（埋下伏笔了）。想了想确实容易启发式合并。但是要讨论很多细节啊，好久没写代码了，真能做出来任何一道题吗。

先写了 T1 的 25 分，并且尝试适应了一下每次修改代码都需要 ./compile_cpp.sh 和 ./run_cpp.sh < hack1.in 的幽默事实。此时好像已经经过了至少半个小时，感觉有点出师不利了，这个 T1 真的是可做题吗。台上其实很早之前就宣称题目按照字典序排序，但是我一般的策略就是会先把所有题都看完然后发呆。感觉其实都是打 Codeforces 打的。论点：俄罗斯 oj 对中国式信息学没有任何帮助。论据：俄罗斯 oj 经常出现奇异搞笑的乱序题目顺序，导致选手需要认真阅读所有题又臭又长的题面；俄罗斯 oj 没有部分分，导致我懒得打非平凡的部分分，于是差点就没进队（虽然我进队本身远远幽默于没有进队）；俄罗斯 oj 还喜欢出假题，题意非常正确，样例非常合理，后面忘了。

然后大概就想了一下 T2。经过艰苦卓绝的奋斗，我终于意识到 e > m 是无法更优的，m = 2 是容易做的，并且在两位数次调试后喜提 12 分。但是在意识到 e > m 无法更优之后，我也没有发现其实所有点的度数应该不超过 2。如此棒棒糖的瞬间简直是我 APIO 2025 中的神来之笔，感觉就差把先做 T3 写脸上了。

显然角度相等的位置可以同时旋转。考虑把 \alpha 和 \alpha + \frac{\pi}{2} 绑定在一起。那么它们作为一个整体，要么向左转，要么向右转，并且显然向其中至少一个方向转是符合题意的。找到这个方向，并且旋转直到合并相邻位置。每次取出最小的一个整体，操作次数就形如启发式合并，是 n\log_2 n 的。

此时此刻我不会任何 T1 和 T2 更优的做法，可已经过去一个小时了。T3 真是像传统 cnoi 风格题一样的难写，其实我也没编出来怎么写，但是还是硬着头皮一行一行加功能。然后在大约两个小时的时候，我成功实现了一个 \mathcal O(n^2) 的做法：它在 selfEval 获得了 0 分。与此同时，APIO 附赠的笔成功在书写 \mathcal O(1) 个字后出现大量的漏墨。笔神真神了。

这个样例真的能要吗。我捏造了五组 n = 2 的样例，并且在艰难的调试后终于通过了 n = 2 的部分。我捏造了五组 n = 3 的样例和五组 n = 4 的样例，并且在艰难的调试后终于通过过了 n \leq 5000 的部分。值得一提的是，因为这个 log.txt 简直就是弱智，我还得不断通过添加和删除 std::cerr 来调试，并且还不能忘记修改之后 Ctrl+S 再使用 ./compile_cpp.sh，逐渐变成一种笑话了。总而言之，这个时候差不多两个小时了。

获得了可观的分数，但是总分差不多只有 100，是不是还没打过去年的许淇文，感觉要铁了。T1 看起来还是很经典，但是好像并不简单。为了凑出来 1 肯定是要做 BSGS 状物的。有一种焦思源模拟赛的美感。考虑一些进制的想法。发现从低向高确定是难做的，因为无法避免 n 足够小时奇怪的冲突。所以从高往低做，是不是就对了。询问次数大概是 \sqrt{n} + \sqrt{n/2} + \ldots = (2 + \sqrt{2})\sqrt{n} 的。实现了一波，一开始只有 59 分，但是发现他妈的只有 29 位而不是 30 位。所以交了一发就是 74 分。大概想了五分钟，发现不会优化，就扔掉了。

然后回去写 T3，发现优化都是好做的。因为写过平方复杂度的暴力，所以代码改的非常流畅。于是我自信提交 selfEval，发现恰好通过了前五个 Subtask。未免有点幽默了。我怀疑这个做法只有 \mathcal O(1) 个小细节写挂了，遂开始检查清空和链表的删除，无果。这个时候差不多还有两个小时。然后我认真地拿起之前的草稿纸重新尝试，发现之前事实上只有 i < j 的情况。如果 i > j 只有一些细节需要翻转。然后再讨论了一下，就过了。不过已经三个小时多了。闹麻了。

上了个厕所放松了下心情。但是我回到座位上才发现自己甚至没有举厕所牌，所以刚才所做的一切属于违规行为。不过省锡中感觉连志愿者都很幽默，并且没有任何人声明我需要举牌，所以我最好假装自己并不知道厕所牌的存在，于是什么事情都没发生。反正要打铁了，最多取消我的成绩也无所谓。

总之 74+12+100 要打铁了。于是现在眼前有两个选择：做 T1；做 T2。我发现我已经不会做 T1 了，所以不妨看看 T2。于是我发现了图是一条链或者一个环。对于链的情况，合并环和强制脱离一个孤点都是容易的，但是此时的分数加起来还没有三元环高颇为幽默。然后我又调试了好久的 T2，并且获得了 22 分。

感觉 74+22+100 要打铁了，于是我开始大声咀嚼饼干。感觉饼干非常好吃。然后看了一下三元环，感觉非常的困难啊。我发现了一件非常优秀的事实：三元环并不需要重标号，非常优雅。然后开始乱编做法，并且写了很多很假的东西然后开始 Hack 自己啊，有点唐。一开始我以为和链一样，三元环也需要尽可能合并环，并且尝试设计诸如「f_t 表示长度为 3t 的环最多能拆出多少个点」，尽显低手风采。但是我终于意识到比起合并环，Alice 可以强制拆环。然后很快就意识到了答案是奇环的个数啊，而且很好构造！虽然不知道为什么，写完三元环的时候就只剩半个小时左右了。

发现 74+46+100 要打铁了。试图寻找四元环的结论，但是我发现这一步非常复杂，然后又思考了一下 T1，但是还是不会优化。感觉已经尽人事，知天命了，所以比较平和地度过了最后二十多分钟的时光。

出场时看到了 N_z_ 和雷暴，Nz 似乎很寄，雷暴似乎很寄，Nz 声称 kradcigam 只有 110，什么罐头我说。然后发现 A 类都很寄。但是无所谓，MatrixGroup 获得了 270，zhuzhu2891 获得了 246，hyman00 抱抱他真糖，黄色蜜蜂 223，IceYukino 和 pp_orange 也都不出意料地非常高，SnowTrace 和 yuanruiqi 也比我高 eps。所以我依然有打铁的巨大潜力。然后发现南外也闹麻了，并且 dx 声称金牌线大约在 240，所以好像这场其实也没有 WC 和去年的 APIO 那么难，于是就不出意料要打铁了。

哦耶，铁铁的牌。

一

我在 APIO 的前两天身穿一个「TIANYI 2024」的衣服，有点好笑。但是好像并没有任何人对此表示意见？

我似乎是第 \mathcal O(1) 个进校的学生，甚至有多种性别的志愿者给我一个人引路。但是事实上地面上有地标箭头啊。省锡中似乎还有一些学生志愿者，但是好像也没有正经到哪里去。许多人随身携带小说。尝试偷拍志愿者，被发现了。然后到达了一处很像邮局的所在，路旁有一个非常有感觉的红色电话亭，我找了一会江苏在哪里，然后就领到了一个包啊，感觉包看起来还是挺不错的。然后要走到宿舍，但是为啥路这么长，以及墙壁上为啥会有金属材质的魔怔宣传文字。不过省锡中占地面积小于天一，此乃一胜。

到达世界最低谷：宿舍！宿舍的床边贴着姓名贴，然后发现 5 号床位的学生名为刘佳贺（不过貌似有一部分宿舍不存在姓名贴，于是他们在好奇 1 2 3 4 号床如何与方位建立映射）。发现附赠的本子上无锡两个大字原来是冰箱贴形式，有点难绷。哇省锡中竟然自带蚊帐，想必蚊帐里只会有一个活着的生物吧（埋下伏笔）。看到了前来寻找我的 IvanZhang。他声称宿管告诉他目前只有一个人来到宿舍，神秘的。宿舍的插头有电，这非常好。但是没有空调遥控器，于是 Ivan 从隔壁宿舍随机摸了一个遥控器过来。

尝试在校园内随机游走，然后邂逅了将与我们相伴许多天的大鹅，但是我是驯鹅高手呵呵呵怕不怕！以及差点就要提前进入比赛场地了，结果被保安赶回来了，哦哦哦啊啊啊。

然后被带领前往了自习室啊，非常牛，但是好像自己也只有前两天在自习室待过啊，非常不牛！自习室里有白色神秘假发，还有许多代码源集训老哥，非常深刻。然后就在自习室里呆了 \mathcal O(1) 时间啊，期间动用高贵的洛谷管理员权限审了一会题解。然后就被带领着去掉了食堂，并且前往了三楼的优质食堂香梅苑。但是为什么本校学生提起香梅苑的美食优先想到的却是薯条呢？中午十二点到了，后面忘了。学校领导声称现在只有 \mathcal O(1) 个学生，所以临时开放香梅苑，然后我就获得了一顿丰盛的午餐。和随后正常的省锡中食堂形成了鲜明的对比。但是大家吃完抛弃我先走了，虽然我只多花费了 \mathcal O(1) 的时间享用美食而已。立刻赶到现场的是姗姗来迟的 IceYukino，并且声称没有认出我，与后文的情节遥相呼应：Ivan 认为踢球时我长得很像 Leo_Lele 并持续认错，然而这是错误的，我对 yyc 坚决背叛、从未忠诚。

打算去小卖部看看有没有什么可以购进的物品，但是和省锡中学生透露的内容差不多：只存在无糖饮料。然后捕捉了两个大只的 sszcdjr 和 shinzanmono 正在购进东方树叶，然后我就分别买了 2 瓶绿茶、红茶、乌龙茶和椰汁。后来说一个塑料袋价值 0.1 元，于是我们就手提着搬回宿舍了。但是感觉真不如付了这一毛钱，因为这样账单就凑整了，非常可爱。不过最后（我个人）得出的结论是：感觉都不如白开水。所以还是颇为幽默的。有人推荐说某盒装饼干很好吃，不过我觉得也不过如此了。

随后就开始踢球以及和高三老哥踢球。中间穿插着若干阵雨。然后就被路过的体育老师以蓝牌罚下了，不是很能理解。回到机房后做了 \mathcal O(1) 个简单题，然后发现不会简单贪心题，有点难过，不过自己实际上什么都不会，所以其实还好，烂的程度均匀分布。然后好像就去试机了，题目是 noip 2024，所以我鉴定没有做的价值，尝试贺了一下 8KB 的 traverse.cpp 并使用 selfEval 测了一下，发现通过了高达一个测试点，非常有实力！不过我不是很有空 debug，就润了。尝试在试机过程中交换徽章，还是获得了一些徽章的，比如说 安徽的一个忘了 id 老哥 和 Z-301。然后围观了 efz 的五个人一起踩在地面上的巨幅（？）地图中的上海上，和一起抄写自己的 query.cpp，非常有实力啊！但是我是消毒药水老师的粉丝，嘟嘟嘟！然后离场时发现消毒药水在百度识图我的徽章，并且询问这个人有没有似，有点深刻^\dagger。

顺便提一句，我已经抓拍了 +\infty 次 0x3b800001 了，很帅啊。图片可能出于某些原因不能放出来。@D2T1 有无续约饭归途？

我突然想起来本来换到 2^20 老师徽章的时候承诺晚上回宿舍给他徽章，但是也没给，有点难过了。波子老师其实来 APIO 了，但是也一直没空去找波子，有点难过了。不过波子感觉还是比线上不魔怔很多！