APIO 2026 游记 & 退役记

· · 生活·游记

前情提要：省选 d2t1 100 \rightarrow 10，遗憾离场。

于是作为退役选手参加了 APIO。

比赛日

你说得对但是 9 点开始比赛为什么要 7:15 集合？

比赛门口能领棒棒糖，我拿了一根橘子味的，感觉很好吃。

到座位上发现右边隔着四五个座位是 xqw，拜谢。

开场发现 T2 是交互，我不会做交互，那咋办。

依旧正序开题，但是这个 T1 怎么这么困难？

感觉是容斥状物，但是想了 20 min 似乎没啥能把指数级优化到 poly 的想法，先不管了看 T2。

T2 怎么是 4 个独立的 sub，那看起来很好拼暴力啊，于是光速写完前三个 sub。

最后一个 sub W = 2000, K = 7，那显然不能只利用大于小于了，等于应该也得用，考虑一些三分状物。

考虑三分递归需要递归到一个和原问题比较相近的形式，猜测递归到一个区间，所以考虑三等分原区间。 注意到大于小于形式很对称，所以询问应当同时包含左子区间和右子区间。 考虑判断的是和，而如果这两部分内没有隐藏的数，和是一个定值，所以考虑通过比较和与这个定值的大小来 check，发现确实能唯一对应递归到的区间，所以问题就只剩下怎么构造和。 值域是 $[1, 2200]$，为了保证三分过程不会被其他数影响，用于构造和的部分不妨钦定其 $\ge 2000$，注意到可以存在加法和减法，所以感受一下这样是合理的。 于是利用一些二进制状物，向集合里加入 $2000 + 1, 2000 + 2, 2000 + 4, \cdots, 2000 + 128$，以及 $2000$ 和 $2200$ 各 $496$ 个，总共恰好 $1000$ 个，且能构造出所有需要构造的值。 然后就做完了，三分到小区间的时候可能会有一点点 corner case，但是是小问题。 此时大概过去 1.5h，得分 0 + 100 + 0。 然后还是回来看 T1，感觉容斥钦定上升段会很大便，改成钦定下降段，这样就只有区间内包含 $0/1$ 个已填的点两种情况。 大概有点思路了，考虑怎么记状态。尝试想了一些类似 CSP-S T4 的想法，发现可以一部分正着做一部分倒着做，且分别只需要 $O(n)$ 的状态，那么就 $O(n^4)$ 了。 此时大概过了 2h，得分 65 + 100 + 0。 感觉 $O(n^3)$ 不一定很简单，于是扔了去看 T3。 我会 $O(mq)$！发现能拿 40，感觉很牛啊，于是光速写完。 看上去特殊性质不是很好些，于是又回去看 T1。 盯了一会转移，发现两个部分都能分步转移，那去掉 $n$ 也是简单的，于是就 $O(n^3)$ 了。 此时大概过去 3h，得分 100 + 100 + 40。 按次序移动到邻域内感觉很不牛，考虑特殊性质怎么做。 发现链就是邻域改成区间，那么一个点如果下一个区间要移动，则只会移动到两个点，所以可以预处理所有贡献然后用二分状物求答案。 然后开始想邻域半径不小于点数一半咋做，发现这个等价于所有邻域都有交，那不就是移到邻域交里面吗？ 这时候我突然意识到邻域交仍然是邻域，所以求区间邻域交可以 st 表。 那不是基本做完了？考虑求一个点为左端点的最右区间满足邻域交非空，那么这个区间和下一个点开始的任意区间的邻域都不交，而不交的邻域从一个移动到另一个时移到的点是固定的！ 于是可以倍增维护，这样查询就 $O(\log m)$ 了。 想完还剩 1.5h，先相信再相信，直接启动！ 大概花了 0.5h 写出一个代码，但是怎么求邻域交写错了一万个地方？ 边对拍边调，还剩 10 min 终于正确性调对了。 selfeval 一测，怎么只有 56？怎么一车点 T 飞了？ 发现预处理是 $O(m\log^2 m)$ 应该是瓶颈，而且求 LCA 和 k 级祖先写的都是倍增。 改 $O(1)$ LCA 和 k 级祖先是来不及了，改成树剖看看能不能多跑过几个点吧。 于是花 4 min 紧急改成树剖，一测，怎么直接过了？ 此时还有 4 min，selfeval 300。 出场碰到喵仔，他说他 90 + 100 + 28，感觉很神秘。 然后问了若干人，似乎都是 200-。 15：30 查分，没挂，感恩。 ---------------------------------------- 以下是一些退役感想。 退役后发挥出巅峰水平虽然幽默，但某种意义上也是完美谢幕。 我的 OI 生涯算是非常神秘了，NOIP 每年都是 100 + 100 + ? + 100，省选每年都能爆个大的。 至少拿到了 WC、APIO 的金牌，目标也算完成了 2/3。 总之，退役快乐，whk 加油。