题解|2024暑期牛客多校04
比赛链接:2024牛客暑期多校训练营4
A.LCT
题意
给定一棵有根树,问按顺序给定的前 $i$ 条边组成的森林中,以 $c_i$ 为根的树的深度。
解题思路
按步骤生成森林的过程,与并查集合并的过程一致。
因此用带权并查集,维护每个点的深度和答案,利用路径压缩降低时间复杂度。
参考程序
1 | struct DSU{ |
C.Sort4
题意
给定一个长度为 $n$ 的排列 $p$ (即序列中 $1$ ~ $n$ 的每个数恰好出现一次)。
每次操作可以选择4个元素,并任意交换它们的位置。
求使得排列变为升序的最少操作次数。
解题思路
把排列看作由 $i\rightarrow p_i$(下标从1开始) 构成的图,这个图中有若干个环,表示这个环中的元素可以通过交换回到原来的位置。
长度为 $3,4$ 的环,可以通过一次操作还原;
长度为 $2$ 的环,可以 $2$ 个环一组通过一次操作还原;
长度大于 $4$ 的环,每次操作可以让 $3$ 个元素回到原来的位置,使得环的长度减少 $3$,直到环的长度小于等于 $4$。
根据这个原则,计算最终答案。
参考程序
1 | void solve() |
H.Yet Another Origami Problem
题意
给定一个长度为 $n$ 的序列 $a$,每次可以选择一个元素 $a_i$,执行以下操作之一:
- 所有原来比 $a_i$ 小的数 $a_j$ : $a_j=a_i+2(a_i-a_j)$ ,即原来 $a_j$ 比 $a_i$ 小多少,现在就比 $a_i$ 大多少。
- 所有原来比 $a_i$ 大的数 $a_j$ : $a_j=a_i-2(a_j+a_i)$ ,即原来 $a_j$ 比 $a_i$ 大多少,现在就比 $a_i$ 小多少。
问任意次操作后,序列 $a$ 中最大元素和最小元素之差 $max(a)-min(a)$ 的最小值。
解题思路
每次操作:
- 对序列 $a$ 排序去重,求出差分数组 $d$ 。
- 选定次小元素 $a_2$ ,执行操作 $1$ ,使得最小元素 $a_1 = a_2 - d_1$ 变成 $a_1’ = a_2 + d_1$ 。
假设重新排序去重后,新的 $a_1’$ 相邻的两项为 $a_j,a_{j+1}$ ,步骤1中这两项的差分是 $d_j=a_{j+1}-a_j$ 。
那么当 $a_i’$ 插到中间时,新的差分数组的变化如下:
- 第1项 $d_1$ 删去(因为 $a_1$ 变成了 $a_1’$ 后移)
- 原本的 $d_j$ 被替换为 $d_j’=d_1-\sum\limits_{k=2}^{j-1}d_k$ ,$d’_{j+1}=d_j-d_j’$ 。
第2点变化可能比较难理解,给出如下例子:
- $a = [1,6,8,10,13,15]$ (原序列排序去重)
- $d = [5,2,2,3,2]$ (差分数组)
- $a_1=1,a_2=6,d_1=5$ (选定次小元素做操作1)
- $a_1’=a_2+d_1=11$
- $a’ = [6,8,10,11,13,15]$ (新序列排序去重,$a_1’$ 位于第4位)
- $d’ = [2,2,1,2,2]$ (新差分数组)
差分数组的变化:
- 第1项 $d_1=5$ 删去
- 第4项 $3$ 变为:$d_1-d_2-d_3=1$ 和 $3-1=2$
这个变化的意义就在于,它证明了任意次操作后的差分数组中的元素,是原差分数组中元素的线性组合,且随着操作次数增加,$\sum d_i$ 逐渐减小,直到 $a$ 仅剩2个元素。
线性组合能达到的最小值为 $\gcd\limits_{i=1}^{n-1}d_i$ 。
参考程序
1 | void solve() |
G.Horse Drink Water
题意
将军饮马问题,将军在第一象限的整点 $(x_0,y_0)$ ,河流由 $x$ 正半轴和 $y$ 正半轴组成。
问将军碰到河流再前往 $(x_1,y_1)$ 的最短路径长度。
解题思路
将起点以 $x$ 轴、 $y$ 轴为对称轴,分别对称到第四、二象限,比较这两个点和终点的距离,取最小值。
参考程序
1 | void solve() |
I
// TODO