APIO2025游记

allenchoi · 2025-05-18 17:12:08 · 生活·游记

省流：银牌 -> 铜牌

Day 1(5.15)

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

Day 2

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

Day3

比赛日。
早上灯自动开了，结果六点二十就醒了，难绷。
吃完早饭后去合了张影，然后就入场了。
开 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！！！