5.21 Contest 题解

A. Permutation

给定四个数 $a,b,c,d$ 求

$$\gcd(\prod_{i=a}^bi,\prod_{i=c}^di)$$

其中这样的询问有 $T(T\le 10)$ 次。$a,b,c,d \le 10^7$。

考虑最大公倍数的另一种形式，如果

$$a=\prod p_i^{\alpha_i}, b=\prod p_i^{\beta_i}$$

则：

$$\gcd(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}$$

于是，我们考虑对于每个质数，处理出来 $a!,b!,c!$ 和 $d!$ 有几个该质因子，然后 $\gcd$ 的质因子数量就是 $\min(b-a,d-c)$。

复杂度就是 $O(N+T\sum\limits_{p\in \mathcal{P}}\log_p N)$，是要严格小于 $O(NT)$ 的。这是因为质数一共只有 $\ln$ 个，但是质因子数量每次的底数都在增长。

给定一棵树，每个点有点权，删去一条边的代价是每个边连接联通快的点权最大值之和，求全部删边的最小代价。

首先，感性理解地，先删点权最大的周围的边是更好的。

于是就有一个做法是先确定删边顺序，然后逆向加边，使用并查集维护。

但是我没想到，于是搞了个乱搞做法。

我们有一个函数 $solve(root,type,from)$ 表示操作节点、操作类型和上一次操作的节点。另外维护一棵线段树来求最大点权的点的编号。

我们刚开始初始化 $dfn$，以 $1$ 为根，然后建立线段树。

然后考虑 $solve(x,type,fa)$ 操作。

如果 $type=0$：

那么我们 $x$ 子树中最大的点的编号，然后进入操作 $solve(y,1,x)$。

将 $y$ 子树内的权值覆盖成 $0$，再加上目前 $x$ 子树内的最大权值和 $a_y$，继续找最大值，直到没有。
如果 $type=1$：

那么我们需要删除 $x$ 的连边。首先删除与它儿子的连边，然后加上贡献。

对于每一个被删除的边，我们进入它的操作 $solve(y,0,x)$。

于是我们就可以操作了。

首先考虑三维的转移。

设 $f_{i,x,y}$ 表示第 $i$ 层有一个人在 $x$，另一个人在 $y$。

但是这样显然不优，因为我们总是一个人在 $a_i$。

因此，我们只需要记录 $f_{i,j}$ 表示一个人在 $a_{i-1}$，另一个人在 $j$ 的时候的最大值。那么得到转移方程：

$$f_{i,j}=\min(f_{i-1,j}+|a_i-a_{i-1}|,\min(f_{i-1,k}+|k-a_i|))$$

然后使用线段树优化即可。