古代 ARC 填坑

· · 个人记录

cnblogs

因为 AGC 已经每场写了题解了，所以这里单独记录集训队作业中 ARC 的部分。一些做过的就不会再写题解了。

ARC095F (\texttt{Easy} \ 3 / 1)

首先给树选定一个根，发现有解的充要条件是所有 sz_u > 1 的 u 构成了一条以根为端点的链。考虑该如何最小化字典序。我们把链最后结点的任意一个儿子也加入这条链，并从这条链的根往下走，对于每个点处理其自身和其 sz = 1 的儿子。具体地，假设遍历到 u 时排列的前 cnt 项已经被填好了，当前结点有 x 个儿子，则在排列的第 cnt + 1 到 cnt + x 个位置依次填上 cnt + 2, cnt + 3, \cdots, cnt + x, cnt + 1。可以证明这是钦定根时最优的构造方法。

根据上述方法，不难发现若根节点有 sz = 1 的儿子，则把这个儿子翻到根节点上面显然更优。不难发现这样操作以后这条链就成为了原树的一条直径。所以我们只有考虑两个直径端点为根的情况即可。

时间复杂度 \mathcal{O}(n)。

ARC096E (\texttt{Easy} \ 3 / 0)

简单数数题。考虑钦定 i 个数不合法。先计算这 i 个数的方案数：设这些数出现在 j 个集合中，则方案为 \begin{Bmatrix} i + 1 \\ j + 1 \end{Bmatrix}（增加一个数 -1 并分成 j + 1 个集合，令和 -1 在一个集合中的数不出现在任何集合中）。这 j 个集合中还可以有剩下 n - i 个数，方案数为 2^{j(n - i)}。剩下的 2^{n - i} 个集合随意取，方案数为 2^{2^{n - i}}。

所以答案为

\sum\limits_{i = 0} ^ n (-1) ^ i \binom{n}{i} 2^{2^{n - i}} \sum\limits_{j = 0} ^ i \begin{Bmatrix} i + 1 \\ j + 1 \end{Bmatrix} 2^{j(n - i)}

时间复杂度 \mathcal{O}(n^2)。

ARC096F (\texttt{Medium} \ 4 / 3)

首先差分一下，变成把每棵子树看作一个物品，问题就变为了多重背包。当然我们是不可能直接去做的，考虑如下引理：

引理：把子树按照 \frac{sz}{sw} 从大到小排序，则至少存在一种最优方案，使得其中选择了 \ge n 次的子树是一个前缀。

使用调整法即可证明。所以我们把每种子树拿出来 \min\{n, d\} 个背包，剩余的贪心即可。

时间复杂度 \mathcal{O}(n^4)。

在贪心数据范围越大看起来越对的这种题目中，应当考虑能否钦定一个我们可以接受的范围内的数据进行其他最优化做法，以保证剩余数据贪心的正确性。这种 idea 见过不止一遍了。

ARC098F (\texttt{Medium} \ 4 / 1)

一个显然的性质是我们肯定会在最后一次到达一个点的时候才捐赠。令 c_u = \max\{a_u - b_u, 0\}，则原来的条件等价于在 u 点的的所有时刻手中的钱数都要 \ge c_u。

把点权转移到边上。即，令 (u, v) 的边权为 \max\{c_u, c_v\}。考虑建出类似 Kruskal 重构树的结构，具体地，按照 c_u 从小到大的顺序枚举 u，然后枚举使得 c_v \le c_u 的每条出边 v 并尽量添加边。

我们在这棵树上 dp，设 f_u 表示以 u 为根的子树的答案。因为走完所有子树最后再回到 u 捐赠肯定不优，所以我们的方案是选择一棵子树 v，先走完其它子树，然后回到 u 捐赠，再往 v 里走。因为路途中钱数单调不增而 c_u 又是子树中的最大值，所以 v 子树以外的限制肯定是最后往 v 走的这一下最紧。设 s_u 表示子树 b 的和，我们有转移

f_u = \min_v \{s_u - s_v + \max\{c_u, f_v\}\}

特别地，当 u 没有儿子时，f_u = \max\{a_u, b_u\}。

时间复杂度 \mathcal{O}(n \log n)。

这题没有想出来的原因主要是受了既定模型的影响，认为本题也存在一种类似的贪心方法，以至于看到路径最大值这种东西都没有往重构树上面想。

ARC099F (\texttt{Easy} \ 1 / 2)

直接哈希即可。

时间复杂度 \mathcal{O}(n \log n) 或 \mathcal{O}(n)。

ARC100F (\texttt{Easy} \ 3 / 2)

简单数数题。首先判掉 a 中本身包含 k 阶排列的情况，并考虑统计没有出现 k 阶排列的序列中 a 的总出现次数。称没有出现 k 阶排列的序列为合法序列。

设 f_{i, j} 表示长度为 i 的合法序列，最后恰有 j 个元素互不相同的方案数；g_{i, j} 表示这些合法序列中长度为 m 的没有重复元素的子串的总个数。f 和 g 显然都可以在 \mathcal{O}(nk) 内求出。

分类讨论。若 a 中没有重复元素，则总出现次数为 \sum_j g_{n, j} \cdot \frac{(k - m)!}{m!}；否则其左右两侧独立，设两侧恰有 l, r 个元素互不相同，则枚举 a 出现的位置，总出现次数可以表示为若干个 f_{*, l} \cdot f_{*, r} 之和。

时间复杂度 \mathcal{O}(nk)。

ARC101E (\texttt{Easy} \ 1 / 1)

简单数数题。直接容斥 + 树上背包即可。

时间复杂度 \mathcal{O}(n^2)。

ARC102F (\texttt{Medium} \ 4 / 1)

很有意思的结论题，哪天把题解补上。

ARC103D (\texttt{Easy} \ 2 / 1)

想复杂了！！！！

首先有解的充要条件是所有 |x_i + y_i| 的奇偶性相同，画个图就可以发现取 len = \{2^{30} - 1, 2^{29} - 1, \cdots, 2, 1(, 1)\} 就可以解决问题。具体地，每次尽量让曼哈顿距离最小即可。

时间复杂度 \mathcal{O}(n \log V)，其中 V = 10^9。

ARC103F (\texttt{Easy} \ 2 / 1)

若以重心为根，则对于所有的 u 都有 d_u > d_{fa_u}。又因为 d 互不相同，所以可以按照 d 从大到小还原。

时间复杂度 \mathcal{O}(n \log n) 或 \mathcal{O}(n)。