06-22 01:18 阅读 63

AtCoder Regular Contest 108 选做

D - AB

给定一个正整数 $N$ 和 $4$ 个字符变量 $c_{\rm AA}, c_{\rm AB}, c_{\rm BA}, c_{\rm BB}$，变量的取值为 A 或 B。

初始时，有一个长度为 $2$ 的字符串 AB，每次操作你可以选择一个长度为 $2$ 的子串 $s_1s_2$，在它们之间插入一个新的字符 $c_{s_1s_2}$。

求通过这种方法能生成多少种长度为 $N$ 的不同的字符串。

答案对 $10^9 + 7$ 取模。

$2 \le N \le 1000$。

2s, 1GB

显然直接分类讨论。

首先不妨设 $c_{\rm AB} = $ A（另一种情况几乎完全相同）。

那么，仅使用 $c_{\rm AB}$，我们就可以把字符串变为 AA...AAB，于是我们对 $c_{\rm AA}$ 进行讨论：

如果 $c_{\rm AA} = $ A，那么答案为 $1$，只有 AA...AAB 一种。
如果 $c_{\rm AA} = $ B，那么此时，字符串可以变为 AABAAABAABAA...AB 这样，即「若干个 A，一个 B，若干个 A，一个 B …… 最终是一个 AB」，于是再对 $c_{\rm BA}$ 进行讨论：
- 如果 $c_{\rm BA} = $ B，那么任意以 A 开头，AB 结尾的字符串就都能生成了，于是答案为 $2^{N-3}$。
- 如果 $c_{\rm BA} = $ A，那么我们还是只能生成上文所描述的那类字符串，而这种字符串的数量不难发现为 $Fib_{N-2}$。

于是答案就很好求了，时间复杂度 $O(N)$。

E - Random IS

给定一个长度为 $N$ 的数列 $a$，数列 $a$ 中的值互不相同，重复执行以下过程：

对于某个未被标记的数，如果它被标记了以后，所有被标记的数仍然呈现一个递增数列，那么就称它是好的。记有 $k$ 个好数。

如果 $k=0$，结束操作，否则从好数中等概率随机选择一个打标记。

求最终被标记的数的期望，对 $10^9 + 7$ 取模的结果。

$1 \le a_i \le N \le 2000$，$a_i$ 互不相同。

3s, 1GB

考虑使用区间 DP，设 $f(l, r)$ 表示 $a_l, a_r$ 都被打标记之后，$[l+1,r-1]$ 这一段被标记的数的个数的期望。

边界条件是 $f(l, r) = 0 \ (r - l \le 1)$。

考虑转移，枚举这个区间中第一个被打标记的点，即：

\[f(l, r) = \frac{\sum_{i=1}^{k} (f(l, pos_i) + f(pos_i, r))}{k}+1 \]

增设 $a_0 = 0, a_{N+1} = N + 1$，那么答案即 $f(0, N + 1)$。

但这样暴力是 $O(N^3)$ 的，会超时。显然，枚举 $k$ 的那层循环可以视作一个单点加、区间求和，于是使用树状数组优化即可。

时间复杂度 $O(N^2 \log N)$。

F - Paint Tree

给定一棵包含 $N$ 个结点的树，第 $i$ 条边连接 $a_i, b_i$，长度为 $1$。

现在，需要给每个结点涂上黑色或者白色，记 $X$ 表示两个白色点之间的最大距离，$Y$ 表示两个黑色点之间的最大距离，那么这种涂色方案的分值就是 $\max(X, Y)$。如果一种方案中某种颜色不足两个点，那么最大距离视作为 $0$。

对所有的 $2^{N}$ 种染色方案，求出它们的分值之和，对 $10^9 + 7$ 取模。

$2 \le N \le 2\times 10^5$。

2s, 1GB

首先找到一条树的直径 $U, V$。

如果 $U, V$ 同色，那么分值必然是直径的长度。

接下来考虑 $U, V$ 异色的情况，比如 $U$ 是白色，$V$ 是黑色。

根据直径的性质，我们可以知道，对于一对合法的 $X, Y$，必然存在某个白色点到 $U$ 的距离是 $X$，某个黑色点到 $V$ 的距离是 $Y$。

那么一遍 DFS 对每个结点求出一个 pair $(x, y)$，表示它离 $U, V$ 的距离。

问题转化为对每个点从 $(x, y)$ 中选一个出来，分值则为最大的元素。

这是很简单的，只要对于某个 $d$，都能求出 $ans \ge d$ 的方案数，累加即可。

但 $ans \ge d$ 的方案数不好求，可以考虑求 $ans \le d$ 的方案数，具体方法为：

如果存在某个 $i$，满足 $\min(x, y) > d$，那么方案数为 $0$。
否则，记有 $c$ 个点的 $x, y$ 均 $\le d$，剩下的点的 $x, y$ 只有一者 $\le d$，则此时的方案数即为 $2^c$。

时间复杂度 $O(N)$。

原文：https://www.cnblogs.com/syksykCCC/p/ARC108.html