牛客练习赛130题解

赛后总结：

符合预期。

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

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

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

update:

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

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

A

• 若 ， 次。
• 若 与 的二进制存在子集关系， 次。
• 否则 次。

B

先考虑无解的情况：

• 或者 。

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

考虑前 步先设置成 ，第 步设置成 。

令 ，若 说明骑士血量是多了，需要调整前 步的大小。

由于要保证骑士前 步不能死，所以考虑从第 步倒序调整，对于每个 还能减少：，然后更新 。

C

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

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

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

• 若令 ，则 。
• 若令 ，则 。

故我们只需要两个树状数组动态维护 的前缀和即可，时间复杂度 。

D

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

又观察到 ，那么未出现的最小正整数最大就是 。

令 ，此时 满足 ，且 ，那么我们的答案至少是 。

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

显然是可以的，考虑序列中的另一个数 ，是有可能存在 的。

不妨设 ，那么我们可以枚举其序列最终可能的 。

现在问题转化为如何判断最好的序列的 可以为 。

结合算术基本定理：

若 ，，

那么

我们可以考虑 相比 ，多出了哪些 。

结合 与 ，容易发现 。

那么将 进行质因数分解，其最多只有 个不同的质因子，那么令 （）， 表示 相较于 多乘的质数次幂部分。

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

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

考虑到 的限制，可能会导致放了 之后，剩余的位置不够，我们可能需要把一些 合并，由于 ，直接暴力检查所有可能即可。

这里给出两种做法：

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

1. ，那么我们可以直接往序列里面加入： 这 个数。
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

出题人做法：

令 表示以 为根的子树，用了 次操作，其中有 个异色的儿子， 表示 的颜色。

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

为根的用了 次操作，以 为根用了 次， 的异色儿子个个数， 的异色儿子个数，直接暴力转移是 级别的。

考虑经典的子树 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++)

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

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

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

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);
        }
    }
}

这样转移最内层循环就可以被优化掉，最终时间复杂度 。

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

F

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

我们令 ，其中 为未出现的最小正整数最大值。

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

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

1. 为 的方案数是多少。
2. 若已知可以 选择的数量为 ，且需要保证 至少出现一次的方案数是多少。

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

对于问题 ，我们直接求 等于 的不好求，我们考虑定义： 表示 为 的约数的方案数有多少？

记 为 所有满足 的因子个数，不难发现直接就变成了问题 。

定义 表示 的方案数，由简单的容斥可以得到：。

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

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

考虑枚举 和问题 的计算，复杂度大约为 ，假设预处大约用时为 ，最终复杂度大约为 。

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

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

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