APIO 2025 游记

今天考语文。

但我跑路了。

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

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

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

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

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

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

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

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

听课，好难啊听不懂。

开幕式氛围感很强。

空调开到 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 3 我是没想到的。

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

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