题单题解 - Der Richter 的动态规划

· · 算法·理论

Der Richter 的动态规划。

CF2190B2 Sub-RBS (Hard Version)

:::info[题意]{open} 给定 n、仅含 ( 和 ) 的括号串 s,定义一个非空子序列 t 的得分为 t 本身为正则括号序列且存在更优的正则括号子序列时,这些子序列中的最大长度(其中 ( 的字典序小于 ),若为真前缀更短者更劣),否则得分为 0,求所有非空子序列得分之和。

::: :::success[思路] 首先有两个重要结论: > **结论 1** $\space$ 一个字符串的得分只有可能为 $0$ 或 $len - 2$,其中 $len$ 为长度。 > > **结论 2** $\space$ 一个字符串的得分为 $len - 2$,当且仅当这个字符串包含 $)(($ **子序列**。 我们先证结论 1。显然,对于一个合法的括号序列,其合法子序列的长度一定为偶数,所以得分最多为 $len - 2$。 接下来分两种情况。若原串不为合法括号序列,则得分为 $0$。 若原串为合法括号序列,此时可以证明,一定可以构造出长度为 $len - 2$ 的更优子序列。 设原串为 $s$,构造出来的子序列为 $t$,显然 $|s| > |t|$,要使 $t$ 比 $s$ 更优,只能是存在一个 $1 \le i \le |t|$,使得:$s_i = )$ 且 $t_i = ($。 又因为 $t$ 是 $s$ 的子序列,其在选取的时候跳过了 $s$ 的第 $i$ 个字符,即 $)$,那么为了使 $t$ 为合法括号序列,在 $i$ 后面的 $j$,$t$ 一定会又跳过一个 $($,才能使得 $t$ 为合法括号序列。显然,删去一个 $)($ 子序列不会影响合法性,所以 $t$ 一定合法且比 $s$ 更优。 然后来看结论 2。 先证必要性:只有包含 $)(($ 子序列才有可能有得分。 在结论 1 的证明过程中,我们提到,$s$ 至少会包含一个 $)($ 子序列。而删去 $($ 后,在 $i$ 后面至少还要有一个 $($,这样才能够使 $s_i$ 能够取到 $($。所以,$s$ 必定包含 $)(($ 子序列。 再证充分性:包含 $)(($ 的子序列一定都有得分。 在结论 1 的证明过程中也提到,删去一个 $)($ 子序列,并不会影响合法性。这是显然的,请读者自己思考。 我们考虑找到一个 $)($ **子串**,并删去最后一个 $($,显然,这样一定能够构造出一个合法的 $t$。 证明就到这里。所以这个问题被转化为;统计所有是合法括号序列且包含 $)(($ 子序列的子序列,并求它们的 $len - 2$ 之和。 考虑动态规划。定义状态 $dp_{i, pre, k = 0/1/2/3}$ 表示,当前考虑前 $i$ 个位置,在当前选择的子序列中,将 $($ 看作 $1$,$)$ 看作 $-1$,累加和为 $pre$,子序列 $)(($ 匹配到第 $k = 0/1/2/3$ 位时的**方案数**,另外再记录一个 $sum_{i, pre, 0/1/2/3}$,表示同样状态下的**长度和**。 考虑转移。首先显然这一位可以不选: $$ dp_{i, pre, k} \leftarrow dp_{i - 1, pre, k} $$ $$ sum_{i, pre, k} \leftarrow sum_{i - 1, pre, k} $$ 考虑当前为 $)$ 的情况。显然可以使 $k$ 从 $0$ 变为 $1$: $$ dp_{i, pre, 1} \leftarrow dp_{i - 1, pre + 1, 0} $$ $$ sum_{i, pre, 1} \leftarrow sum_{i - 1, pre + 1, 0} + dp_{i - 1, pre + 1, 0} $$ 考虑当前为 $($ 的情况。显然可以使 $k$ 从 $1$ 变为 $2$ 或从 $2$ 变为 $3 dp_{i, pre, 2} \leftarrow dp_{i - 1, pre - 1, 1} sum_{i, pre, 2} \leftarrow sum_{i - 1, pre - 1, 1} + dp_{i - 1, pre - 1, 1} dp_{i, pre, 3} \leftarrow dp_{i - 1, pre - 1, 2} sum_{i, pre, 3} \leftarrow sum_{i - 1, pre - 1, 2} + dp_{i - 1, pre - 1, 2}

注意,如果 pre 满足对应要求(> 0 或 < n),则只能够进行 k 变化的转移,不能进行不选择的转移,否则会重复计数。最后答案即为 sum_{n, 0, 3} - 2 \times dp_{n, 0, 3}。这里可以滚动数组优化。

:::

CF2194F1 Again Trees... (Easy Version)

:::info[题意]{open} 给定一棵树,每个结点有一个权值 a_i,再给定一个不可重集合 b,其大小为 k,用一个序列 \{ b_k \} 表示。求原图中满足以下条件的边集数量:

::: :::success[思路] Easy version 的入手点在于,$k$ 的范围极小,这点在上面的题意中也有所凸显。 首先容易想到一个暴力树形 DP。状态:$dp_{u, x}$ 表示,考虑 $u$ 的子树中,包含 $u$ 的连通块异或和为 $x$ 的方案数。转移根据删/不删 $(u, v)$ 边分类讨论即可得出。 但是这样,状态空间是会爆炸的。原因很显然,$x$ 并不一定 $\in b$。因为 $u$ 可能并不是包含 $u$ 的那个连通块中深度最浅的点。 但是话又说回来了,我们发现,$u$ 的子树中,除了包含 $u$ 的这个连通块可能并不完全属于 $u$ 的子树,其他的连通块都包含于 $u$ 的子树。也即我们设: $$ S = \left\{ \bigoplus \limits _ {i \in T} b_i \mid T \subseteq \{ 1, 2, \dots, k\} \right\} $$ 定义状态:$dp_{u, s}$ 表示,考虑 $u$ 的子树,除了包含 $s$ 的那个连通块,其他的连通块的异或和为 $s$ 的方案数。容易发现,$s \in S$ 是一定成立的。此时状态空间 $O(16n)$,不会爆炸。 对于 $u$ 的一个儿子 $v$,我们按边 $(u, v)$ 是否删去的两种情况来作讨论。下面,我们记 $$ sum_u = \bigoplus _ {v \text { in subtree of } u} a_v $$ 即,$sum_u$ 表示 $u$ 子树的异或和。 1. 不删去边 $(u, v)$。此时 $u$ 和 $v$ 同属一个连通块,设 $v$ 子树中包含 $v$ 的连通块大小为 $sum_v \oplus t$,显然 $t \in S$,那么转移如下: $$ dp'_s \leftarrow \sum \limits _ {\substack{v \text { is son of } u \\ t \in S}} dp_{u, s \oplus t} \times dp_{v, t} $$ 其中 $dp'$ 为处理完儿子 $v$ 后 $dp_u$ 的真实值。 2. 删去边 $(u, v)$.此时 $u$ 和 $v$ 分属两个连通块,设 $v$ 子树中包含 $v$ 的连通块大小为 $sum_v \oplus t$,要求 $sum_v \oplus t \in b$。此时 $t$ 子树内所有的连通块对于 $u$ 来说,全都变为了不包含 $u$ 的其他连通块,即应当全部计入新的状态。根据上面的要求,$sum_v \oplus s \in S$ 一定成立。 所以转移如下: $$ dp'_{s} \leftarrow \sum \limits _ {\substack{v \text { is son of } u \\ t \in S \\ sum_v \oplus t \in b \\ sum_v \oplus s \in S}} dp_{u, s \oplus sum_v} \times dp_{v, t} $$ 按照上述方法转移即可。注意,这里 $s$ 一维需要离散化,且需要对于每个 $S_i \oplus S_j$ 预处理出其排名,以便直接处理转移。 ::: ## [P15804 [GESP202603 八级] 消息查找](https://www.luogu.com.cn/problem/P15804) :::info[题意]{open} 有 $n$ 条消息,每一条消息可以引用前面的消息,也可以不引用。对于消息 $i$ ($1 \le i \le n$),以 $r_i$ 标记消息 $i$ 是否有引用,以及所引用的消息编号。若 $r_i > 0$,则消息 $i$ 为引用了消息 $r_i$;若 $r_i = 0$,则消息 $i$ 没有引用消息。 要求实现一个消息定位工具。如果当前位于消息 $i$ ($1 < i \le n$),那么接下来可以选择以下两种操作之一: - 定位到消息 $i - 1$; - 如果消息 $i$ 引用了消息 $r_i$,定位到消息 $r_i$。 以上操作可以执行任意次(包括零次)。给出 $q$ 次查询,每次查询两个正整数 $x_i > y_i$,表示询问从 $x_i$ 定位到 $y_i$ 最少需要多少次操作。 ::: :::success[思路] 下文中 $m$ 表示有引用的消息总数。 显然,每个查询的答案,就相当于选择若干不相交的区间 $(r_j, j]$ 使得其长度之和最大。我们设其为 $val_i$,则答案为: $$ ans_i = x_i - y_i - val_i $$ 然后这个看起来就像一个 DP 不是么。我们考虑使用一次引用 $j$。那么,$r_j$ 之前的情况就是一个子问题,所以可以考虑 DP。 我们设计状态:$dp_k$ 表示,考虑前 $k$ 条引用消息时的 $\max val$。然后考虑转移: 1. 不使用引用。则显然有 $$ dp_k \leftarrow dp_{k - 1} $$ 2. 使用引用。考虑第 $k$ 条引用消息,其能够使用的最大前提是 $r_k \ge y$,于是我们设 $pre_k$ 表示右端点 $\le r_k$ 的引用消息数量,然后 $$ dp_k \leftarrow dp_{pre_k} + (k - r_k + 1) $$ 显然 $pre_k$ 可以在 $O(m \log m)$ 的时间复杂度内预处理。 因为每次的 $y$ 不一样,所以我们每次都需要重新 DP,但由于 $m \le 10 ^ 3$,所以总时间复杂度: $$ O(m \log m + qm) $$ 勉强通过。 ::: ## [P15862 [LBA-OI R3 B] 回去!](https://www.luogu.com.cn/problem/P15862) :::info[题意]{open} 给定一张图,每个点的出度均为 $1$,每个点有一个字符。现在要在图上游走。首先,在图上等概率均匀随机地选择一个起点,然后用一个栈记录起点到当前点上路径的点,初始栈为空。每一步都有两种选择: - 前进:沿着当前点的唯一出边行走,并将到达的点加入栈,概率为 $p$; - 后退:弹出栈顶,回到之后的栈顶,若此时栈为空则回到起点,概率为 $1 - p$。 每走完一步,当前点的字符会被加入一个字符串中。现在要走 $2k$ 步,求结果字符串前 $k$ 位与后 $k$ 位相等的概率 ::: :::success[思路] 首先,我们可以把游走过程分为两段:第 $1$ 步到第 $k$ 步,以及第 $k + 1$ 步到第 $2k$ 步。 我们枚举起点,然后立即就可以得出沿着出边一直走的长度为 $2k + 1$ 的路径。我们从这 $2k$ 个点中,选取一个点,作为第二段的起点,显然起点的出点和该起点的出点的字符应当相等。 两端起点都确定后,我们考虑动态规划。设状态 $dp_{i, x, y}$ 表示,当前两段各走了 $i$ 步,第一段走到 $x$ 处,第二段走到 $y$ 处的概率,其中 $1 \le x, y \le 2k + 1$。 接下来考虑转移。 我尝试过把所有情况都在这里列出来,但是失败了。因为实在是太多了。 我们分为 $4$ 个方向处理。如果遇到 $x$ 或 $y$ 等于 $1$ 的情况且需要前进的时候,把对应概率改为 $1$ 即可。因为在起点只能向右移动。 我们设两段字符串的起点为 $2$ 和 $v$,则初始状态是 $dp_{1, 2, v}$,因为此时已经匹配了一个。 在 DP 时,我们先不处理第 $k$ 步,即两端交接的那一步。这个情况需要单独处理。我们枚举第二段终点,显然第一段终点和第二段起点一定要相邻,且两段各走了 $k$ 步。这样最终状态就确定了。 注意最后输出的是 $nP$,直接对每个起点的概率求和输出即可。 ::: ## [AT_dp_w Intervals](https://www.luogu.com.cn/problem/AT_dp_w) :::info[题意]{open} 考虑一个长度为 $N$、仅由 `0` 和 `1` 组成的字符串。该字符串的分数按照如下方式计算: - 对于每个 $i$($1 \leq i \leq M$),如果从第 $l_i$ 个字符到第 $r_i$ 个字符之间至少包含一个 `1`,则将 $a_i$ 加到分数上。 请你求出字符串分数的最大值。 $1 \le N \le 2 \times 10 ^ 5, |a_i| \le 10 ^ 9$。 ::: :::success[思路] 我们先来考虑如何设计状态。我们从左往右构造字符串,考虑一个题目给定区间 $[l, i]$: - 若字符串第 $i$ 位为 $1$,显然该区间一定得分; - 若字符串第 $i$ 位为 $0$,那么字符串 $[l, i)$ 区间内至少出现一个 $1$ 才能得分。 所以,一个区间 $[l, i]$ 是否得分,取决于: 1. 第 $i$ 位是否为 $1$; 2. 若第 $i$ 位为 $0$,之前的 $1$ 的分布方式。 但是显然我们无法随时记录前面 $1$ 的分布情况。注意到,我们设定当前位为 $0$,那么 $[l, i]$: - 当最后一个 $1$ 的位置 $\ge l$ 时,得分; - 当最后一个 $1$ 的位置 $\lt l$ 时,不得分。 所以,一个状态中只需要记录**最后的 $1$ 的位置**即可。 于是我们定义状态:$dp_i$ 表示,当前最后一个 $1$ 的位置是 $i$ 时的最大价值。并记 $dp_0 = 0$,表示没有 $1$ 时没有价值。 考虑转移。我们考虑区间 $[l, i]$,分情况讨论: 1. 若第 $i$ 位为 $1$:此时 $[l, i]$ 一定有价值,可以从前面的任意状态转移而来: $$ dp_i \leftarrow \max \limits _ {0 \le j \lt i} dp_j + \sum \limits _ {r_k = i} a_k $$ 2. 若第 $i$ 位为 $0$:此时 $[l, i]$ 有价值当且仅当 $[l, i)$ 内存在至少一个 $1$,不能更新 $dp_i$,而是应当以当前区间的价值更新前面的状态: $$ dp_j \leftarrow dp_j + a \space (\forall j \in [l, i)) $$ 其中 $a$ 为区间 $[l, i]$ 的价值。 显然这个 DP 过程可以使用线段树维护。 ::: ## [P11233 [CSP-S 2024] 染色](https://www.luogu.com.cn/problem/P11233) :::info[题意]{open} 给定一个长度为 $n$ 的正整数数组 $A$,其中所有数从左至右排成一排。 你需要将 $A$ 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分: 设 $C$ 为长度为 $n$ 的整数数组,对于 $A$ 中的每个数 $A_i$($1 \leq i \leq n$): - 如果 $A_i$ 左侧没有与其同色的数,则令 $C_i = 0$。 - 否则,记其左侧**与其最靠近的同色数**为 $A_j$,若 $A_i = A_j$,则令 $C_i = A_i$,否则令 $C_i = 0$。 你的最终得分为 $C$ 中所有整数的和,即 $\sum \limits_{i=1}^n C_i$。你需要最大化最终得分,请求出最终得分的最大值。 ::: :::success[思路] 若某个位置 $i$ 要产生贡献,那么必然存在一个位置 $j < i$,满足: - $a_j = a_i$; - $i, j$ 染成相同颜色; - 区间 $(j, i)$ 中的所有位置都染成另一种颜色。 最后一点尤为重要:由于只有红、蓝两种颜色,若 $i$ 与 $j$ 同色,且 $j$ 是 $i$ 左侧最近的同色位置,那么 $j + 1, \dots, i - 1$ 必须全部与它们异色。 首先很容易想到一个暴力 DP:设 $dp_i$ 表示前 $i$ 个数的最大得分。但转移时,很难判断第 $i$ 个位置能否产生贡献,因为我们并不能从前面的状态 $dp_j$ 中获取能够影响 $a_i$ 贡献的决定性因素,换言之没有记录最后一个与 $a_i$ 同色的位置。 因此,我们需要在 DP 状态中增加一个条件,让中间区间的颜色能够确定。设 $dp_j$ 表示考虑前 $j + 1$ 个数,且要求第 $j$ 个位置与第 $j + 1$ 个位置颜色不同的情况下的最大得分。 为了方便转移,额外设一个虚拟位置 $a_0 = 0$,并令 $dp_0 = 0$。因为题目保证所有 $a_i \ge 1$,所以该虚拟位置不会产生贡献。 考虑转移。设当前计算 $dp_{i - 1}$,注意不是 $dp_{i}$。这个状态就限定了 $i$ 和 $i - 1$ 的颜色不同。设 $j$ 是位置 $i$ 左侧最近的、与位置 $i$ 颜色相同的位置。那么: - 必有 $j \le i - 2$,因为前面已经限定位置 $i - 1$ 与 $i$ 异色; - 区间 $[j+1,i-1]$ 全部与位置 $i$ 异色,因此这一整段颜色相同; - 位置 $j$ 与 $j + 1$ 异色,恰好符合状态 $dp_j$ 的限定条件。 于是,$dp_{i - 1}$ 可以从 $dp_j$ 转移而来。你可能会问:这个状态是如何想到的呢?其实,就是把**最近同色位置**转化成一个可以枚举的边界。 我们先考虑朴素转移。即枚举合法 $j$ 然后转移。我们考虑一段前缀中,如果全部染成同色,能够产生的贡献 $S_r$。则 $$ S_r = \sum \limits _ {i = 2} ^ r [a_i = a_{i - 1}] a_i $$ 前面已经提到,从 $dp_j$ 转移到 $dp_{i - 1}$(其中 $0 \le j \le i - 2$),那么位置 $j + 1$ 到 $i - 1$ 都被染成了同一种颜色。容易发现,其中相邻且数值相同的位置产生的贡献为 $$ S_{i - 1} - S_{j + 1} $$ 至于位置 $i$,如果 $a_j = a_i$,它就可以与位置 $j$ 同色并获得 $a_i$ 的贡献;否则没有额外贡献。 因此 $$ dp_{i - 1}= \max _ {0 \le j \le i - 2} \left( dp_j + S_{i - 1} - S_{j + 1} +[a_j = a_i] a_i \right) $$ 接下来考虑优化。我们发现,朴素转移方法中,最耗时的是枚举所有 $j$。我们首先把当前的区间贡献提前维护起来。 我们使用一个线性表 $v$。在处理位置 $i$ 之前,定义 $$ v_j = dp_j + \sum_{k = j + 2} ^ {i - 1} [a_k = a_{k - 1}] a_k $$ 也就是说,$v_j$ 表示状态 $dp_j$ 加上从它出发、把后续位置染成同色时,已经能够获得的相邻相等贡献。 于是转移简化成 $$ dp_{i - 1} \leftarrow \max_{0 \le j \le i - 2} \left(v_j + [a_j = a_i] a_i\right). $$ 现在只剩下一个问题:怎样快速求这个最大值?我们记 $p = pos_{a_i}$,其中 $p$ 是 $a_i$ 在 $[1, i - 2]$ 中最后一次出现的位置;若没有出现,则令 $p = -1$。 分类讨论。 当 $j > p$ 时,因为 $p$ 是最近一次出现 $a_i$ 的位置,所以 $a_j \ne a_i$,这些状态转移到当前位置时都没有额外贡献,因此只需要查询 $$ \max_{p + 1 \le j \le i - 2} v_j $$ 即可。 当 $j \le p$ 时,状态 $p$ 的候选值为 $v_p + a_i$。所以整个转移变成 $$ dp_{i - 1} \leftarrow \max \left( \max_{p + 1 \le j \le i - 2} v_j, v_p + a_i \right) $$ 特别地,当 $p = -1$ 时,第二项不存在,只需查询区间 $[0, i - 2]$ 的 $v$ 值即可。 前面解释了如何转移。但是还需要维护贡献:当 $a_i = a_{i - 1}$ 时,相邻的两个数如果染成相同颜色,就可以获得 $a_i$ 的贡献。对于所有之前已经存在的候选状态 $v_j$,只要 $j \le i - 2$,它们都可以让位置 $i - 1$ 和 $i$ 染成同色,从而多获得 $a_i$。 因此,当 $a_i = a_{i - 1}$ 时,需要执行 $$ v_j \leftarrow v_j + a_i \space (0 \le j \le i - 2) $$ 所以,我们可以使用线段树来维护线性表 $v$。注意区间右端点是 $i - 2$,**不包含**刚刚建立的新状态 $dp_{i-1}$。因为这个新状态要求位置 $i - 1$ 与 $i$ 异色,两者不能因为数值相同而直接取得相邻贡献。 注意,应当在计算完 $dp_i$ 后更新 $pos_{a_{i - 1}}$,也是因为上面的原因。 ::: ## [P9100 [PA 2020] Miny](https://www.luogu.com.cn/problem/P9100) :::info[题意]{open} 给定 $n$ 个地雷,编号为 $1, 2, \dots, n$。每个地雷 $i$ 具有一个位置坐标 $a_i$ 和一个爆炸半径 $r_i$。且满足 $a_1 < a_2 < \dots < a_n$。若第 $i$ 个地雷被引爆,那么所有满足 $|a_j - a_i| \le r$ 的地雷 $j$ 均会被引爆。初始时可以选择一个地雷集合 $S$,引爆这个集合内所有的地雷。求最后结果的总数,模 $10 ^ 9 + 7$。 ::: :::success[思路] 我们先考虑暴搜的状态来推导 dp 状态。然后就会发现,暴搜的状态只能够暴力记录集合 $S$,这样的时间复杂度显然是错的。 所以我们定义状态:$dp_i$ 表示仅考虑前 $i$ 个地雷的引爆情况,且钦定第 $i$ 个地雷不被引爆的方案数。这样就满足了动态规划的无后效性原则。 考虑转移。如果从 $j$ 转移到 $i$,那么需要满足 $j$ 到 $i$ 之间(开区间)的所有地雷不能引爆 $j$ 或 $i$。我们定义 $pre_i$ 和 $nxt_i$ 分别表示第 $i$ 个地雷左边/右边第一个能够引爆 $i$ 的地雷下标。那么 $j$ 和 $i$ 应当满足:$pre_i \le j$ 且 $nxt_j \ge i$。转移就是这样: $$ dp_i \leftarrow \sum \limits _ {j = pre_i} ^ {i - 1} dp_j [nxt_j \ge i] $$ 显然这样是 $O(n ^ 2)$ 的,需要考虑优化。我们可以把上式拆成前缀和相减的形式: $$ \sum \limits _ {j = 0} ^ {i - 1} - \sum \limits _ {j = 0} ^ {pre_i - 1} $$ 这样就可以树状数组“离线”处理了。时间复杂度 $O(n \log_2 n)
至于 pre 和 nxt 数组,单调栈正反两遍 O(n) 即可求出。

P10138 [USACO24JAN] Cowmpetency G

:::info[题意]{open} 给定整数 N, Q, C,求满足条件的整数序列 c_1, c_2, \dots,c_N 的数量,答案对 10 ^ 9 + 7 取模。

要求:

保证所有 a_i 互不相同,且至少存在一个合法序列。

::: :::success[思路] 定义: $$ M_i = \max _ {1 \le j \le i} c_i $$ 即前缀最大值。我们称位置 $i$ 为**记录位置**,当且仅当: $$ c_i > M_{i - 1} $$ 且钦定 $1$ 为记录位置。考虑一条约束 $(a, h)$,条件等价于: $$ c_h > M_a \qquad c_{k} \le M_a \qquad (a < k < h) $$ 所以,按照记录位置的定义: - 位置 $h$ 必定为记录位置; - $(a, h)$ 间的所有位置都不能为记录位置。 容易证明,这两条和所给约束是充要的。 据此,我们可以把所有位置分为三类: 1. 必为记录位置; 2. 不能为记录位置; 3. 自由位置,即随意选择。 显然对于约束 $(a, h)$,只需把区间 $(a, h)$ 定为禁止,$h$ 定为必须即可。 由于 $N$ 较大,我们考虑从 $C$ 入手。定义状态 $dp_i$ 表示,已经处理的前缀的最大值恰好为 $i$ 时的方案数。显然 $i \in [1, C]$。 考虑初始状态。显然 $c_1$ 可以为任何值。当 $c_1 = i$ 时,显然前缀最大值只可能为 $i$。所以,初始时 $$ dp_i = 1 \qquad (1 \le i \le C) $$ 为了方便表示下文的转移,先定义前缀和: $$ pre_i = \sum \limits _ {j = 1} ^ i dp_i $$ 考虑转移。因为 $N$ 过大,但是这个状态仍然需要枚举下标,又发现类别相等的位置会形成一段区间,所以我们可以把上面的分段点整理出来,去重后再枚举。设我们当前需要考虑长度为 $L$ 的一段连续区间 1. 当前区间内所有的点都**必须成为记录位置**。我们在处理约束的时候,每次都会把一个单点定为必须,所以这种情况一定是一个个单点。设此前最大值为 $p < i$,显然有 $$ ndp_i \leftarrow \sum \limits _ {p = 1} ^ {i - 1} dp_p $$ 即 $$ ndp_i \leftarrow pre_{i - 1} $$ 2. 当前区间内所有的点都**不能成为记录位置**。这个区间内所有的元素都要且只要满足 $1 \le c_j \le i$。所以每一个元素都有 $i$ 中方案。所以 $$ ndp_i \leftarrow i ^ L dp_i $$ 3. 当前区间内所有的点都可以随意选择类别。分两种情况讨论: - 第一种情况:原来的最大值已经是 $i$。要使处理之后,最大值依然是 $i$,则选择方案数的上一个情况一样,即 $$ i ^ L dp_i $$ - 第二种情况:原来的最大值为 $p < i$。要使处理之后,最大值达到 $i$,则该区间内至少存在一个 $i$。考虑容斥计算方案数。首先所有元素都在 $[1, i]$ 内随意选择的方案数为 $$ i ^ L $$ 然后,不存在 $i$ 的方案数,即只在 $[1, i)$ 内选择的方案数为: $$ (i - 1) ^ L $$ 所以,两式相减 $$ i ^ L - (i - 1) ^ L $$ 而最大值 $< i$ 的方案数一共有 $$ \sum \limits _ {p = 1} ^ {i - 1} dp_p = pre_{i - 1} $$ 种。所以这种情况的贡献为 $$ [i ^ L - (i - 1) ^ L] pre_{i - 1} $$ 所以,总体转移为 $$ ndp_i \leftarrow i ^ L dp_i + [i ^ L - (i - 1) ^ L] pre_{i - 1} $$ 如何判断一个分段点对应的是哪种类别?对于点 $i$: 1. 若存在一个 $h_j = i$,那么其为记录位置; 2. 若存在一个 $(a_j, h_j)$ 满足 $a_j < i < h_j$,那么其必须不为记录位置; 3. 若没有找到,显然它是自由的。 ::: ## [P9871 [NOIP2023] 天天爱打卡](https://www.luogu.com.cn/problem/P9871) :::info[题意]{open} 有 $n$ 天,每天可以选择**打卡**或**不打卡**。 - 每打卡一天,能量值减少 $d$。 - 不能连续打卡超过 $k$ 天,即不能出现连续 $k+1$ 天全部打卡的情况。 - 有 $m$ 个挑战,第 $i$ 个挑战要求区间 $[l_i,r_i]$ 内的所有天都打卡,满足后获得 $v_i$ 的能量,其中 $l_i=x_i-y_i+1$,$r_i=x_i$。 - 每个挑战只要满足条件就能获得奖励,多个挑战可以同时完成。 求一种打卡方案,使得 $n$ 天结束后的能量值最大。 等价于:选择若干天打卡,在不存在长度为 $k+1$ 的连续打卡区间的前提下,最大化 $$ \sum _ {\text {已完成的挑战 } i} v_i - d \times \text {打卡天数} $$ 注意:能量值允许为负数。 $\color {red} 1 \le n \le 10 ^ 9$。 ::: :::success[思路] 设当前选择打卡区间为 $[L, R]$,那么若某一个挑战 $[l_i, r_i]$ 包含于 $[L, R]$,即 $$ L \le l_i \le r_i \le R $$ 那么可以获得该挑战的能量收益 $v_i$。又因为我们选择的若干打卡区间之间至少有一天不打卡,即 $$ R_{i - 1} + 2 \le L_i, \qquad i > 1 $$ 所以问题转化为: - 求若干不相交且长度 $\le k$ 的区间,使得打卡收益减去打卡花费最大。 先不管 $N = 10 ^ 9$ 的逆天数据范围,我们依然定义状态: - $dp_i$ 表示前 $i$ 天的最大能量。 考虑转移。设最后一次打卡区间为 $[L, R]$,则依照上述要求,有转移: $$ dp_R \leftarrow \max \Big \{ dp_{R - 1}, \max _ L \Big (dp_{L - 2} - (R - L + 1)d + \sum _ {L \le l_i \le r_i \le R} v_i \Big ) \Big \}, \qquad \max \{ 1, R - k + 1 \} \le L \le R $$ 观察到,如果一个打卡区间没有获得挑战奖励,那么直接删去这个区间,一定不会使答案更劣。所以,我们可以令 $R$ 为某个 $r_i$。也即我们只需要在 $r_i$ 处转移。 接下来考虑优化转移。在转移式中把与 $L$ 无关的项移到外面: $$ dp_R \leftarrow \max \Big \{ dp_{R - 1}, -dR + \max _ L \Big (dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i \Big ) \Big \} $$ 不妨设 $$ f(L) = dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i $$ 上式变为: $$ dp_R \leftarrow \max _ {\max \{ 1, R - k + 1 \} \le L \le R} \Big \{ dp_{R - 1}, -dR + \max _ L f(L) \Big \} $$ 接下来只需考虑如何递推地维护 $f(L)$ 即可。容易发现,对 $f(L)$ 产生贡献的,无不可分为以下两种: 1. 挑战奖励。我们当前处理到 $R = r_i$,那么对于所有 $L \le l_i$,都要使 $$ f(L) \leftarrow f(L) + v_i $$ 这是一个区间修改。 2. DP 值产生的贡献。计算出 $dp_R$ 后,因为要递推地维护 $f(L)$,对于所有 $$ L - 2 \ge R $$ 的 $L$,都应该使 $$ f(L) \leftarrow f(L) + dp_R - dp_{R - 1} $$ 这也是一个区间修改。 求 $dp_R$ 时,只需区间查询 $$ [\max \{ 1, R - k + 1 \}, R] $$ 即可。这可以使用线段树维护。 还没完呢。前面忽略了 $N = 10 ^ 9$ 的范围而使用了状态空间为 $O(n)$ 的 DP,要缩减状态空间。考虑 $$ f(L) = dp_{L - 2} + (L - 1)d + \sum _ {L \le l_i \le r_i \le R} v_i $$ 随着 $L$ 的增大: 1. $dp_{L - 2}$ 只可能在 $L = r_i + 2$ 时发生变化; 2. 奖励和只可能在 $L = l_i + 1$ 时发生变化; 3. 而 $(L - 1)d$ 是一个线性增加的项。 又因为 $d > 0$,所以在一段没有变化的区间内,$f(L)$ 一定是单调递增的,只需取最右端的值。所以,只需要维护以下位置: $$ \{ 1 \} \cup \{ l_i \} \cup \{ r_i \} \cup \{ r_i + 1 \} $$ 这些位置都是 $f(L)$ 除 $(L - 1)d$ 这一项外变化的位置的前一位,也即没有变化的区间右端点。 ::: ## [P7519 [省选联考 2021 A/B 卷] 滚榜](https://www.luogu.com.cn/problem/P7519) :::info[题意]{open} 在某地进行了一场 ICPC 竞赛,我们只关心其滚榜环节。共有 $n$ 支队伍参赛,$i$ 号队伍在封榜前通过的题数为 $a_i$。按照过题数从大到小进行排名,若两支队伍过题数相同,则编号小的队伍排名靠前。 滚榜时主办方以 $b_i$ 不降的顺序依次公布了每支队伍在封榜后的过题数 $b_i$(最终该队伍总过题数为 $a_i + b_i$),并且每公布一支队伍的结果,排行榜上就会实时更新排名。现在不知道队伍被公布的顺序,也不知道最终排行榜上的排名情况,只知道每次公布后,本次被公布结果的队伍都成为了新排行榜上的第一名,以及所有队伍在封榜后一共通过了 $m$ 道题(即 $\sum_{i = 1}^{n} b_i = m$)。求最终排行榜上队伍的排名情况可能有多少种。 $\color {red} 1 \le n \le 13, 1 \le m \le 500$。 ::: :::success[思路] 首先,$n$ 极小,可以考虑状压 DP。首先,第一个被公示的队伍过题数应当超过所有队伍。设第 $i$ 个队伍作为第一个被公示的队伍时,需要增加的最少题数为 $st_i$。则 $$ st_i = (\max a) - a_i + [i > p] $$ 其中,$p$ 为满足 $a_p = \max a$ 的最小 $p$。这是因为,第 $i$ 支队伍首先要和当前最大的队伍齐平,如果 $i$ 比当前最大的队伍编号大,那么还需多过一题才能成为榜一。 然后,我们设 $d_{i, j}$ 表示,如果第 $j$ 支队伍紧接着第 $i$ 支队伍被宣布,那么第 $j$ 支队伍**在封榜后**至少需要比第 $i$ 支队伍在封榜后多过的题数。则 $$ d_{i, j} = \max (0, a_i - a_j + [j > i]) $$ 因为 $b_i$ 不降,所以 $d_{i, j} \ge 0$。于是,我们设最终公示顺序为排列 $p$,则 $$ b_i \ge st_{p_1} + \sum \limits_{k = 2}^i d_{p_{k - 1}, p_k} $$ 将 $\sum b$ 展开,可得: $$ m = \sum b \ge n \times st_{p_1} + \sum \limits_{k = 2}^n (n - k + 1) \times d_{p_{k - 1}, p_k} $$ 于是,我们设状态 $dp_{S, i, c}$ 表示,当前选择的集合为 $S$,最后被公示的队伍是 $i$,当前代价为 $c$ 时的方案数。则 $$ dp_{S \cup \{ j \}, j, c + (n - k) \times d_{i, j}} \leftarrow dp_{S, i, c} $$ 其中 $k = |S|$,初始状态为 $dp_{\{ i \}, i, n \times st_i} = 1$。因为实际上 $c \le m$ 的状态都可以被算作答案,所以最终结果为: $$ \sum \limits_{i = 1}^n \sum \limits_{c = 0}^m dp_{\{ 1, 2, \dots, n \}, i, c} $$ ::: ## [CF2159D1 Inverse Minimum Partition (Easy Version)](https://www.luogu.com.cn/problem/CF2159D1) :::info[题意]{open} 给定一个长度为 $n$ 序列 $a$。定义一个序列的价值为,其最后一个元素与序列最小值的比值向上取等后的结果。现在要求对原序列进行划分,使得每一段的代价之和最小。 $1 \le n \le 4 \times 10 ^ 5, 1 \le a_i \le 10 ^ {18}$。 ::: :::success[思路] 我们先说结论。 > **结论 1** $\space$ 我们只需保留原序列中的**严格后缀最小值**(即满足 $a_i < \min \limits_{j = i + 1}^n a_j$ 的 $a_i$),对这个序列求出来的答案与原序列相同。 > > **结论 2** $\space$ 对于最优划分后的序列,每个子段的代价只可能为 $1, 2, 3$。 先看结论 1。我们考虑一个非严格后缀最小值 $a_i$,当其作为划分的右端点时,我们只需把这个端点移至 $i$ 后面的第一个后缀最小值 $j$,答案不会更劣。因为即使右端点后移使得最小值变化,也只会变为该后缀最小值,使得代价变为 $1$。 再看结论 2。我们考虑最优划分(假设)中一个代价 $> 3$ 的子段。设该子段值为 $b_1, b_2, \dots, b_k$,其代价为 $x = \big \lceil \frac {b_k} {b_1} \big \rceil > 3$。显然其长度 $k \ge x$,否则全部划分为单点答案一定更优。子段的最小值为 $b_1$,我们找到一个 $p$,使得 $p$ 为最大的满足 $b_p \le 2b_1$ 的下标。我们将这个子段划为 $[1, p]$ 和 $[p + 1, k]$ 两部分。 - 对于第一部分,显然其代价 $\le 2$; - 对于第二部分,最小值由 $b_1$ 变为了一个 $> 2b_1$ 的值,其代价必然 $\le \big \lfloor \frac x 2 \big \rfloor$。 综上,最后的代价 $\le 2 + \big \lfloor \frac x 2 \big \rfloor \le x$,这个式子在 $x > 3$ 时成立。所以这样改变一定不会更劣。可以证明,优化到最后,整个序列的代价只会由 $\{ 1, 2, 3 \}$ 组成。 读者可以思考,为什么 $x = 3$ 的情况没法被优化掉?尝试自行构造反例。 所以定义状态:$dp_i$ 表示以 $i$ 为右端点的划分方案的最小代价。下面我们设序列 $c$ 为只保留严格后缀最小值的序列 $a$。 考虑转移。首先 $c_i$ 单独成段: $$ dp_i \leftarrow dp_{i - 1} + 1 $$ 然后,考虑最后一段的代价为 $2$ 或 $3$ 的情况。 我们设: - $L_2$:满足 $2c_{L_2} \ge c_i$ 的最小下标; - $L_3$:满足 $3c_{L_3} \ge c_i$ 的最小下标。 最后一段代价为 $2$: $$ dp_i \leftarrow \min \limits_{j = L_2}^{i - 1} (dp_{j - 1} + 2) $$ 代价为 $3$: $$ dp_i \leftarrow \min \limits_{j = L_3}^{i - 1} (dp_{j - 1} + 3) $$ 我们发现,$dp_i$ 是**单调不减**的。我们考虑 $c_i$ 的所属: 1. 若 $c_i$ 单成一段,那么去掉后答案减少 $1$; 2. 若 $c_i$ 作为前面的子段的结尾,那么去掉后答案一定不会变大,因为 $c_i$ 严格递增。 去掉最后一个元素的答案即为 $dp_{i - 1}$。所以 $dp_{i - 1} \le dp_i$ 是成立的。 所以,看似需要数据结构优化转移,其实直接取 $L_2 - 1$ 和 $L_3 - 1$ 即可。 ::: ## [P9352 [JOI 2023 Final] 训猫 / Cat Exercise](https://www.luogu.com.cn/problem/P9352) :::info[题意]{open} 给定一棵 $N$ 个点的树,每个点有一个高度 $a_i$,且高度互不相等。有一只可爱小猫,初始时在最高的点上。每次可以选择一个点放置障碍,然后可爱小猫会按照如下方式移动: - 若可爱小猫当前所在的位置没有障碍,则无事发生; - 若可爱小猫当前所在的位置,以及其所有相邻位置上都有障碍,可爱小猫就会似在你面前; - 否则,可爱小猫会选择当前可达点(即到达路径上没有障碍的点)中,高度最高的点,按照最短路径移动。 在可爱小猫似掉之前,请你求出她最大可以移动多少距离,这是可爱小猫的临终遗愿,你一定要满足她呢。 ::: :::success[思路] 我们按高度从高到低来 DP。定义状态 $dp_u$,表示从 $u$ 开始最多可以走多少步。这里的状态隐含了这样的条件:比当前猫塔高度更高、无法再参与后续移动的部分已经被排除,后续目标位于更低高度的连通块中。 对于猫塔 $u$,如果它能够转移到某个低高度连通块的代表 $v$,那么这一段会产生 $\text {dis} (u, v)$ 次移动,之后还能获得 $dp_v$ 次移动。因此: $$ dp[u] = \max_v \left \{dp_v + \text {dis} (u, v) \right\} $$ 其中,$v$ 是与 $u$ 相邻的低高度连通块中高度最高的点。若不存在这样的连通块,则 $dp_u = 0$。 为什么只需考虑高度最高的点?先说结论: > **结论** $\space$ 对于小猫下一步即将前往的连通块 $C$,设 $v$ 为其中高度最高的点,对于 $C$ 中任意一个点 $w$,都有: > > $$ > dp_v \ge dp_w + \text {dis} (v, w) > $$ > > 这个式子的意义是,从 $dp_v$ 转移,答案不会比从其他点转移更劣。 接下来给出证明。 显然 $w = v$ 时不等式成立。否则,我们设在 $v$ 放置障碍后,$w$ 所在的连通块为 $D$。我们可以通过封死通往其他不包含 $w$ 的连通块的路径来强制让小猫走向 $D$。设 $D$ 中最高点为 $v'$。则由转移式: $$ dp_v \ge dp_{v'} + \text {dis} (v, v') $$ 而显然 $$ dp_{v'} \ge dp_w + \text {dis} (v', w) $$ 我们运用树上距离三角不等式: $$ \text {dis} (v, w) \le \text {dis} (v, v') + \text {dis} (v', w) $$ 得到 $$ dp_v \ge dp_w + \text {dis} (v, v') + \text {dis} (v', w) \ge \text dp_w + {dis} (v, w) $$ 故命题得证。 具体地,如何转移?我们从高度低的塔开始,从下往上转移。我们可以用并查集来维护一个连通块内最高的点,具体的,我们从低到高枚举高度 $h$,然后可以得到高度为 $h$ 的点 $u$。我们从 $u$ 的邻居中,寻找高度 $< h$ 的点 $v$,我们可以从这个连通块内转移。然后并查集的作用就体现出来了,我们使用并查集获取 $v$ 连通块内最高的点 $v'$,按照上述方式转移后,把 $v'$ 的父亲(并查集中)设为 $u$,表示 $v'$ 连通块内最高的点为 $u$。至于计算树上距离,方法多种多样,这里不赘述。 猫一开始位于高度为 $N$ 的猫塔上,因此答案是 $ dp_{p_N} $,其中 $p_i$ 表示满足 $a_j = i$ 的 $j$。 ::: ## [[ABC424G] Set list](https://www.luogu.com.cn/problem/AT_abc424_g) :::info[题意]{open} 有 $N$ 个 idol,另有 $M$ 首歌。每首歌需要 $B_i$ 个 idol 跳舞,而每个 idol 最多可以跳 $A_i$ 场舞。现在要开一张演唱会,需要选出若干首歌,使得每首歌都有足够的 idol 跳舞,且每个 idol 跳舞的场数不能超过各自的限制。每首歌另有一个价值 $C_i$,求选出的所有歌的 $C_i$ 总和最大值。 $\color {red} 1 \le n, m \le 100$。 ::: :::success[思路] 这看着就很像背包啊。很像,很像啊。 首先有一个显然的错误解法。我们求出 $\sum a_i$,然后直接 01 背包: $$ dp_i \leftarrow dp_{i - B_i} + C_i $$ 其中 $1 \le i \le S$。 那么这个错在哪里呢?~~首先如果这是对的那么这题就不可能放在 G~~,其次,在这个做法中,同一个 idol 对于同一首歌的贡献**可能被重复计算**。比如 $N = M = 2, A = [100, 0], B = [2, 2]$,此时 $S = 100 \ge B_1 + B_2$ 显然成立,但是显然这个 idol 不能分裂成两个跳舞,至少题目不允许。 接下来讲正解。我们考虑一个歌曲子集 $T$,其大小 $|T| = t$。这些歌总共需要 $$ \sum \limits _ {j \in T} B_j $$ 次舞蹈。我们考虑第 $i$ 个 idol,在所有歌曲中,她最多能够贡献多少次舞蹈呢?显然为 $$ \min \{ A_i, t\} $$ 次。所以,$T$ 子集合法,当且仅当 $$ \sum \limits _ {j \in T} B_j \le \sum \limits _ {i = 1} ^ N \min \{ A_i, t \} $$ 我们考虑背包 DP。定义状态:$dp_{i, j, s}$ 表示,考虑前 $i$ 首歌,选取 $j$ 首,$\sum B = s$ 时的最大 $\sum C$。 如何转移?我们将 $B$ 从大到小排序,此时每次转移时添加的歌曲一定是最小的。每次添加后,我们都判断一遍 $s \le \sum \min \{ A_i, j \}$ 是否满足即可,此时判断的是最终选取的歌曲子集中**最大的 $j$ 个**的合法性。 为什么只需要判断最大的 $j$ 个?因为不等式右边只与 $t$ 有关,要使整个集合都满足要求,那么前 $k$ 大一定要满足。即,前 $k$ 大满足,是整个集合满足的**充要条件**,这里 $1 \le k \le t$,$t$ 为最终选取歌曲数。 所以,最终转移为: $$ dp_{i, j, s} \leftarrow dp_{i - 1, j - 1, s - B_i} + C_i $$ 其中 $$ B_i \le s \le \sum \limits _ {k = 1} ^ N \min \{ A_k, i \} $$ ::: ## [P13785 [eJOI 2022] Longest Unfriendly Subsequence](https://www.luogu.com.cn/problem/P13785) :::info[题意]{open} 给定一个长度为 $n$ 的序列 $a$。定义一个序列 $b$ 为不友好的,当且仅当: - 不存在下标对 $(i, j)$ 使得 $|i - j| \le 2$ 且 $b_i = b_j$。 求 $a$ 中最长不友好子序列长度。 ::: :::success[思路] 如果依然沿用常规子序列 DP 的状态:$dp_i$ 表示最后一个选取 $i$ 的最优方案,你会发现这个很没前途啊,因为转移过于复杂,不便优化,这里也不写了,毕竟是错误做法。 我们先不考虑在 $N$ 为十万级别能够通过的做法,先来想暴力状态设计。我们发现,如果记录选出子序列的后两个元素,就可以简化转移。于是尝试定义状态: - $dp_{i, j}$ 表示选取的子序列最后两个元素依次为 $a_j, a_i$($a_j$ 先于 $a_i$)时的最优方案。 显然 $j < i$ 且 $a_i \neq a_j$ 时这个状态才能合法。于是转移: $$ dp_{i, j} \leftarrow \max \Big \{ 2, 1 + \max _ {\substack{k < j \\ a_k \neq a_j, a_k \neq a_i}} dp_{j, k} \Big \} $$ 这显然是 $O(n ^ 3)$ 的,无法通过此题。这个应该可以优化到 $O(n ^ 2 \log n)$ 级别,但因为状态空间有 $O(n ^ 2)$,所以还是去不掉这个平方。 于是考虑优化状态。我们发现,$j$ 只需取值于 $[1, i)$ 区间内离 $i$ 最近的 **5 个不同数的最后出现位置**,令其为 $pre_i$。证明如下: 1. 首先,我们可以钦定所有 $j$ 都是 $a_j$ 在 $[1, i)$ 中的最后出现位置。因为子序列的合法性与其中数值在原序列中的下标无关,只与数值有关,且取最后一个一定不会比取前面的更劣; 2. 我们考虑把某个位置 $p$ 插入当前子序列: $$ \dots, h, j, \color {red} p \color {black}, i, s, \dots $$ 依照要求,有: $$ a_p \notin \{ a_h, a_j, a_i, a_s \} $$ 由鸽巢原理,一定存在至少一个 $p \in pre_i$,使得其满足上述要求。因为 $a_h, a_j, a_i, a_s$ 至多有 $4$ 种取值,如果候选集合大小至少为 $5$,那么一定可以找到符合要求的转移。 证毕。于是我们可以把状态定义改为: - $dp_{i, j}$ 表示选取的子序列最后两个元素依次为 $a_{\color {red} pre_{i, j}}, a_i$ 时的最优方案。 转移变为: $$ dp_{i, j} \leftarrow \max \Big \{ 2, 1 + \max _ {\substack{k < j \\ a_k \neq a_{\color {red} pre_{i, j}}, a_k \neq a_i}} dp_{\color {red} pre_{i, j} \color {black}, k} \Big \} $$ 这样时间复杂度就由 $O(n ^ 3)$ 变为了 $O(25n) = O(n)$,状态空间也大幅缩减。 ::: ## [AT_npcapc_2024_o New School Term](https://www.luogu.com.cn/problem/AT_npcapc_2024_o) :::info[题意]{open} 给定 $2N$ 个点,要求将其划分为两个大小相同的组。给定 $M$ 个要求,每个要求用 $(u_i, v_i)$ 表示,其含义为 $(u_i, v_i)$ 不能在同一个组内,否则就要承受 $2 ^ i$ 的代价。求代价最小的情况下,每个点属于哪个组。 ::: :::success[思路] 这是一道值得反复品鉴的好题。我尽量把所有细节都讲清楚。 下面设 $V = 2N$。 首先,若干个不互相矛盾的不同组的要求,可以构成一个二分图。而维护二分图的一个经典技巧就是扩展并查集,又称拆点。具体地,在本题中,可以把点 $i$ 拆成两个 $i, i + 2N$,分别表示 $i$ 在两个点集中的点。举一例:若 $u, v$ 在并查集内联通($u + V, v + V$ 同样联通,这点在维护的时候会保证),那么 $u, v$ 同色,否则 $u, v$ 异色,且此时有 $u, v + V$ 联通和 $u + V, v$ 联通。还需要对于每个连通块根节点都维护其所统辖的连通块内的黑/白色点数量,这个在合并两连通块时可以维护。 因为以任意 $> 1$ 的数为底数的幂函数都是递增的,这个自己对 $f(x) = 2 ^ x$ 求导就可以得到;所以显然是先满足靠后的要求。所以,我们可以贪心地从后往前加边,每个要求就是一条跨越两集合之间的边。 显然二分图中会存在多个连通块。因为当前可能存在若干点没有要求限制,而这些点间显然不需要连边。设第 $i$ 个连通块的黑/白色节点个数分别为 $a_i, b_i$,而题目要求两组大小相等,则应当确定是否存在一个长度为连通块个数的序列 $t$,使得 $$ \sum t_i = N, \qquad t_i \in \{ a_i, b_i \} $$ 这里又有一个技巧。我们可以把 $sum = \sum \min (a_i, b_i)$ 作为基础,然后把每个连通块看作一个重量 $w = |a_i - b_i|$ 的物品。是否存在合法的方案,就等价于是否可以选取若干个物品,使得重量和恰好为 $N - sum$。 然后,我们考虑第 $i$ 个要求 $(u_i, v_i)$。 若此时 $u, v$ 两点的关系已经确定,即 $u, v$ 联通或 $u, v + V$ 联通,那么此时这个要求的代价已经确定,可以直接跳过。 若此时 $u, v$ 两点的关系尚未确定,我们需要考虑这个要求是否需要被满足。下面来说明一下两个连通块合并后黑/白色点的个数变化。设此前两连通块黑/白色点的个数分别为 $(c_{u, 0}, c_{u, 1})$ 和 $(c_{v, 0}, c_{v, 1})$,合并后黑/白色点的个数分别为 $(c_0, c_1)$。 若 $u, v$ 异色,则 $$ c_0 = c_{u, 0} + c_{v, 1}, \qquad c_1 = c_{u, 1} + c_{v, 0} $$ 若 $u, v$ 同色,则 $$ c_0 = c_{u, 0} + c_{v, 0}, \qquad c_1 = c_{u, 1} + c_{v, 1} $$ 如果使用普通背包 DP,那么每次都要重新跑一遍,时间复杂度高达 $O(N ^ 3)$,会起飞。 但是有一种东西叫作可撤销背包 DP。我们考虑将上面的可行性背包 DP,改为方案数 DP。这样一来,就可以支持撤销了,具体地,只需要减去方案数即可。判断是否可行,也只需判断对应的 $dp$ 值是否非零即可。但是方案数太大了,容易起飞,于是我们将其对一个大质数取模。至于为什么是个大质数,因为要减小方案数能够被其整除的概率。具体地,增加一个物品: ```cpp if (!w) return; for (int i = w; i <= n; i++) { dp[i] = (dp[i] - dp[i - w] + MOD) % MOD; } ``` 删去一个物品: ```cpp if (!w) return; for (int i = n; i >= w; i--) { dp[i] = (dp[i] + dp[i - w]) % MOD; } ``` 注意一定要判断 $w = 0$ 的情况。这样单次更新就是 $O(N)$ 的了。 关于如何维护 $sum$,如下:若 $u, v$ 异色,那么 $$ sum \leftarrow sum - (\min (c_{u, 0}, c_{u, 1}) + \min (c_{v, 0}, c_{v, 1})) + \min (c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0}) $$ 此时需要在 DP 中删去 $(c_{u, 0}, c_{u, 1})$ 和 $(c_{v, 0}, c_{v, 1})$,加入 $(c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0})$。 判断完异色之后,如果非法(即 $dp_{N - sum} = 0$),那么需要继续令 $u, v$ 同色,此时 $$ sum \leftarrow sum - \min (c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0}) + \min (c_{u, 0} + c_{u, 1}, c_{v, 1} + c_{v, 0}) $$ 删去 $(c_{u, 0} + c_{v, 1}, c_{u, 1} + c_{v, 0})$,加入 $(c_{u, 0} + c_{u, 1}, c_{v, 1} + c_{v, 0})$ 即可。 最终还要构造答案。我们可以按照上面的技巧重新做一遍可行性 01 背包 DP,然后记录每个连通块是否被选中。按照是否被选中来划分集合即可。这里放一份片段,细节有点多: ```cpp pair<bool, int> ndp[2N]; bool inst0[4N]; ... int target = n - sum; ndp[0] = {1, 0}; for (int i = 1; i <= (V << 1); i++) { if (find(i) != i) continue; int j = find(i <= V ? i + V : i - V); if (i > j) continue; int root = cnt[i].first <= cnt[i].second ? i : j; int w = abs(cnt[root].first - cnt[root].second); inst0[root] = 1; if (!w) continue; for (int k = target; k >= w; k--) { if (!ndp[k].first && ndp[k - w].first) { ndp[k] = {1, root}, pre[k] = k - w; } } } for (int k = target; k; k = pre[k]) { int r = ndp[k].second; inst0[r] = 0; int s = find(r <= V ? r + V : r - V); inst0[s] = 1; } ``` 建议自己磕出做法,不要看我写的,实在调不出再来看。这样对你的实力提升较大。 ::: ## [P17833 [CSP-S 2026] 迁徙 / migrate](https://www.luogu.com.cn/problem/P17833) :::info[题意]{open} 给定 $N$ 个坐标严格递增的岛屿,坐标为 $a_1, a_2, \ldots, a_N$,以及一个距离限制 $d$。 从岛屿 $i$ 可以直接飞到岛屿 $j$,当且仅当: $$ |a_i - a_j| \le d $$ 统计有多少对起点、终点,使得从起点到终点恰好存在两条不同的最短路线。 $1 \le n \le 2 \times 10 ^ 6$。 ::: ::::success[思路] 给一个不要 dp of dp 的正经 DP 做法。感谢 @yuhong056 dsa 给我的做法,不然我都不会想做这个题,快去 % 他。 这种 -S 正赛题最精了,他可以出得没有任何过难的算法,但你还是做不出。而且平方级暴力 DP 简直没有一点可优化的空间,直接 ban 掉数据结构,最克我这种人了。 回到正题。首先,容易知道,两点间的最短路数量,等于最短路上经过的每一段间的最短路径数乘积。这个是一个再简单不过的乘法原理。 而题目要求有 $2$ 条最短路径的点对个数,也就意味着,每一段的最短路径数只能长这样: $$ 1 \times \dots \times 1 \times \color {red} 2 \color {black} \times 1 \times \dots \times 1 $$ 设某一满足要求(最短路径数为 $2$)的点对间,有 $(x, y)$ 两点间的最短路径有两种选择,对应上面的 $2$,且 $(x, y)$ 是**最近的**满足上述要求的点对。有如下结论: > **结论 1** $\space$ $(x, y)$ 间的最短路长度一定为 $2$。 >:::info[证明] >显然不可能为 $1$。当长度 $\ge 3$ 时,总可以从两边去掉一些点,使得最短路长度变短,与最近这一前提条件相悖。 >::: > **结论 2** $\space$ $(x, y)$ 间如果有 $x \rightarrow a \rightarrow y$ 与 $x \rightarrow b \rightarrow y$($a < b$)两种走法,则一定不存在 $x \rightarrow c \rightarrow y$,使得 $a < b < c$。这个显然。因为只有两种走法。但是你会得到一个奇妙的结论:$b = a + 1$。 > **结论 3** $\space$ 设 $L_u, R_u$ 分别为点 $u$ 往左/右走最远能够到达的点编号,则 $a = R_x, b = L_y$。 > :::info[证明] > 因为 $(x, y)$ 间最短路长度为 $2$,所以 $x, y$ 一定可以直接到达 $a, b$,也就等价于 > $$ > a \le R_x, \qquad b \ge L_y > $$ > 故 $a, b$ 的合法取值区间为 > $$ > [R_x, L_y] > $$ > 容易知道,这个区间内的所有点都可以被取为 $a, b$。而由上一个结论:$b = a + 1$,代表该区间长度为 $2$,故 > $$ > a = R_x, \qquad b = L_y > $$ > ::: 于是问题被转化为:有多少 $(p, q)$ 分别能够衔接至 $x, y$ 且 $p \rightarrow x$ 和 $q \rightarrow y$ 分别只有一条路径。 设状态 $dp_i$ 表示,有多少个 $j < i$ 满足: - $j$ 无法跨越 $i$ 且 $j \rightarrow i$ 只有一条路径。 考虑第 $j$ 个点对 $dp_i$ 的贡献: 1. $i = j$,即最短路长度为 $0$。此时贡献为 $1$。 2. $j \rightarrow i$ 的最短路长度为 $1$。此时需要满足: $$ R_j = i, \qquad L_i \le j $$ 但是这样直接求有点麻烦。考虑将 $R_j = i$ 稍作变换: $$ R_j = i \iff X_i \le X_j + d < X_{i + 1} \iff X_i - d \le X_j < X_{i + 1} - d \iff \boxed {L_i \le j < L_{i + 1}} $$ 于是这部分 $j$ 的贡献为 $\min (i, L_{i + 1}) - L_i$。 3. $j \rightarrow i$ 的最短路长度 $> 1$。我们选取 $j \rightarrow i$ 路径上的倒数第二个点 $k$,即 $j \rightarrow \dots \rightarrow k \rightarrow i$。此时需要满足: $$ R_k = i, \qquad L_i = k $$ 容易发现,这里 $k$ 所满足的条件比第二条的更为严苛。因为要保证 $k$ 为最小的可取值,否则会算重。这个条件等价于 $$ R_{L_i} = i $$ 若 $i$ 满足上述条件,则可以从 $dp_{L_i}$ 转移而来。而 $k = L_i$ 的贡献在第二条中已计算过,所以要 $-1$。 总之,这部分的转移为: $$ dp_i \leftarrow 1 + \min (i, L_{i + 1}) - L_i + [R_{L_i} = i] (dp_{L_i} - 1) $$ 右边的同理。读者可以自行推导。 求出左右两边的 $dpl_i, dpr_i$ 后,考虑枚举 $x, y$,计算如何求出满足条件的 $p, q = p + 1$ 个数。应当满足: $$ L_x = p, \qquad R_y = q $$ 依照上面的变换方法,得 $$ L_{p + 1} \le x < L_{p + 2}, \qquad R_{p - 1} < y \le R_p $$ 还要考虑 $x < p, y > q$。我们知道,这些区间里的 $x, y$,对于答案分别都有一些基础贡献: $$ C_x = \min (p, L_{p + 2}) - L_{p + 1}, \qquad C_y = R_p - \max (p + 1, R_{p - 1}) $$ 还要加上左右两侧只有一种情况的贡献。左边,只有 $dpl_{L_{p + 1}}$ 对于 $C_x$ 有贡献。 :::info[证明] 反证法。设我们当前固定一组满足条件的 $x, y$: $$ R_x = p + 1, \qquad L_y = p $$ 假设 $x > L_{p + 1}$。 因为 $x > L_{p + 1}$,所以必然存在边 $x \rightarrow p$ 和 $x \rightarrow p + 1$。又 $L_y = p$,所以 $p \rightarrow y$ 和 $p + 1 \rightarrow y$ 必然存在。 故从 $x$ 到 $y$ 至少有两条路径:$x \rightarrow p \rightarrow y$ 和 $x \rightarrow p + 1 \rightarrow y$。 设 $j \le L_{p + 1}$。我们要证明,任意一个满足 $j \rightarrow x$ 最短路唯一 $j$,都不可能给答案带来贡献。设 $\operatorname {dis} (j, x) = h, z = L_{p + 1}$,则 - $z \rightarrow p + 1$ 存在; - $L_p \le z$; - 对于任意 $z \le t < p$,$t \rightarrow p$ 存在。 我们取 $j \rightarrow x$ 最短路上最后一个中转点 $t$。显然 $j \le t < x < p$。分两种情况讨论: 1. $t \ge z$。因为 $t \ge z = L_{p + 1} \ge L_p$,故 $t \rightarrow p$ 存在。于是可以直接走: $$ j \rightarrow \dots \rightarrow t \rightarrow p \rightarrow y $$ 这条最短路的长度为 $h + 1$。而经过 $x$ 的两条最短路: $$ j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p \rightarrow y $$ $$ j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p + 1 \rightarrow y $$ 长度均为 $h + 2$。所以,原来的最短路结构被破坏。 2. $t < z$。因为 $t \rightarrow x$ 存在,且 $t < z < x$,故 $X_x - X_z < X_x - X_t \le d$,所以 $t \rightarrow z$ 也存在。此时可以构造出三条路径: $$ j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p \rightarrow y $$ $$ j \rightarrow \dots \rightarrow t \rightarrow x \rightarrow p + 1 \rightarrow y $$ $$ j \rightarrow \dots \rightarrow t \rightarrow z \rightarrow p + 1 \rightarrow y $$ 这些最短路的长度均为 $h + 2$。与前文所述有两种方案相悖。 故结论成立。 ::: 右边是同理的。而且取左边、右边的 $dp$ 值,分别有前提条件: $$ L_{R_{p + 1}} = p, \qquad R_{L_{p}} = p + 1 $$ 这个读者可自己思考。记得算贡献的时候要 $-1$,因为已经计算过基础贡献了。 ::::