APIO2024 游记

Lucky_Xiang · 2024-05-21 19:56:10 · 生活·游记

前言

演讲的时候总是犯困，每次都睡了好几觉。

正篇

这次 APIO 的 OJ 用的是 QOJ 的框架，评测可以快速返回结果了！

T1

很快做了出来，用时 10min。

T2

很快写出了一个 dp。但是这个 dp 转移不太方便，需要维护 n 个单调队列，有前缀加、查最小值的操作。

前缀加不好进行。于是我又开了一个树状数组维护偏移量，再直接在凸包上二分找最小值的位置，通过了前两个 subtask，获得 10 分。（subtask 3 在第 23 个点 WA 掉了）

仔细检查了各个部分，发现不可能爆 int，而数组也没有开小，但是我怎么也发现不了错误。直到剩余 2.5h 的时候才发现这样不一定是凸包，二分这个步骤就是错误的。于是把二分换成暴力，再将前两个 subtask 特判掉，发现这时在 28 号测试点 TLE 了。

于是开始乱搞，队列大就使用二分，队列小就使用暴力，这时通过了 subtask 3，喜提 40 分。（subtask 4 在 36 号测试点 WA 掉了）

然后就是各种调参，但是 36 号测试点非常强，怎么也过不去，把 25 发提交全部用完了，结果还是没 AC。

很难受。

T3

开始做 T3 的时候，我 T2 还有 4 次提交机会，所以打算打完部分分就继续乱搞 T2。结果发现最低档部分分都不会做了。冷静下来发现可以通过造一个菊花图解决，喜提 5 分。

于是开始做 subtask 2。可以造两个菊花，但是这样只有一种删边方式能够让其出错。我以为交互库是随机的，就放心做了。写完了以后发现在第 7 个点 WA 掉了，此时我意识到交互库可能是自适应的。于是再将编号随机化，结果还是在 7 号测试点 WA，说明交互库按照树形态自适应，就放弃了。