APIO2025游记

省流：银牌 -> 铜牌

早上九点出发去机场。
开车到岗顶然后坐地铁，全程 3 号线但是两次换乘（体育西路 and 短程换长程），广州地铁无敌了。
飞机延误了，下午快三点才到。无锡得机场是军民两用的，第一次到这种机场呢。
到省锡山，领了一堆纪念品后，拎包入住。收拾好后在学校里逛了一圈，超大超好看。
晚上试机，是 NOIP 的题目，打了个 T2T3，测一下栈空间，没啥问题就不管了。

白天都在讲课。
早上是图论和集合幂级数。
图论讲了几道好题，但听的似懂非懂；集合幂级数一开始就掉线了，去网上看了几篇文章，后面干脆刷手机了。
下午博弈论加构造。博弈论讲的有点快，后面就在自己看课件了。构造题感觉就是传统、为明天比赛铺垫的（（
晚上开幕式，有越剧表演，听不懂。后面有灵岛的讲话，前面忘了后面忘了。
回到宿舍后摆了一个钟，然后看了一下上午讲的题，十一点半睡觉。

比赛日。
早上灯自动开了，结果六点二十就醒了，难绷。
吃完早饭后去合了张影，然后就入场了。
开 T1。一开始想二分，但不会。后来想到如果两个数 $\mod n$ 相同，那答案就是两者之差的因数，枚举一下就行了。
联想到生日悖论，随机生成 $10^5$ 个数，$99.6$ 的概率有相同的。然后对序列二分，每次随机分成两半，如果其中有一半有相同的就递归。
期望次数 $4\times10^5$，期望得分 $50$ 左右。自测的时候在 $40$ 到 $60$ 左右波动。
然后开 T2,T3。
都没啥思路，去看了眼 T3，想了二十分钟还是不会，于是决定拿个 $5$ 分跑路了。
再去看 T2。
首先 $m=2$ 是好做的，因为一次一定能让一个置换环长度减一。
继续思考，如果原图有度数超过 $2$ 的点那么分数一定不会增加，直接 return。
然后考虑链。发现如果有 $\ge m$ 个 $p_i\ne i$ 时，把不合法的点按搜索序拍起来，那么合并要么直接让一个置换环长度减一要么把两个置换环并起来，这样子分数不会变少。
然后是 $m=e=3$。
发现一个长度为三的置换环可以让答案加一，所以尝试每次分出去一个长为 $3$ 的环。假设每次只会操作一个置换环内的点。发现每次操作相当于将环分成三段，然后 Bob 选其中一段，再把另外两段并起来。然后，如果环长为偶，则三段中必有一段是偶，Bob 可以把环分成两段偶的；而如果环长为奇，则 Alice 可以选择 $1+1+x$，则得到一个偶环一个奇环。因此，每个奇环会有 $1$ 的贡献，而偶环没有。然后如果合并两个环不会增加奇环数量，所以不用考虑这种情况。
想出来这一坨之后，先写了 T2 代码，然后再去写 T3 $5$ 分。
之后去研究 T2 $m=e=4$ 的情况。借鉴上面的思路，一个长为 $4$ 的环可以有 $1$ 的贡献。考虑将环先拆成长为 $2,3$ 的“基本环”。两个 $2$ 可以并成一个 $4$，然后带来 $1$ 的贡献之后缩短成 $3$。两个 $3$ 可以合成一个 $6$，然后把 $6$ 拆成 $2$ 和 $4$，$4$ 再变成 $3$。构造策略的时候如果有长度大于 $4$ 的环先拆掉，不然就合并两个 $2$ 或 $3$，直到达到答案。有个坑点，原图 $4$ 个点在环上的顺序不一定是 $0,1,2,3$ 这样，被坑了一会。
写完还剩 20min，摆烂了。
估分 $55+70+5$。
出来之后跟其他人随便聊两句就回宿舍了，开摆！
下午去复评，T1 只有 $25$？？？
询问次数炸了，百思不得其解。在本机用 SelfEval 多测几次，基本都是 $50$ 左右，然后有一两发 TLE $25$？？？
恼，申请重测。然后一个砖家过来看了眼代码，发现里面有 rnd(time(0)) 不能重测？？？气死了！！！
感觉 TlE 是换了 grader，或者说赛时样例根本没上强度。非常不合理啊。周围也有一个大佬 T1 被创了，一起吐槽。然后还发现，如果换成一个好一点的随机种子就可以稳定在 $55$？悲愤！！！
吃完饭回宿舍一算，发现 $20$ 组多测，每次生日悖论 $99.6$ 的正确率，总的正确率只有 $88$ 左右，傻了。再看看群里，说赛时样例 $T=10$，c?? w??nm！！！
$25+70+5$，感觉又要铁了。
晚上索性不去听讲题了，在宿舍摆烂。
晚些时候听人说 $T1$ 要整题重测，只好拜月了。

早上去听讲，在公示栏上发现成绩变成 $45+70+5=120$ 了，还算能接受吧...
然后听讲听不懂，玩手机。
吃完午饭后赶紧去社会活动（一个涉密的船舶研究所，还不让带手机），结果来回车程两小时，在那里就看了半小时宣传片，纯唐诗。
晚上结营、颁奖，说银牌线 $130$。wc 真的换个种子就银了...
然后一堆抽象讲话。颁奖还只给一张奖状，连个牌子都没有？？？六百六十六

感觉这次比赛搞得挺唐的。放三道脑电波题，然后 $T1$ 又有点随机区分，无语。
不过也算有了个金钩（吧？）