挑战赛#25 全题解

亚洲卷王 AK IOI

2025-12-01 19:39:00

发布于：北京

11阅读

0回复

0点赞

ACGO 挑战赛 #25 全题解

T1

直接模拟即可。

时间复杂度： $O(n)$ 。

空间复杂度： $O(n)$ 。

T2

模拟机器人走路，并使用 set 记录走过的点。每次走到一个新点时候先判断是否在 set 里即可。

时间复杂度： $O(n \log n)$ 。

空间复杂度： $O(n)$ 。

T3

注意到题目最下面一句话：请注意，如果不同的排列得到相同的数，只计为 $1$ 个。

所以我们枚举所有平方数，总共 $10^\frac{n}{2}$ 个，看每一个平方数能否重排为 $s$ 即可。注意， $0$ 也是平方数。

时间复杂度： $O(n10^{\frac{n}{2}})$ 。

空间复杂度： $O(n)$ 。

T4

考虑维护全局 mex。使用 set 维护所有未出现的数。

设 cnt[x] 表示 $x$ 出现次数。当 cnt[x] 减少为 $0$ 时，把 $x$ 插入到 set 中；当 cnt[x] 增加为 $1$ 时，把 $x$ 从 set 中删除。

修改操作可以看作一次插入和一次删除。

另外，本题值域 $10^9$ ，看上去十分吓人，但容易发现，mex 最大只有 $n$ ，所以 set 只维护 $0 \sim n$ 就可以。

时间复杂度： $O((n+q) \log n)$ 。

空间复杂度： $O(n)$ 。

T5

考虑一种情况，就是 $u,v$ 之间有一条链（也就是 $u \rightarrow a_1 \rightarrow\ a_2 \rightarrow \dots \rightarrow a_t \rightarrow v$ 的情况）。那么容易发现 $u$ 和 $a_2$ 会先连边，然后 $u$ 和 $a_3$ 连边，……以此类推，最后 $u$ 和 $v$ 连边。