ACGO 挑战赛 #25 全题解
T1
直接模拟即可。
时间复杂度:O(n)O(n)O(n)。
空间复杂度:O(n)O(n)O(n)。
T2
模拟机器人走路,并使用 set 记录走过的点。每次走到一个新点时候先判断是否在 set 里即可。
时间复杂度:O(nlogn)O(n \log n)O(nlogn)。
空间复杂度:O(n)O(n)O(n)。
T3
注意到题目最下面一句话:请注意,如果不同的排列得到相同的数,只计为 111 个。
所以我们枚举所有平方数,总共 10n210^\frac{n}{2}102n 个,看每一个平方数能否重排为 sss 即可。注意,000 也是平方数。
时间复杂度:O(n10n2)O(n10^{\frac{n}{2}})O(n102n )。
空间复杂度:O(n)O(n)O(n)。
T4
考虑维护全局 mex。使用 set 维护所有未出现的数。
设 cnt[x] 表示 xxx 出现次数。当 cnt[x] 减少为 000 时,把 xxx 插入到 set 中;当 cnt[x] 增加为 111 时,把 xxx 从 set 中删除。
修改操作可以看作一次插入和一次删除。
另外,本题值域 10910^9109,看上去十分吓人,但容易发现,mex 最大只有 nnn,所以 set 只维护 0∼n0 \sim n0∼n 就可以。
时间复杂度:O((n+q)logn)O((n+q) \log n)O((n+q)logn)。
空间复杂度:O(n)O(n)O(n)。
T5
考虑一种情况,就是 u,vu,vu,v 之间有一条链(也就是 u→a1→ a2→⋯→at→vu \rightarrow a_1 \rightarrow\ a_2 \rightarrow \dots \rightarrow a_t \rightarrow vu→a1 → a2 →⋯→at →v 的情况)。那么容易发现 uuu 和 a2a_2a2 会先连边,然后 uuu 和 a3a_3a3 连边,……以此类推,最后 uuu 和 vvv 连边。
因此,实际上同一个连通块内的所有点会互相连边。
使用并查集维护每一个连通块的大小 siz,答案为 m−∑isizi(sizi−1)2m-\sum_i \frac{siz_i(siz_i-1)}{2}m−∑i 2sizi (sizi −1) 。
时间复杂度:O((n+m)logn)O((n+m) \log n)O((n+m)logn) 或 O((n+m)α(n))O((n+m)\alpha(n))O((n+m)α(n))。
空间复杂度:O(n)O(n)O(n)。
T6
假设我们在点 uuu,已经计算出 f(u)f(u)f(u) 的考虑从 uuu 向儿子 vvv 移动会产生什么改变。
容易发现,uuu 到 vvv 的子树里每一个点的路径减少 111,uuu 到其它点每一个点的路径增加 111。
定义 preupre_upreu 表示 uuu 子树内的点权和,得到:
f(v)=f(u)−prev+preroot−prevf(v)=f(u)-pre_v+pre_{root}-pre_v f(v)=f(u)−prev +preroot −prev
先暴力算出 f(1)f(1)f(1),然后根据该公式推到所有点上,取 min\minmin 即可。
时间复杂度:O(n)O(n)O(n)。
空间复杂度:O(n)O(n)O(n)。