APIO 2025 游寄 最后更新于 2025-05-19 21:22:15

为啥我要写这个。 看到 hack 连第一步都不会做，然后意识到可以生日悖论随一个出现哈希冲突的序列，随便二分一下第一个出现哈希冲突的前缀然后暴力枚举哪个数冲了并枚举因子。 听上去很对啊。枚举因子可以忽略不计量级很小，二分也只是根号 $\log$，操作次数限制才 1e6，这不随便过？ ？？？$10^6$ 怎么是有分的限制？限制怎么是 $1.1\times 10^5$？代 $B=\sqrt{n}$ 算出来我怎么只能得 $1$ 分？ 这个时刻我意识到这个做法有点完蛋，不过生日悖论不占瓶颈交互次数，肯定要优化二分。 然后开始思考一些做法，这个时候我并没有想到分成左右两侧的这种做法（讲题的时候听到我觉得比较神奇。）于是发现自己不会规避这个二分，并且我的生日悖论预期也占了 1e5+，不如先放弃。 看到 permgame 更是觉得这个题不能要了，又交互又博弈还限制交互次数，随意猜了 $e>m$ 的做法，又写了 $m=2$ 获得了高达 $12$ 分的高分。 比赛已进行两个半小时。现在的得分是：$12$ 分。还有 hack 的 $25$ 分部分分没写，rotate 没分。 看了眼 rotate 感觉大事不妙，怎么又是个构造。先写了 $16$ 分部分分，然后感觉随便排序对位匹配一下就好了。 一点多 SelfEval 显示我 rotate 得了 $100$ 分，我感觉自己成功签到，开始继续做 hack。 把自己的做法瞎实现了一下，一开始序列长度取的 $10^4$，把样例先调过了，随机输了个数发现只需要 $1.2\times 10^5$ 次，严重卡不满？然而我想多了，SelfEval 显示我超过了 $10^6$ 的询问次数。 这个做法询问次数方差太大了，又输了 $10$ 个数前 $9$ 个都大概 5e5 以内第 $10$ 个直接跑到了 1e6+eps。 胡乱调了参数又多得了 $6$ 分。感觉分数单峰可以三分参数，最后取到的参数让我 SelfEval 斩获了 $48$。遗憾的是最终只有 $37$ 分。 又开始思考一些奇奇怪怪的做法，比如二分。但是我觉得判定性问题不好做（不会 BSGS 属于是）更觉得这是严格 $\sqrt{n}\log n$（事实上随便优化成 $\sum_i \sqrt{\dfrac{n}{2^i}}$ 并斩获 $70+$ 分）就放弃了这条路子。 后来又去想了 permgame。最后十分钟发现树疑似是唐，但我必定写不完了，只能开摆。 赛后出场时发现图要么是链要么是环，疑似是诈骗，要被区分了。 原来环很难做啊。 没想到自己有 Ag 拿，应该是字典序放题导致的。