APIO2025游寄

diqiuyi · 2025-05-19 20:52:26 · 生活·游记

day -1

不知道为什么买了今早八点的机票。到无锡吃了午饭后就三点了。然后就放弃了游玩。

day 0

同样是不知道在干嘛。早上的时间也不够玩啥的，在万达随便玩了会。不过台球还挺好玩的。

下午三点前往省锡中，学校很大，但是好像整个学校的厕所的冲水装置都绵软无力，只能起到稀释的作用/jk。饭堂还行。

day 1

讲课，基本都没听懂，就当无事发生吧。

day 2

比赛日。

上来先看 A，先是瞎胡了一个几个 log 的做法，后面发现是假的，浪费了一点时间。这时提示题目顺序是按字典序排序，那这个题可能并不容易啊。

后面发现应该就是个生日悖论状物，然后可以写一个分治状物找到 (x,y) 满足 n\mid x-y，之后只用很小的代价就可以找出答案了。这样是 O(\sqrt{n}) 次操作的，但是常数太大，看着不太能过。

首先考虑怎样避免检验整个序列，发现可以构造一个长为 2\sqrt{n} 的序列使得 1\sim n 都出现过，这样会好不少。另外考虑到只需要把 n/2\sim n 包含在内即可，所以序列长度其实是 \sqrt{2n} 的。但好像还是过不了。

此时过去时间稍久，而我还没看 BC 的题意，所以考虑开始同时思考 BC。思考了一秒钟发现 B 只有链或环需要操作。那看来这个题一定是签到了吧，C 先不去想了。还好没有一直企图做出 A 啊。

B 拿了 6 分后继续观察，大胆猜测链就是把所有 len>m 的环长度变为 m-1，调了半天只过了 m=2。之后发现可以通过把两个环拼在一起来把它们合并成一个环，所以答案 \ge n-m+1。这个东西写了 30 行，这时候已经开始两个半小时了，而我仅有 22 分。

这时候我猜测环的情况就是把所有环分组，然后如果一组的环长和 \bmod\ m-1 的结果是 1 那么就会产生 1 的贡献。但是这个我也不会做。但是 m\le 4 的时候这个用脚维护，所以我相信了这个是对的。m=3 写了 50 行，此时我获得了 46 分。m=4 写了 100 行，但是死活过不了啊，怎么回事呢。

没时间了，于是我把 A 给写了，为了避免被定向卡我加上了随机化，可以获得 [50,70] 分/qiang。为了调参，我反复提交了多次，然后忽然过不了第一档了？原来我之前写挂了吗，改回来以后可以稳定 \ge 70 了，并交出了一发 100 分。算了一下现在期望得分大概是 125 分。此时大概是 14:30，好像不得不开 C 了。