APIO 2025 游记

· · 生活·游记

更好的阅读体验

Day -1 (5.15)

今天考语文。

但我跑路了。

上飞机前从电脑往手机里传了十几首歌，准备在飞机上听，然后发现自己没带耳机。还好我还传了一部小说过去，感觉几个小时应该读不完二十万字。

在小说里发现了字符串“文化课”，有点害怕。

离降落还有半个多小时的时候广播说机场要求关上遮光板，到机场不准拍照。关了遮光板后还关灯，于是开始聚精会神地睡觉。

坐了很久的大巴到学校。在报道处看见了一张地图，上面似乎是他们学校某届毕业生的去向，有意思的是北京的位置写了“北京大学 11 人，清华大学 2 人”。

发了一件衣服和一个包，包里有各种奇奇怪怪的东西，感觉有用的也就一支笔和一个 U 盘了。

到了宿舍打开随身 WIFI，-90 dBm 还是能用的。

试机，写个 assign 还 WA 了，调了半小时。

Day 0

昨晚没睡好啊，床上有点太热了。

听课，好难啊听不懂。

开幕式氛围感很强。

Day 1

空调开到 22 度，睡眠质量显著提高。

入场，发现发了好多好吃的。

前 4h 打了 78+22+16，后 1h 啥也不会，开始狂吃，并感觉两部分时间一样长。

更加详细的赛时情况

最开始先读了一遍题，由于 T2 题目太长不是很好理解，并且 T3 的 2 \times 10^6 次操作和一次操作可以更改多个 a 值看起来很吓人，所以认为 T1 是最简单的。

随后想了一个 25pts 做法并在第 40min 写完。

想到构造序列，用 O(\sqrt{n}) 的长度覆盖 1, 2, \cdots, n - 1 的所有差值，尝试序列 1, 3, 6, 10, 15, \cdots，有问题。然后想到 1, 2, \cdots, \sqrt{n}, 2\sqrt{n}, \cdots, n，没什么问题。

尝试在这个做法外面套一个二分做到 O(\sqrt{n}\log{n})，这个东西刚好卡进 10^6，预计得分 28pts，感觉写了会很亏，于是继续想。

想到自己可以不用覆盖 1, 2, \cdots, mid，只需要覆盖 l + 1, l + 2, \cdots, mid，于是变成了约 1.5 \times 10^5 次询问，78pts。

想 T2，先写了 m = 2 和 e > m，12pts，e = m - 1 没什么思路，去写了一个 T3 的 n = 2，目前得分 78 + 12 + 5 = 95。

想到了 T2 这个拆环、并环的过程，写出了 e = m - 1，猜测 T3 是配对 \lfloor\frac{n}{2}\rfloor 对达到最优效率，于是写了 1 \le a_i \le 25000，此时已经过去 4h。

继续思考如何优化 T1，想到哈希冲突的具体次数还没用上，一直在尝试利用这个信息。

写了一个利用信息每次将二分区间缩小 \frac{3}{2} 的做法，WA 了，感觉这个缩小有问题，把缩小条件改严格一点，没 WA 但询问次数达到 1.9 \times 10^5，不如直接二分优。

比赛结束时为 78+22+16。

一些想法

T2 的 e = m = 3 和 T3 正解没打出来很可惜，“因为我觉得 T1 是最简单的，所以就在 T1 拿了很多分”很神奇。

可能都是因为难度排序的比赛打多了，更习惯先做 T1 吧。

出来怎么听说 T3 比 T1 简单啊？

听讲题，听完 T3 上去讲了一下自己的悲惨经历（sub2 check）。

发现自己场上发明了 BSGS。

T2 太震撼了！

Day 2

不懂这个社会实践在干什么。

颁奖，现在全世界都要知道我铜牌了。

“结束了，孩子们”。

Day 3

还能写 Day 3 我是没想到的。

飞回 CQ，但发现自己被迫爆照了。

link

我就是那个穿着黄白衣服被拍了四张的，这里就不放了。