6.8 模拟赛题解

A. Cut Ribbon (CF189A)

Des

给定四个数 $n,a,b,c$，要求把 $n$ 长度的绸带划分为若干段，每一段的长度必须是 $a,b$ 或者 $c$。求最长的划分段数。

Sol

显然，我们设 $f_i$ 表示前 $i$ 的长度最长能分多少段，然后显然有：

$$\left{\begin{matrix} &f_i = f_{i-a}+1, \text{if } i\ge a \& f_i=f_{i-b}+1, \text{if }i\ge b \& f_i=f_{i-c}+1,\text{if }i\ge c\end{matrix} \right.$$

于是这道题就做完了。复杂度 $O(n)$。

B. Boredom (CF455A)

Des

给定一个数列 $a_n$，要求进行若干次操作。每次操作选择一个数 $a_k$，删除所有等于 $a_k-1$ 和 $a_k+1$ 的数，并且获得 $a_k$ 的收益。求最大收益。

Sol

关于我刚开始读错题了以为删除 $a_{k-1}$ 和 $a_{k+1}$ 这件事

显然，如果我们选择了 $a_k$，则之后可以无代价地选择所有等于 $a_k$ 的数，因此我们可以视作一次操作选完了所有等于 $a_k$ 的数。注意到 $a_k$ 的值域只有 $1e5$，因此直接计一个桶 $s_i=\sum\limits_{j=1}^n [a_j==i]\times a_j$，然后进行动态规划。

设 $f_i$ 表示选到 $i$ 时的最大收益。显然，我们可以选择 $i$，这样最多就只能再选择 $f_{i-2}$；也可以不选择 $i$，这样就等于 $f_{i-1}$，因此，得到转移方程：

$$f_i=\max{ f_{i-2}+s_i, f_{i-1}}$$

C. 奶酪 (Luogu P3958)

Des

给定一些空间坐标系中半径都为 $r$ 的球，两个球两两可达，当且仅当它们相切或相交。问能否从 $z=0$ 的平面到达 $z=h$ 的平面。

Sol

显然，我们枚举 $\forall i,j\in [1,n]$，并且判断可不可达，可达就连边。顺便判断每个球是否可达 $z=0$ 或 $z=h$。然后从 $z=0$ 开始跑看能否到达 $z=h$ 即可。

D. Pair of Numbers

Des

给定一个长度为 $n$ 的数列，求最长的区间 $[l,r]$ 使得 $\exist i\in [l,r]$，对于 $\forall j\in [l,r]$ 都有 $a_i\mid a_j$。并且求这些最长区间的左端点。

Sol

显然，题意转化一下就变成了求最长区间 $[l,r]$ 使得

$$\gcd\limits_{i=l}^r a_i=\min\limits_{i=l}^r a_i$$

但我们不想求 $\min$，因此可以枚举那个被整除的数 $a_i$，然后向两边拓展。这里可以使用 $ST$ 表来维护区间 $\gcd$，因为 $\gcd$ 显然是数越多值越小，因此可以向两边二分求端点。这样的复杂度是 $ST$ 表一个 $\log$，$\gcd$ 一个 $\log$，查询一个 $\log$，二分一个 $\log$，因此是 $n\log ^2n$。

E. Cows (POJ 2481)

Des

给定一些区间 $l_i, r_i$，求每一个区间被多少个别的区间包含。这里，$j$ 区间包含 $i$ 区间被定义为 $l_j\le l_i$ 且 $r_j\ge r_i$ 且 $len_j>len_i$。

Sol

显然，我们可以按照左端点排序，使得一定满足 $l_j\le l_i$。然后在扫过去之后可以让右端点的地方 $+1$，然后统计一下所有 $>r_i$ 的地方有多少个区间，同时统计 $r_i$ 上有多少个与 $i$ 不同的区间即可。

这里有一些细节。比如说按照左端点排序，左端点相同时按照区间长度从大到小排序。而且统计与 $i$ 相等的区间数量的时候不能提前统计，而是需要早扫描的过程中逐个统计。

F. Dominant Indices (CF1009F)

Des

给定一棵树，对于树上的每个节点 $u$，求：

$$f(u) = \max\limits_d {\sum_{v\in \text{subtree}(u)} [\operatorname{dis}(v, u)=d]}$$

Sol

翻译一下题目，就是对于一棵树上的每一个点 $u$，求 $u$ 的子树内节点数量最多的一层。其中如果有许多层数量相同就选择深度最小的一层。

本来这个题可以 $O(n)$ 使用长链剖分解决，但是我们不会长链剖分，怎么办呢。显然这个题可以使用线段树合并，也就是从叶子结点开始统计，每一次在自己深度的地方 $+1$，然后父亲合并每一个儿子。线段树的话就需要维护坐左边的最大值即可。

H. 萌萌哒 (Luogu P3295)

Des

要求你填一个 $n$ 位的没有前导零的数，并且有 $m$ 个限制，每个限制形如 $l, r, L,R$，即 $l,r$ 内的数一定要和 $L,R$ 内的一样。求有多少种填法。

Sol

首先看看怎么暴力。显然，对于操作 $l,r,L,R$，我们直接使用并查集，令：

$$fa_{find(i+l)} = find(i+L) (i\in [0, r-l])$$

然后令 $ans=\frac{9}{10}$，输出

$$ans\times \prod_{i=1}^n10^{[find(i)=i]}$$

即可。

但是显然暴力不能够通过本题。因此我们考虑怎么优化。

这就不得不谈到一个并查集的 $\text{trick}$。就是建处 $\text{ST}$ 表，然后每一次并查集操作我们拆成两个 $\text{ST}$ 表上的并查集操作。也就是说，对于操作 $l,r,L,R$，我们计 $t=\log (r-l)$，则就可以只连接 $f_{l, t} = f_{L, t}$ 和 $f_{r-2^{t}+1,t} = f_{R-2^t-1, t}$ 即可。

然后，在下传标记的时候，如果一个点 $i$ 有 $find(i,t) \not =i$ 那么就需要下传标记。计 $y = find(i,t)$，则 $f_{i, t-1} = f_{y, t-1}$，$f_{i+2^{t-1}, t-1} = f_{y+2^{t-1}, t-1}$ 即可。

另外，特别值得注意的一点是，我们总是希望从小到大传递标记，也就是说，在令 $f_{i, t} = f{j, t}$ 的时候，我们总希望 $i<j$，这样就可以保证不出现死循环。

I. Tree (CF1111E)

Des

给定一棵树。每次询问有若干个数，前三个为 $k,m,r$ 分别表示节点数量，分组数量和根节点。即选中树上的 $k$ 个节点，在 $r$ 为根的情况下至多分成 $m$ 组有多少种分发，要求每个组内不能出现祖先关系。

Sol

是不是一眼虚树，但其实完全没必要。我们发现一个点能分到哪几个组里只与它有多少个关键节点祖先有关。因此，我们可以假设我们已经知道了它有多少个祖先，并且都做完了这些祖先的动态规划，然后试着转移当前节点。

我们设 $f_{i,j}$ 表示前 $i$ 个点分成 $j$ 组的方案数。那么一个点可以分到原来的组里面，也可以自己一个组。而它不能分到祖先在的组里面。因此，我们设 $s(u)$ 表示 $u$ 有多少个关键节点祖先，那么很容易得到转移方程：

$$f_{i,j} = \max{ j - s(i), 0}\times f_{i-1, j} + f_{i-1, j-1}$$

然后就可以考虑如何先计算祖先。我们发现可以提前把点按照 $dfn$ 排序，这样就一定能够保证祖先在 $u$ 之前就被处理到。但是每一次的根节点不一样，因此我们可以考虑先计算出 $s(u)$，这样 $s(u)$ 小的一定是大的的祖先。那么 $s(u)$ 使用树剖求 $(r, u)$ 路径上的关键节点数量即可。复杂度 $O(n\log^2n +nm)$。