「CF581F」 Zublicanes and Mumocrates - 树形dp

一棵树上有 $n$ 个节点,把每个节点染成黑色或白色,要求叶子节点一半是黑色,一半是白色(保证叶子节点的个数是偶数)。

求在满足要求的情况下,最小的两端颜色不同的边的数量。

「CF542D」Superhero's Job - dp + 数论

我们定义
$$
J(x) = \sum_{d | x} [\gcd(x,\frac{x}{d}) = 1] d
$$

请你求出 $J(x) = A$ 有多少个 $x$ 满足条件。

「CF543C」Remembering Strings-状态压缩dp

给定 $n$ 个长度均为 $m$ 的字符串,再给出一个 $n$ 行 $m$ 列的矩阵 $\{a_{nm}\}$。
矩阵元素 $a_{ij}$ 代表把第 $i$ 个字符串第 j 个字符改成其它任意字符所需要的代价。

现在要求对于任意一个字符串,总存在某一位置 $j$ 使得该位置上的字符在任意其他字符串该位置的字符不同。

即为对于第 x 个字符串 ,有 $\exists j \in [1,m] , \forall i \in [1,n],s_{xj} \neq s_{ij}$ 。

求把所有字符串修改成满足上述要求的字符串的最小代价是多少?

数据范围: $1 \le n,m \le 20,1\le a_{ij} \le 10^6$ 。

「CF321E」Ciel and Gondolas-wqs二分+决策单调性

Ciel 狐狸在游乐园里排队等待上摩天轮。现在有 $n$ 个人按编号顺次在队列里,有 $m$ 条船,第 $i$ 条船到时,前 $q_{i}$ 个人可以上船。保证 $\sum q_i = n$。 人总是不愿意和陌生人上同一条船的,当第 $i$ 个人与第 $j$ 个人处于同一条船上时,会产生 $u_{i,j}$ 的沮丧值。请你求出最小的沮丧值和。一条船上的人两两都会产生沮丧值,不会计算这个沮丧值两次。

「CF476E」Dreamoon and Strings-动态规划

Dreamoon 有一个字符串 $s$ 和一个模式串 $p$,他会先从 $s$ 中删除恰好 $x$ 个字符来产生一个新的字符串 $s’$ 。然后他会计算 $occ(s’,p)$,即从 $s’$ 中能找到的等于 pp 的不相交的子串数量的最大值。他想让 $occ(s’,p)$ 的值尽可能大。

更形式地说,让我们用 $ans(x)$ 表示所有可以从 $s$ 中删去恰好 $x$ 个字符得到的 $s’$ 中 $occ(s’,p)$ 的最大值。Dreamoon 想要知道对于所有的 $x$ $(0 \leq x \leq |s|)$, $ans(x)$ 的值。

「CF813D」Two Melodies-简单dp

给定一个长度为 $n$ 的数组,我们要从中找出两个不相交(不含邮相同元素的)的子序列,要求每个子序列的任意两个相邻元素的差的绝对值为 $1$ 或 在模 $7$ 意义下相同。请你求出这两个子序列长度和的最大值。

「CF86C」Genetic engineering-AC自动机+dp

我们定义一个 DNA 序列为仅有 ATCG 四个字母的字符串。

给出 $m(1 \le m \le 10)$ 个 DNA 序列模式串 $s_i$,每个长度均不超过 $10$ ,我们定义一个 DNA 序列 $w$ 是好的,当且仅当对于 $w$ 的每一个位置 $i$ ,都存在至少一个模式串 $s_j$ , 使得 $w[l…r] = s_j$( $w[l…r]$ 表示一个原字符串的一个子串) , 其中 $1 \le l \le i \le r \le |w|$( $|w|$ 为 DNA序列 $w$ 的长度) 。

请你计算出所有长度为 $n(1 \le n \le 1000)$ 的好的 DNA 序列的个数。

「CF486E」LIS of Sequence-简单数据结构

给你一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ,你需要把这 $n$ 个元素分成三类:$1,2,3$,每类的条件如下:

  1. 所有的最长上升子序列都不包含这个元素

  2. 有但非所有的最长上升子序列包含这个元素

  3. 所有的最长上升子序列都包含这个元素

「CF311B」Cats Transport-斜率优化dp

Zxr960115 是一个大农场主。他养了 $m$ 只可爱的猫子,雇佣了 $p$ 个铲屎官。这里有一条又直又长的道路穿过了农场,有 $n$ 个山丘坐落在道路周围,编号自左往右从1到n。山丘 $i$ 与山丘 $i-1$ 的距离是 $d_i$ 米。铲屎官们住在 $1$ 号山丘。

一天,猫子们外出玩耍。猫子 $i$ 去山丘 $h_i$ 游玩,在 $t_i$ 时间结束他的游玩,然后在山丘 $h_i$ 傻等铲屎官。铲屎官们必须把所有的猫子带上。每个铲屎官都会从 $1$ 走到 $n$ 号山丘,可以不花费时间的把所有路途上游玩结束的猫子带上。每个铲屎官的速度为一米每单位时间,并且足够强壮来带上任意数量的猫子。

你的任务是安排每个铲屎官出发的时间,最小化猫子们等待的时间之和。

「CF115E」Linear Kingdom Races-dp+线段树优化

你是一个赛车比赛的组织者,想在线性王国中安排一些比赛。

线性王国有 $n$ 条连续的从左到右的道路。道路从左到右依次编号为从 $1$ 到 $n$ ,因此道路按照升序排列。在这些道路上可能会有几场比赛,每一场比赛都将使用这些道路的某个连续的子序列。而且,如果某场比赛举行了,你将获得一定数额的金钱。没有比赛在时间上重叠,所以每一段道路可以在多个比赛中使用。

不幸的是,所有道路的状况都不佳,需要修理。每条路都有与之相关的维修费用,你需要支付这笔费用来修理道路。只有在某场比赛中需要使用的所有道路都进行了修复,才能进行比赛。你的任务是修复道路并使你的利润最大化。你的利润被定义为你从比赛中获得的总金额减去你花在修理道路上的钱。请注意,您可以决定不修任何道路,并获得利润 $0$ 。

输出你能获得的最大利润。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×