【10.27】【VP】Codeforces Round #746 (Div. 2)

ALL：7
AC：2
补题：2

这场题出的挺好（

---

B. Hemose Shopping

题意：

给你两个数 $n,x$，代表有 $n$ 个元素。

现在问你，能否通过交换两个距离大于等于 $x$ 的数 $a_i,a_j$ （即 $|i-j|\ge x$），使得数组可以按照非递减的顺序来排序。

如果可以，输出 YES，否则，输出 NO。

思路：在序列左端和右端各覆盖一个长度为 $x$ 的区间，可以发现中间被覆盖两次的元素是无法交换的。对于最多覆盖一次的元素，发现可以直接或者间接交换任意两个元素的位置，即可以排序。

AC代码：https://codeforces.com/contest/1592/submission/178078664

---

C. Bakry and Partitioning

题意：

一棵树有 $n$ 个节点，第 $i$ 个节点的点权为 $a_i$ 。（注：树是一个有 $n$ 个节点、$n-1$ 条边的连通图）

你需要回答：能不能选择这棵树中的至少 $1$ 条边、至多 $k-1$ 条边删除，使得删除完这些边的树满足以下条件：

• 每个联通块的点权异或和相等

数据范围： $n,k(2\le k\le n\le 10^5),1\le a_i\le 10^9$

思路：从结果开始考虑，如果最终有奇数个节点，那么可以缩到剩 $3$ 个异或和相等的点；如果有偶数个，那么可以缩到剩 $2$ 个异或和相等的点。

那么先考虑是否有一条边使得切开这条边两个子树各自异或和相等，有的话即有解；否则，至少要删去两条边，在 $k\ge 3$ 的前提下继续判断。

考虑两个异或值为全局异或的两个连通块在原树的位置：1. 两棵子树不相交。2. 一棵子树属于另一棵子树。我们计算每棵子树最多有多少个不相交的异或为全局异或的子树（不算上自身）的数量，记为 $cn{t}_i$ 。如果是前者，则要满足 $cn{t}_i\ge 2$ ；如果是后者，需要满足 $cn{t}_i=1\text{AND}{x}_i=0$ 。

AC代码：https://codeforces.com/contest/1592/submission/178094659

---

D. Hemose in ICPC ?

题意：

给一棵 $n(2\le n\le 10^3)$ 个点的树，定义 $Dist(u,v)$ 为 $u\to v$ 路径上的边构成的边权集合的 $\gcd$，且 $u\ne v$。

每一你可以询问交互库 $x$ 个点的点集 $X$，交互库会返回 $X$ 中， max ⁡ { D i s t ( u , v ) } , u , v ∈ X \max\{Dist(u,v)\}, u,v \in X max{Dist(u,v)},u,v∈X 。也就是说，交互库会找到 $X$ 中 $Dist$ 最大的一个点对 $(u,v)$ 并且返回它们的 $Dist$。

最多可以询问交互库 $12$ 次。你需要找到整棵树中 $Dist(u,v)$ 最大的那个点对 $(u,v)$。若有多个，任意一个都合法。

交互格式：

询问：? k v_1 v_2 ... v_k

回答：! u v

思路：问题等价于寻找树上最大边权对应点对。我们考虑树上的一个点集连通块，这个连通块不断向外拓展时， $\max (\gcd (u,v))$ 是不减的。我们可以在先序遍历序列上二分（这样点集一定是联通的），得到最大边权。

AC代码：https://codeforces.com/contest/1592/submission/178105654