CF #969 题解

· · 个人记录

CF Round 969 题解（全）

验题人，upsolve AK，但是无法限时 AK。

A

考虑一次操作不能选两个偶数，至少要选两个奇数。

因此假设有 k 个奇数，最多进行 \lfloor \frac{k}{2} \rfloor 次操作。

这个上界是显然能取到的，考虑每次取出相邻的奇数和中间的偶数。

B

假设最大值是 v，很容易证明若干次操作后最大值仍然是 v 对应的值。

模拟即可。

C

根据“小凯的疑惑”，本题可以将 c 加上 \gcd(a,b) 的充分大倍。因此可以将每个数对 \gcd(a,b) 取模。

假设取模后排序的结果是 a_1，a_2，\dots，a_n，我们最优解必定形如 [a_k,a_{k+1},\dots,a_n,a_1+\gcd(a,b),a_2 + \gcd(a,b) , \dots,a_{k-1}+ \gcd(a,b)]，枚举 k 即可。

D

注意到对于根 rt 和叶子 u，如果 rt 和 u 的颜色相同那么权值为 0，否则权值为 \pm 1。因此，先手需要最大化和根颜色不同的节点的数量，后手需要最小化它。

当根的颜色确定的时候，问题非常简单。

否则稍加分析可以得到，谁去确定根的颜色谁吃亏，而且在根确定之前确定叶子节点也是不划算的（你的功劳可能给别人做嫁衣裳去了）因此两个人都会先选非根非叶子节点，然后某个人不得不确定根节点，剩下交错选叶子结点。

经过 irris 大神提醒，发现写漏掉了，我自裁。如果已经确定的两种颜色的叶子数量差的绝对值大于 0，那么先手确定显然是更优的。

模拟即可。

E

首先观察到，题目给的编号实际上就是一个 DFS 序。这样保证了所有 i \to (i \bmod n + 1) 路径的总长度为 2n-2，且每条边恰好在一条路径中出现。

对于每条路径，如果其中所有边都被确定了那么 f 就是所有边的和。否则，f 取 w 减去路径外所有确定的边的和。假设路径上确定的边和为 w_1，目前确定的总和为 w_2，那么 f = w - (w_2-w_1) = w + w_1 - w_2。

前者很好维护，后者维护这样的边的总数，这样的边的 w_1 的和。

没确定一条边，只有 O(1) 个量发生变化，直接维护即可。

F

分析一下一个序列稳定之后的结果。

它只能是一个公差为奇数的等差数列。我们只需要公差为 1。

给定一个序列，求出差分数组，并且把其中偶数元素取奇数部分，设得到集合 S。

最后的公差 d 必满足 \forall u \in S，d \mid u。即 d \mid \gcd_{u \in S} u%。

一个序列是合法的，当且仅当 d \mid \gcd_{u \in S} u。这个是容易证明的。

差分是不关心顺序的，因此我们可以记 b_i = \dfrac{| a_i - a_{i+1}|}{2^k} 使得它恰好为奇数。

对于每个 l，符合条件的 r 满足：

使用 st 表维护区间 \gcd，使用二分统计答案即可。

G

如何判断一个序列是否合法？

显然，最大值和次大值放序列两边，最小值和次小值放他们边上，以此类推。

以长度为 5 和 6 的序列分别举例：

[5,1,3,2,4]

和

[6,1,4,3,2,5]

我们发现，只要保证 i+j = n+1 的 a_ia_j \le k 即可……吗？

当长度是奇数的时候，最中间那个位置并不需要和自己乘起来。这一点很重要。

我们先不管它吧，对于一个排好序的序列 a，假设最后将 x 个数变为 1，那必定是最大的 x 个数，需要满足：

如果 $n$ 是偶数，直接求 $i+r_i$ 的最小值（其实 $i > n-x$ 的时候也是对的，可以想想为什么）。发现 $a_r$ 其实只有 $O(k^{0.5})$ 种可能（整除分块），因此我们取的 $i$ 也只有 $O(k^{0.5})$ 可能。 如果 $n$ 是奇数，直接求 $i+r_i$ 的最小值可能会把答案算小。因为对于某个 $i$ 它可能不需要满足。这时候需要某种数（即整除分块所有分段点）恰好被移动到序列的中间。那么它的左边不能有和它整除分块后同种的数，因此必须是某一种数的端点。发现必须这种数开头的位置 $i+r_i$ 已经取到了最小值（而且是唯一最小值）。复杂度 $O((n+q) \sqrt k)$。 ## H 这题可以用点分树水过去。 容易发现，只要所有点的度数 $\le 3$，且根的度数 $\neq 3$，就一定可以补全为二叉树，此时 $d$ 为根到其他节点的最远距离，即到直径两端点的较大距离。 取出直径中点，我们只需要找和它距离最近的，度数不是 $3$ 的点。可以使用点分树。 `multiset` 常数太大，可以换为延迟删除的 `priority_queue`。复杂度 $O(n \log^2 n)$。 ## I 孩子这辈子第一次切 Div.1 最后一题，很激动。 样例对 $$ \left[ \begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix} \right] $$ 无解说明很有启发性。如果我们要出现这样的结构，假设第一列最后一次涂了 $1$，那么第二行最后一次涂 $2$ 必在其之后，第二列最后一次涂 $1$ 亦在其之后，第一行最后一次涂 $2$ 在其之后。。。唉，那 $a_{1,1}$ 只能是 $2$，矛盾了。 所以，假设第 $i$ 列 $1$ 的位置是 $S_i$，则 $\forall 1 \le i < j \le n$，$S_i \subseteq S_j$ 或 $S_j \subseteq S_i$。 于是整张图表必须和一个杨表同构。 整理为杨表，很容易发现把每列 $1$ 的个数拿出来，最少的操作次数就是： $$ \sum_{i=1}^n [a_i \neq 0] + \sum_{i=1}^{n-1} | a_i - a_{i+1} | $$ $f$ 就是（考虑哪些操作时可以交换的） $$ (\prod_{i=1}^n (\sum_{j=1}^n[a_j=i])!)(\prod_{i=1}^{n-1} (a_i-a_{i+1})!) $$ 然后就可以分类讨论了。你既要考虑是否和杨表同构，又要考虑这一大堆阶乘的变化。 复杂度 $O(n+m)$，给我写成了 $O(n + m \log n)$，不过无所谓。