题解 - Codeforces Round 1106 (Div. 2) A-E

A

不论进行了怎样的重排，我们都可以发现，执行 $-1$ 操作的总次数是 $\sum_i a_i - \sum_i b_i$。

所以剩下的约束就是 $a_i\ge b_i,\forall i$。

如果一开始给定的就满足上述条件，我们不需要重排。

否则，设 $a_p=\min a,b_q=\min b$。

• 如果 $a_p<b_q$，那么无论 $a_p$ 放在哪个位置，它都会比对应位置的 $b$ 更小，所以一定不存在合法重排。

• 如果 $a_p\ge b_q$，我们可以通过交换论证法。如果最终存在一个合法的重排，使得 $a_i\ge b_i,\forall i$，那么我们把 $b_q$ 对应的元素换成 $a_p$：

  1. $q$ 这个位置仍然合法；

  2. $a_p$ 原先在的位置，被换上了一个 $\ge a_p$ 的元素，仍然合法。

所以只要把 $a,b$ 分别从小到大排序，看是否都成立 $a_i\ge b_i$ 即可，复杂度 $O(n\log n)$。

B

令 $V_{p,a}$ 表示 $a$ 的质因数分解中 $p$ 的次数，那么对于给定的条件，我们可以枚举所有的 $p$，将式子化成一个 $\max,\min$ 相关的式子。

由于是对于一个相同的 $p$ 考虑， 下面将 $V_{p,x}$ 简写为 $V_x$。

原式即 $\min(\max(V_a,V_b),\max(V_b,V_c))=\min(V_a,V_c)$。

不妨设 $V_a\le V_c$，我们考虑 $V_b$ 相对于 $V_a,V_c$ 的位置：

1. $V_b\le V_a\le V_c$，那么 $LHS=\min(V_a,V_c)=V_a$。
2. $V_a< V_b\le V_C$，那么 $LHS=\min(V_b,V_c)\neq V_a$。
3. $V_a\le V_c<V_b$，那么 $LHS=\min(V_b,V_b)\neq V_a$。

因此，原式成立当且仅当 $V_b\le V_a$，也就是说 $V_b\le \min(V_a,V_c)$。

转化为 $\gcd$，也就是 $b\mid \gcd(a,c)$，这等价于 $b\mid a$ 且 $b\mid c$。

因此只需要枚举 $b$ 并枚举它的所有倍数即可，复杂度 $O(n\log n)$。

C

考虑从节点 $u$ 向下走，什么时候和子孙能达到的 Guild 不同。

这里可以把树看成若干层，那么如果想要与子树达到不同的 Guild，那么这个 Guild 必须要跨越至少两个子树。

考虑将子树的深度从大到小排序，我们逐个枚举到达 $u$ 的距离 $h=0,1,\dots$，可以看出如果超过了深度的次大值，那么就会与达到与子树能达到相同的 Guild，否则就不会。

这里不需要真的排序，只需要取非严格次大值即可。

复杂度 $O(n)$。

上面是官方做法，我这里给出一个毛毛虫火箭的做法。

令 $dp(u,d)$ 表示与 $u$ 距离为 $d$ 的集合，那么我们可以长链剖分进行转移。

由于树的性质，这里并集一定是无交之并，所以我们可以直接给每个数赋一个随机权，用 $\sum_{v\in S} w_v$ 表示集合 $S$ 的哈希值。

根据长链剖分的性质，总共被更新的集合为 $O(n)$ 个，那么我们只需要把这些更新之后的集合全部插进一个 set 里，最后取 size 即可。

那么根据这样的分析，会有 $O(n)$ 个互不相同的集合。如果你使用了 $64$ 位随机数，它们哈希碰撞的概率上界是 $n^2/2^{64}$，是可以接受的。

Fun fact: 我因为使用了 mt19937 rng 并且直接调用了 rng()，生成了一堆 $32$ 位随机数，这让碰撞概率爆炸，并且我最后也没发现，直接给我掉了 $100$ 多分。

复杂度 $O(n\log n)$。

D

这个我赛时纯猜的，所以下面梳理一下如何证明这个结论。

首先，对于质因子 $p\mid n$，一定会单独放一层。

如果这一层有别的元素 $q$，那么 $\gcd(p,q)\neq 1$，一定就会有 $\gcd(p,q)=p$，也就是说 $p\mid q$。按照要求，这样的 $q$ 应当在编号更大的层中。

这已经导出了 $\omega$ 层，分别是 $L_1,L_2,\dots,L_{\omega}$。

我们考虑在 $L_\omega$ 层的 $p$，它到达 $n$ 的某一条路径：$p,ps_1,ps_1s_2,\dots, ps_1s_2\cdots s_k$，其中 $ps_1s_2\cdots s_k=n$，并且 $s_i$ 都是质数。

考虑其中任意一个 $ps_1s_2\cdots s_i$，去掉任何一个 $s_j$ 后，按照要求，都应当严格在前面的层中。

那么这就会有额外的 $k$ 层，其中 $k+1$ 就是 $n$ 的所有质因数次数之和。

所以答案不可能比 $\omega +k$ 更优，并且可以证明这样的方案总是可以构造出来的。

考虑 $\Omega(n)$ 表示 $n$ 所有质因数的次数之和，那么我们按照 $\Omega$ 值给 $n$ 的所有因子 $d$ 分类：

• 对于 $\Omega(d)=1$，即质因子，根据前面的讨论，它们会单独放到 $\omega$ 层；
• 对于 $\Omega(d)=2\sim k+1$ 的因子，我们把 $\Omega$ 值相同的放在一层。

这样的话一共是有 $\omega+k$ 层，下面证明这个方式是合法的。

对于 $\Omega(d)=m\ge 2$ 的层，对质因数种类进行数学归纳性构造：

• 当只含有 $p_1$ 时，显然只能放 $p_1^m$，如果 $V_{p_1, n}< m$ 则不能放。
• 假设 $p_1\sim p_k$ 都可以，此时加入 $p_{k+1}$，我们将所有 $d$ 分为两类：含有 $p_{k+1}$ 和不含 $p_{k+1}$：
  1. 如果不含 $p_{k+1}$ 的没有放，那么所有含 $p_{k+1}$ 的显然可以随便放，它们之间的 $\gcd$ 都是 $\ge p_{k+1}>1$ 的。
  2. 否则，按照归纳假设，不含 $p_{k+1}$ 的元素存在合法排列使得相邻 $\gcd > 1$。之前排列的最后一个数 $q$，由于 $\Omega(d)=m\ge 2$，随便取一个质因数 $r$，让 $(q/r)\times p_{k+1}$ 作为含 $p_{k+1}$ 的集合的第一个元素，那么这样就让这两段的分界线的 $\gcd=q/r >1$。

复杂度 $O(n+q)$，线性筛。

E

考虑如果所有的 $\mathtt{N}$ 已经确定，答案是什么。

设 $i$ 位置是 $\texttt{F}$ 时，$f_i=1,t_i=0$；否则 $f_i=0,t_i=1$。

枚举区间 $l,r$ 后，不难看出答案是 $\sum_{i=1}^n f_i - \sum_{i=l}^r f_i+\sum_{i=l}^r t_i$。

设 $w_i=f_i-t_i$，那么答案由两部分构成，$\sum_{i=1}^n f_i-\sum_{i=l}^r w_i$。

我们可以形式化地写出最终式子：

$$\max_{S}\left(\min_{l,r}\left(\sum_{i=1}^n f_i - \sum_{i=l}^r f_i+\sum_{i=l}^r t_i\right)\right) =\max_{S} \left(\sum_{i=1}^n f_i-\max_{l,r} \sum_{i=l}^r w_i\right)$$

其中 $S$ 表示替代 $\texttt{N}$ 的合法方案。

然而，枚举方案是 $O(2^n)$ 的，显然不行。

此时我们需要考虑求内层最小值的过程，实际上只需要总 $\texttt{F}$ 数、最大后缀和、最大子段和，就可以在添加一个元素的状态下求出新的最小值。

设计 $dp_{i,f,s}$ 表示前 $i$ 个位置中，总 $\texttt{F}$ 数为 $f$，最大后缀和为 $s$ 的最小权值的最大值。注意最大子段和可以通过这个权值与 $f$ 直接算出来。

这样把 $O(2^n)$ 的状态划分到了 $O(n^3)$ 个状态。

转移不难，这里就不写了，复杂度 $O(n^3)$。