2024.7.25 牛客多校赛 4
Nuyoah_awa
·
·
生活·游记
单干，没有鲜花，直接进入正题。
G
将军饮马。
性质：对称哪个点对答案无影响，两点都对称一定劣于只对称一点。
将一点分别对于 x,y 轴对称，求对称后两点最小距离。
code
I
用优先队列处理出每个点最靠左都跟这个点有临边的点。然后枚举 $l$，双指针维护最靠右的合法 $r$，则 $r$ 可取 $l\sim r$。
[code](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70419628)
## C
一个排列， 每次选 $4$ 个数任意交换位置，问最少几次操作可排序。
考虑若 $a_i = i$，则这个点不用动。否则这个点上的数需要去到 $a_i$ 很想第三场的一个题，唯一指向可以想到连边。特别的，每个数最后变为 $i$ 有唯一的入边，所以是一系列环。
考虑对于每个环 $h_1\to h_2 \to \dots \to h_n \to h_1$，则每次选 $4$ 个至少可将三个数归位，假设选 $1\sim 4$ 环变为 $h_4 \to h_5 \to \dots \to h_n \to h_4$，则操作次数为环的 size 除三，若之后剩 $3/4$ 个即余数为 $0/1$，则最后一次可直接归位，余数为 $2$ 的情况需要多来一次，特别的，每个环相对独立，所以两余数为 $2$ 的环拼凑只需操作一次（最后向上取整）。
[code](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70423599)
PS：开始想了个假贪心，吃一发罚时。
## H
对于多个数，每次可以选择一个数，并且将所有大于或小于他数关于其对称，求最大值和最小值的差。
套路题，跟上一场一道很像，答案为所有数的差的 gcd。
[code](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70424832)
## A
一棵树上边建边边询问，求一个点开始的最长路径。
因为边权都是 $1$，所以最长路径长度就是子树内最大深度减该点深度。
边建边边用带权并查集维护即可。
[code](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70426199)
## F
构造一棵树，使其节点个数尽可能少，且有两点满足 $f(u)-f(v) = x$。
考虑 $u$ 到 $v$ 有唯一的简单路径，这条路径上的点对于两点贡献和相等，考虑在路径上连其他点改变差值。
对于一个点，到两点的简单路径一定是先经过 $u,v$ 间的简单路径上的一个点后再分别走向两个点，则贡献差即为从简单路径上连出的位置距离两点的差值。
很明显，若已知总节点个数则所有点连接到 $u$ 或 $v$ 上差值最大。
不妨设总共 $x$ 节点，简单路径上 $b$ 个点，$a$ 个点连在 $u$ 上，则差值为 $a \times (b+1)$。
则可得方程：
$$\begin{cases}a + b + 2 = x\\ a\times(b+1) = ans\end{cases}$$
由于 $x$ 是定值，根据均值不等式可得当 $a = b+1$ 时 $ans$ 最大。特别的因为 $a,b$ 均为整数，所以有时也可退而求其次取 $a = b$。
于是可以考虑二分求出理论最少点数。
但是考虑构造的话，我们发现若原一点连于 $u$，我们将其改变为连在距 $u$ 距离为 $1$ 的点上后，他对于答案的贡献减少了 $2$。所以对于一个点数 $x$，若不改变 $b$，则答案与 $x$ 同奇偶，若改变 $b$，则分类讨论为：
1. $a = b+1$ 时，$ans = t ^ 2 \to ans = (t+1)\times(t-1)$，即 $ans = ans - 1$，所以 $ans$ 不一定与 $x$ 同奇偶，可以构造。
2. $a = b$ 时，$ans = a \times (a + 1) \to (a-1)\times (a+2)$，原为偶，后依然为偶则此次枚举出的 $a,b$ 无法构造，只能再引进一个点从而构造出这样一棵树。
[code](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70434402)
### 摆烂。
完结撒花~
[back](https://www.luogu.com/article/sop1ckso)