CSP模拟赛#34

Lgx_ / 2024-10-09 / 原文

A

定义两个元素互不相同的序列相似，当且仅当离散化后的排列相同。给定 $0\sim n - 1$ 的排列 $a$，其中有些位置空缺。你需要填写排列 $a$，最大化 $k$ 的个数满足对于任意长度为 $k$ 的子序列，满足互不相似。

$n\le 20$

给定 $a,k$，先考虑如何判定。猜结论：对于任意 $i,j$ 满足 $|a_i - a_j| + |i - j|\ge k + 2$。钦定 $i < j, a_i < a_j$，我们可以删掉 $a_{i + 1\cdots j - 1}$，以及值域在 $a_i + 1 \sim a_j - 1$ 的所有数，最后删掉 $a_i$ 或 $a_j$ 都是等价的。即只要删的数的个数 $\le k$ 则不合法。

然后难以状压。考虑直接爆搜剪枝，发现可以通过。

启示：猜结论要大胆；爆搜剪枝。

B

有 $n$ 种物品，每个物品有体积 $w_i$ 和价值 $v_i$。有一个空的背包，你每次可以选择一个物品放进背包，求最终放满背包时，背包内所有物品价值总和最大值，以及达成最大值的方案数（选物品先后顺序之分），答案对 $1092515507$ 取模。共 $m$ 次询问，每次给出固定的背包容量 $q_i$。

$n, m, q, w_i\le 100, \ q_i, v_i \le 10^9$

考虑矩阵快速幂，存一个二元组 $(a, b)$ 表示最大值以及达成最大值的方案数。矩阵快速幂完美契合了选物品有顺序的方案数限制，以及放满背包的限制。

C

有 $n$ 个鼓和 $m$ 个奖励，第 $i$ 个奖励为：在第 $k_i$ 次选择第 $x_i$ 个鼓打时，有 $w_i$ 的收益。设当前已经打过的鼓的编号为 $l\sim r$，那么下一次可以选择第 $l - 1$ 个或第 $r + 1$ 个鼓打。有 $q$ 次询问，每次给出 $s_i$ 表示第一次打的鼓的编号，求最大总收益。

$1\le n\le 10^9, \ 1\le m, q\le 5\times 10^5$

考虑每个奖励 $(k, x, w)$，我们划分为两个区间 $[x - k + 1, x]$ 和 $[x, x + k - 1]$。对于 $[x - k + 1, x]$，当打完了 $[x - k + 1, x - 1]$ 后打 $x$ 时会有收益，$[x, x + k - 1]$ 同理。有收益的区间一定是呈一条包含关系的链，考虑 dp，按左端点递增、右端点递减对区间排序：设 $f[i]$ 表示链接到了第 $i$ 个区间的答案。

每次可以用树状数组优化转移。最终要求支持对一段区间内的 $s$ 进行答案 chkmax，可以动态开点标记永久化线段树 / 扫描线 + 可删堆解决。

D

一棵 $n$ 个点的树，初始时你需要安排一些人在任意节点上，一个人通过第 $i$ 条边有对应时间 $t_i$。有 $m$ 个任务，第 $i$ 个任务为 $(a_i, b_i, c_i)$，表示在 $a_i$ 时刻需要聚集至少 $b_i$ 个人于 $c_i$ 节点。求完成所有任务的最小总人数。

$n, m\le 10^5$

一个任务向完成该任务的人能够完成的下一个任务连边，形成一张 DAG，答案即为 DAG 最小带权链覆盖。运用 Dilworth 定理，转化为求最大带权反链。对于一个点 $u$ 以及子树内的一个任务，我们用一个区间 $[l, r]$ 表示子树外需要在 $\le l$ 时刻到达 $u$ 才能完成该任务，并且该任务完成后必须在 $\ge r$ 才能离开子树。不难看出，合法条件即为所有区间都有交。可以 dp，设 $f[u, i]$ 表示考虑了 $u$ 子树，选择了子树内若干个任务，其中时刻 $i$ 是这些任务的区间交集中的一个时刻。转移先把所有儿子 dp 值对位相加，然后对于每个 $i$，将 $f[u, i - w_u ... i + w_u]$ 对 $f[u, i]$ 进行 chkmax，其中 $w_u$ 为点 $u$ 到父亲连边的长度。