Yandex Cup 2024 Semifinal 游记

· · 生活·游记

前情提要：预选赛游记。上述游记比较魔怔向（所以被归类为闲话），本篇游记则相对较为正式。

省流：1+1+1+0+1+0=5，青少年组 rk 9 / 122，总榜 rk 82 / 617。

本场比赛分两组，青少年组和非青少年组，题目相同，但是分开算排行（本人被分到青少年组了）。共有 617 人进入本场比赛（半决赛），非青少年组选 20 人进入莫斯科的决赛，青少年组好像是选 10 人（晋级了但是我去个毛线）。

比赛从 11 月 3 日的 22:00^{\mathrm{UTC+8}} 开始，洛谷 IOI 赛制（即按照所有题目 AC 提交的总时间排序，但是错误提交不加罚时；我第一次见到这种东西是在洛谷上面，故将其命名为“洛谷 IOI 赛制”），2 个小时 6 个题。本来觉得太晚了，如果打了第二天模拟赛会似；但是后面想了想，名额很少，比较珍贵，不去就是浪费了一个名额。所以就想着打一会儿就睡觉，也算是没浪费这个机会。

从学校赶回家后匆匆就开始了比赛。上来开 T1，是个签到，直接贪心排序做完了。

接着开 T2，发现题面有点长，是个 \bmod 10^9+7 期望题，先跳了。

开 T3，哟这不矩阵快速幂求路径数的板子题吗！随即发现直接对于每个询问硬搞是不行的，于是把邻接矩阵的 2 的整数次幂预处理出来，这样后面查询可以直接用向量乘，复杂度少个 n。时限开了 4\mathrm{s}，跑了 2.153\mathrm{s}，比较极限但是好歹过了。

回去搞 T2，发现预处理组合数之后算个概率，做差一下再转回期望就可以了。

接着看 T4，看了半天没看懂它在干什么。直接开 T5，看起来很可做！直接对于每个质因数跑出虚树然后求个直径端点，之后对于虚树上每个原始的点更新。写写写，为什么预处理质因数就耗了 496\mathrm{MB} 啊！感觉有点可怕，但是 ML 512\mathrm{MB}，所以感觉还不赖。接着写虚树，写写写样例过了，交一发发现 WA 了。仔细一看输出格式，为什么有 -1 的情况，而我的程序根本没有输出 -1 的可能——发现 a_i 可以等于 1，改改改，再一交，TLE！发现 LCA 还是 O(\log n) 查询的，改成 O(1) LCA，交一发，评测机卡住了很久，但是过了。时间和空间分别是，1.638\mathrm{s} / 2\mathrm{s} 和 502.41\mathrm{MB} / 512\mathrm{MB}，空间但凡少开个 10\mathrm{MB} 都过不去。

感到睡意袭来，于是去睡觉。

后面的以后再更，先等着查 CSP-S 的分。 拖延了，那就继续回来写。

比赛完看榜，似乎晋级了啊。但是肯定去不了俄罗斯，于是决赛的事情就作罢了。不过这还是一次挺不赖的参赛体验。感到非常开心！

现在只能希望接下来的 CCPC 重庆站和 NOIP RP++。