牛客练习赛130题解

赛后总结：

$A,B,C$ 符合预期。

赛时来看， $D$ 题的样例有点弱，但是由于看到 wa 率大之后，发现的比较晚，考虑到时间因素，就没在赛时补充。~~

$E$ 的树形 DP，可能由于 $D$ 的影响，导致写的人比较少，同时可能也因为其需要点码量。

$F$ 属于 $D$ 的加强，通过 $D$ 的启发，考察计数能力。

update:

D 题，题解给出了一些比较强的 case，便于大家赛后debug。

$B$ 题，数据稍弱（感谢评论区提出），赛后增强了一些case数据。

A

若 $x=y$ ， $0$ 次。
若 $x$ 与 $y$ 的二进制存在子集关系， $1$ 次。
否则 $2$ 次。

B

先考虑无解的情况：

$R\times(k-1) h\leq 0$ 或者 $L\times k h>0$ 。

否则必然存在一种合法的构造方式，这里给出一种比较简单的构造方法：

考虑前 $k-1$ 步先设置成 $R$ ，第 $k$ 步设置成 $L$ 。

令 $s=R\times(k-1) h L$ ，若 $s>0$ 说明骑士血量是多了，需要调整前 $k-1$ 步的大小。

由于要保证骑士前 $k-1$ 步不能死，所以考虑从第 $k-1$ 步倒序调整，对于每个 $R$ 还能减少： $\min(s,R-L)$ ，然后更新 $s$ 。

C

推一下式子，很容易得到：

\sum_{i=1}^n\sum_{j=1}^nf_{\min(i,j)}\times g_{\max(i,j)}=\sum_{i=1}^n(f_i\times\sum_{j=i 1}^ng_j g_i\times\sum_{j=1}^if_j)

考虑修改怎么维护这个值，由于是单点修改，我们可以考虑本次修改对答案带来的变化即可。

记 $V$ 为目前的答案，容易推出：

若令 $f_i=x$ ，则 $V\to V (x-f_i)\times(2\times\sum_{j=i 1}^ng_j g_i)$ 。
若令 $g_i=x$ ，则 $V\to V (x-g_i)\times(2\times\sum_{j=1}^if_j-f_i)$ 。

故我们只需要两个树状数组动态维护 $f,g$ 的前缀和即可，时间复杂度 $O((n T)\log n)$ 。

D

首先考虑最好的序列的特征，要让未出现的最小正整数最大，显然我们需要尽可能的让 $1,2,3,..$ ，尽可能出现在序列中。

又观察到 $LCM(1,2,3,...,32)>10^{14}$ ，那么未出现的最小正整数最大就是 $32$ 。

令 $d=LCM(1,2,3,...,k)$ ，此时 $d$ 满足 $d\leq Y$ ，且 $LCM(d,k 1)>Y$ ，那么我们的答案至少是 $d$ 。

那么我们答案能不能更大呢？

显然是可以的，考虑序列中的另一个数 $c>k$ ，是有可能存在 $d<LCM(d,c)\leq Y$ 的。

不妨设 $LCM(d,c)=d\times i$ ，那么我们可以枚举其序列最终可能的 $LCM$ 。

现在问题转化为如何判断最好的序列的 $LCM$ 可以为 $d\times i$ 。

结合算术基本定理：

若 $x_1=p_1^{a_1}\times p_2^{a_2}\times ..\times p_{n_1}^{a_{n_1}}$ ， $x_2=p_2^{b_1}\times p_2^{b_2}\times ..\times p_{n_2}^{b_{n_2}}$ ， $x_m=...$

那么 $LCM(x_1,x_2,...,x_m)=p_1^{\max(a_1,b_1,...,c_1)}\times p_2^{\max(a_2,b_2,...,c_2)}\times ...\times p_{n}^{\max(a_n,b_n,...,c_n)}$

我们可以考虑 $d\times i$ 相比 $d$ ，多出了哪些 $p^a$ 。

结合 $LCM(1,2,3,...,32)>10^{14}$ 与 $LCM(d,k 1)>Y$ ，容易发现 $1\leq i\leq 31$ 。

那么将 $i$ 进行质因数分解，其最多只有 $3$ 个不同的质因子，那么令 $V=p_{1}^{a_1}\times p_2^{a_2}\times ...\times p_m^{a_m}$ （ $m\leq 3$ ）， $V$ 表示 $d\times i$ 相较于 $d$ 多乘的质数次幂部分。

由于我们只有 $n$ 个数，有 $k$ 个数已经确定了填了 $1\backsim k$ ，那么还剩下 $n-k$ 个数，我们需要选择一下数放进去，可以使得其多出 $V$ 这部分。

我们要保证往序列里面加入一些数，使得其多出 $V$ 这部分，同时要满足序列的最大值 $\leq X$ 。

考虑到 $n$ 的限制，可能会导致放了 $1\backsim k$ 之后，剩余的位置不够，我们可能需要把一些 $p^a$ 合并，由于 $m\leq 3$ ，直接暴力检查所有可能即可。

这里给出两种做法：

第一种：直接大力分类讨论

$n-k\ge m$ ，那么我们可以直接往序列里面加入： $p_1^{a_1},p_2^{a_2},...,p_m^{a_m}$ 这 $m$ 个数。
否则说明我们位置不够，否则我们需要合并一些质数次幂，即将他们乘到一起，按 $m=1,2,3$ 进行分类讨论即可。
- 如果 $n-k=1$ ，那么说明只剩下一个位置，只能把所有 $p^a$ 相乘，然后直接判断其是否 $\leq X$ 。
- 特别的如果 $m=3$ ，如果只需要合并一次，可以考虑选择最小的两个 $p^{a_1},p^{a_2}$ 乘起来，然后判断。

第二种：可以直接 DFS 或者全排列枚举合并的可能，或者写个简单的状压 DP。

第二种做法比较不容易出错，第一种做法的分讨实现起来需要注意细节。

一些比较强的 case：

input:
8
32 100000000000000 72201776446300
32 1145 69872686884000
31 555 72201776446300
32 78956421 69872686884000
31 98788985 72201776446309
7 100 372
23 16568 1629547920
17 1145 8648640

output:
69872686884000
67543597321200
53569059944400
69872686884000
69872686884000
360
1629547920
7927920

E

出题人做法：

令 $dp[u][i][j][0/1]$ 表示以 $u$ 为根的子树，用了 $i$ 次操作，其中有 $j$ 个异色的儿子， $0/1$ 表示 $u$ 的颜色。

不难发现其转移就是树上背包的合并，每次枚举 $i,j,su,nc,sv$ ，其中分别表示：在合并了前几个儿子，当前以 $u$

为根的用了 $i$ 次操作，以 $v$ 为根用了 $j$ 次， $u$ 的异色儿子个个数， $v$ 的异色儿子个数，直接暴力转移是 $O(n^5)$ 级别的。

考虑经典的子树 size 的优化：

for (int i = 1; i <= std::min(sz[u], k); i++)
	for (int j = 1; j <= std::min(sz[v], k) && i + j <= k; j++)

这里优化完，复杂度可以做到 $O(n^4)$ ，考虑继续优化，观察树上背包合并的转移式子。

$tmp[u][i j][su][nc]=\max(tmp[u][i j][su][nc],dp[u][i][su][nc] dp[v][j][sv][nc])$

$tmp[u][i j][su 1][nc]=\max(tmp[u][i j][su 1][nc],dp[u][i][su][nc] dp[v][j][sv][!nc] \frac{sv\times(sv-1) su\times(su-1)}{2})$

容易发现 dp[v][j][sv][!nc] + sv * (sv - 1) / 2 + su * (su - 1) / 2 像这样的式子可以提前预处理出来最大值，因为都是用的儿子 $v$ 的 $dp$ 去算的。

可以在转移之前，先做一些预处理：

static int maxv1[N][2], maxv2[N][2];
for (int i = 0; i <= std::min(k, sz[v]); i++) {
    for (int j = 0; j < 2; j++) {
        maxv1[i][j] = maxv2[i][j] = -inf;
    }
    for (int sv = 0; sv <= (int)g[v].size(); sv++) {
        for (int nc = 0; nc < 2; nc++) {
            maxv1[i][nc] = std::max(maxv1[i][nc], dp[v][i][sv][nc]);
            maxv2[i][nc] = std::max(maxv2[i][nc], dp[v][i][sv][nc] + sv * (sv - 1) / 2);
        }
    }
}

这样转移最内层循环就可以被优化掉，最终时间复杂度 $O(n^3)$ 。

在内测验题中，其实也有其他的状态设计，例如可以不记录异色儿子个数，而是在转移的时候去处理。

F

经过 Easy 版本的启发，现在考虑如何进行计数。

我们令 $d=LCM(1,2,...,k)$ ，其中 $k 1$ 为未出现的最小正整数最大值。

我们需要枚举最后序列的 $LCM$ 为 $d\times i$ ，并且计算其方案数，最后累加即可。

至此，在保证未出现的最小正整数最大的情况下，我们需要解决两个问题：

$LCM$ 为 $d\times i$ 的方案数是多少。
若已知可以 $a_i$ 选择的数量为 $cnt$ ，且需要保证 $1\backsim k$ 至少出现一次的方案数是多少。

容易发现问题 $2$ 是一个经典的容斥问题，结合容斥原理和组合数学可以求解。

对于问题 $1$ ，我们直接求 $LCM$ 等于 $d\times i$ 的不好求，我们考虑定义： $f_i$ 表示 $LCM$ 为 $d\times i$ 的约数的方案数有多少？

记 $cnt_i$ 为 $d\times i$ 所有满足 $\leq X$ 的因子个数，不难发现直接就变成了问题 $2$ 。

定义 $g_i$ 表示 $LCM=d\times i$ 的方案数，由简单的容斥可以得到： $g_i=f_i-\sum_{d\times j\ |\ d\times i}g_j=f_i-\sum_{j\ | \ i}g_j$ 。

考虑每部分计算的时间复杂度，对于 $f_i$ 的这些因子我们可以提前预处理出来，这块复杂度并不高。

对于每次枚举 $i$ ， $cnt_i$ 的计算可以从预处理的 vector 二分出来，这里 $log$ 复杂度就可以解决。

考虑枚举 $i$ 和问题 $2$ 的计算，复杂度大约为 $\lfloor \frac{Y}{d}\rfloor\times k\times \log n$ ，假设预处大约用时为 $C$ ，最终复杂度大约为 $O(C T\times \lfloor \frac{Y}{d}\rfloor\times k\times \log n)$ 。

这里复杂度瓶颈在于每次计算方案，需要枚举 $i\times d$ ，然后里面要做组合数学，容斥，还需要用到快速幂。

考虑到时限，最终给定 $4$ s，只要预处理做好了，正常的实现可以在 $2\backsim 3$ s 内跑过。

实测，其实可以当 $n$ 太大，做快速幂的时候，可以考虑降幂，可以优化快速幂。

牛客练习赛130出题人题解

牛客练习赛130题解

A

B

C

D

E

F