APIO2025 游记

zhengjinyi · 2025-05-20 22:07:24 · 生活·游记

省流：萌新第一次打 APIO 极限卡到 8 钩线。

Day -?

前情提要：CSP 316 T2 挂 10pts 成 306 去不了 WC。

Day -1

坐了七个小时的动车总算到了无锡。

晚上试机学习使用 selfeval，写了 NOIPT1。之前以为 APIO 完全是 IOI 赛制，现在才知道是 pretest。

学校和宿舍环境挺好的，不过宿舍没温的饮用水比较神秘。蚊子竟然会飞到蚊帐里面，恼。

Day 0

上午图论几乎没听懂，集合幂级数听到以前学过的知识+eps 就突然啥也听不懂了。下午博弈非常抽象，感觉很牛，听到后面越来越困。构造场就是跟着对脑电波。

晚上看开幕式，打那个什么的能力？

22:30 就自动熄灯了，睡得挺香。

Day 1

上机测试！

运气比较好和 A 类选手一起被分在在小考场，空调很冷。

\color{green}{如需去卫生间，请举此牌。}

开场瞄一眼三个题，构造浓度也太高了。第一反应觉得 T1 最可做，开始想 T1，想了 1h 只会 25pts 乱搞，上界好像 7e5 左右，写掉再说。这个时候广播讲题目是乱序的，不早说。

打了一下 T2 的 12pts 简单暴力。T3 看上去似乎比较可做，决定把时间投入到 T3。

先猜最大值，发现是 \lfloor\frac{n}{2}\rfloor\times\lceil\frac{n}{2}\rceil\times 90°，两两配对。要求价值和不降的限制很恶心，构造次数上界也很松，不知道怎么用。在草稿纸上画了 \frac13 张纸的图，想了很久想出来一个很贪心的做法，在配对过程中直接找每一条是否跟着动，正确性一点不会证。先写了一发三方发现对了，优化成 n^2\log，可以获得 74pts，但是操作次数是平方的。又盯着 T3 想了一会毫无优化空间，操作次数限制是一个 log，感觉完全不知道怎么用。

码风被 0-index 阴暗扭曲了，又不知何故跟着输入格式开了一摩尔 vector，感觉三份代码都丑死。

还剩不到 2h。T1 没思路，觉得 T2 比较有思考空间，感觉 3 和 4 两个 task 可以做一做。仔细地刻画这个看上去很奇怪的博弈，分讨慢慢推，发现树的情况下只有链有用。还剩大约 80min 的时候把 10pts 的 task 会了，代码要构造方案非常恶心，写了许久总算拿到 10pts。写完又去看了看另外两题，还是毫无思路。然后仔细思考 24pts m=3 的 task，似乎不难，画了 3,4,5,6,7 的环找规律和分析。还有 12min 的时候证明出来奇环贡献为 1，偶环贡献为 0，比 10pts 的 task 还简单，恼。急。剩下 10min rush 这个做法，迅速写完了，一发挂，两发挂，三发挂，遗憾离场。