APIO 2025 游记

· · 生活·游记

神秘三个构造交互题。

T1 很快有了一个 O(\sqrt n\log_2 n) 的二分做法，写了一下发现获得了 8+17+2=27？？尝试优化但是失败了，改了改二分时的分割点位置获得了 29，遂弃之，开 T2。这时 1h 左右。

发现 m=2 很简单，写了。猜 e>m 时初始状态即最优，写了，对了。现在 12。

发现 e=m=3 时图是一个三元环。分析了一下发现若 i\to p_i 连边则每个奇环对答案有 1 的贡献，策略是简单的。很快也想出了这个策略的最优性证明，就写。真的不好写。获得了 36，现在 2.5h。

看一眼 T3，n=2 送分，写了，5 分。v_i\le 25000 一时半会儿没想清楚，遂弃之，回到 T2。

看 T2 的 e=m-1 就是树的部分。这时才发现如果图中有一个点的度数 \ge 3 那么 Bob 可以保证分数永远不增。于是图就变成了链或环。很快会了链，写，还是难写。获得 46。3.25h。

还要冲 e=m=4 吗？原来以为有两种情况的，现在只剩四元环一种了。既然三元环时答案与环长 \bmod 2 有关，那么四元环时可能就与 \bmod 3 有关。写了，不对。发现这个猜想是错的。比如 i\to p_i 形成六元环，Alice 取 0,1,5,4 四个点那么 Bob 要么直接使一个 i=p_i 要么造出一个四元环。

然后还有什么两个二元环拼一个四元环一类的。发现可以分讨了，开写，极其难写。14:51 终于过了，再拿 24 分，T2 获得 70。

发现 e=m=3 和 e=m=4 的做法截然不同，猜测策略和 e,m 的奇偶性相关。结束前口胡了一个做法，不知道对不对。

于是 29+70+5 离场。

出来有人告诉我 T3 是签到，又有人说写 T3 的 Sub2 获得了 100？？？让他说了一下做法，发现真的很简单。这下亏麻了。

又有人说他的 T1 的 O(\sqrt n\log n) 获得了 78。我问他做法，结果他告诉我他的询问大小是

\sqrt n+\sqrt\dfrac{n}{2}+\sqrt\dfrac{n}{4}+\sqrt\dfrac{n}{8}+\dots

？？？？

这 不 是 O(\sqrt n) 吗。

马上发现自己的做法也很容易优化到这个次数。又亏麻了。

最后发现 Cu 线 80。T1 实际评测出了 28，总分 28+70+5=103。惊恐地发现如果最后 T2 e=m=4 没做出来那么我就是 103-24=79<80。还听说 T2 最高分只有 70。

怀疑自己是否获得成就：所有 T2 获得 70 分的选手中，总分最低者。

抽象。