APIO2026 游记

· · 生活·游记

前情提要 CSPS 擦线进冬令营，冬令营擦线铜牌，NOIP 擦线进 APIO。为什么不能擦线进 D/fn/fn/fn

T1 计数 T2 交互 T3 数据结构，这是 APIO？读了遍题感觉没有去年的题神秘，尽管我没去过 APIO2025，但我刷过视频前两天看了看题。

都没有思路所以顺着做。T1 20 分状压 DP 是简单的，性质 A 可以类似插入 DP 做到 \mathcal O(n^3)，不过这个做法没法拓展到 p_i \ne 0 的情况。再后面的部分分就彻底没思路了。开 T2，感觉四个包是四个完全不同的题。前两个包是容易的，第三个包肯定是用二进制做，然后我可以询问前缀和与当前位置的大小，就能确定 Sally 的蛋糕在排序后的位置。再扫一遍就能求出答案。不过这是个 2 \log。然后第一步是可以二分的，这样我就是 \log + \log \log。ok 很牛的做法。第四个包依旧没有思路，只会放 2000 个一然后二分，可以获得 eps 分。开 T3。显然有 \mathcal O(nq \log n) 的暴力（\log 是求 LCA），然后又又又没思路了。树是链的情况好像可以倍增，复杂度二 \log。写了一会发现细节居多，注意到只有八分，放弃为好。写完所有暴力就只有一个小时了。中间又尝试了写 T3 的链不过越写分类讨论情况越多。然后我猛然发现 T3 还有一档 \mathcal O(nq) 的部分分，这是不是把两两 LCA 的预处理一下就能过了。哇还真是。

出场得分 119。怎么别人都会 T2？第三个包竟然可以把 \log \log 改成 30 - \log，第四个包竟然是注意到 3^7 > 2000！！

后面忘了。出场后一直以为自己是 Fe，直到闭幕式开始前几分钟一个志愿者跟我们说待会上台要跟着他走才反应过来自己有 Cu。赢麻了。

回收开头：APIO 擦线铜，擦线八级勾。