# 新坑

Author: Fanyi Pu

Published: 2019-08-04

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cfdpproblems>

CodeForces 动态规划题目练习与题解。

决定开个新坑，刷一些 CF 上的 `dp` 题。

现在做了几题：

**10**

\[2019.8.5]忽然发现 sto[**xielinhan**](https://codeforces.com/profile/xielinhan)orz 怎么什么题都做过啊，果然是神仙……

\[2019.8.6]大家快看这里有个叫 `pufanyi` 的沙雕自闭了：

![](https://pufanyi.com/posts/oi-icpc/codeforces/cfdpproblems/zibi.avif)

果然他是个菜鸡……

\[2019.9.21]文化课真香……感觉好久没做题了……

![](https://pufanyi.com/posts/oi-icpc/codeforces/cfdpproblems/gugugu.avif)

## CodeForces 913F Strongly Connected Tournament

有 $n$ 个国际象棋棋手，他们先两两比赛，实力强的会有 $p$ 的概率打败实力弱的（$p$ 从头至尾都是相同的），然后赢得把边连向败的。然后再把每个强连通分量的抠出来继续做，知道所有人都有一个唯一的排名。求共期望下棋多少盘。

我们令 $f_i$ 表示有 $i$ 名棋手的答案，我们考虑转移。

我们有：

$$
f_i=\sum_{j=1}^{n} g_{i,j}s_{j}\left(f_j+f_{i-j}+i(i-j)+\frac{j(j-1)}{2}\right)
$$

其中 $g_{i,j}$ 表示从 $i$ 个点中选出 $j$ 个点而这 $j$ 个点均被另外 $i-j$ 个点打败的概率，$s_i$ 表示 $i$ 个点是强连通分量的概率。

大概思路就是枚举一下

只要我们算出 $s_i$ 和 $g_{i,j}$，剩下的就是解方程的问题了。

我们考虑 $g_{i,j}$ 的转移。

我们考虑最后一个节点是否选入 $j$ 个的这个集合中：

$$
g_{i,j}=p^{i-j}g_{i-1,j-1}+(1-p)^{j}g_{i-1,j}
$$

然后我们考虑 $s_i$。

我们考虑用 $g$ 转移 $s$：

$$
s_i=1-\sum_{j=1}^{i-1} s_jg_{i,j}
$$

代码：[58105715](https://codeforces.com/contest/913/submission/58105715)

## CodeForces 908G New Year and Original Order

给 $n\le 10^{700}$，问 $1$ 到 $n$ 中每个数在各数位排序后得到的数的和。答案膜 $10^9+7$。<sup>[1](https://pufanyi.com/blog/oi-icpc/codeforces/cfdpproblems#user-content-fn-1)</sup>

一道有趣的数位 dp。

我们令 $f_{i,j,k,[0/1]}$ 表示从高到低第 $i$ 位，共有 $j$ 个数超过 $k$，是否卡上界（$[0/1]$）。

转移比较简单：

```cpp
f[i + 1][j + (p >= k)][k][K && (p == d[i + 1])] += f[i][j][k][K];
```

考虑统计答案，冷（da）静（kai）思（ti）考（jie）之后就会发现是这个：

$$
\sum \left(f_{n,i,j,0}+f_{n,i,j,1}\right)\times \underbrace{11\cdots 111}_{i\text{个}1}
$$

代码：[58147084](https://codeforces.com/contest/908/submission/58147084)

## CodeForces 889E Mod Mod Mod

给出长度为 $n(n\le 200000)$ 的序列 $\{a\}$，定义 $f(x,i)(x\ge 0,i\ge 1)$ 为：

$$
f(x,i)=
\begin{cases}
x\bmod a_i&  i=n\\
x\bmod a_i + f(x\bmod a_i,i+1)& 1\le i < n
\end{cases}
$$

求 $f(x,1)$ 的最大值。

神仙的状态定义。

我们考虑把答案分解为 $ki+b$ 的形式，$i$ 表示的是做到 $a_i$ 的时候。

我们考虑 $g_{i,j}$ 表示到第 $i$ 个数，$k=j$ 时最大的 $b$。这样答案就是 $\max_{i=0}^{\infty}ni+g_{n,i}$。

我们考虑优化这个方程。

首先我们需要发现一个性质：最优方案一定有某个余数为 $a_i-1$，否则整体 $+1$ 即可。<sup>[2](https://pufanyi.com/blog/oi-icpc/codeforces/cfdpproblems#user-content-fn-2)</sup>

于是我们发现，其实只要考虑是哪次取模后变成 $a_i-1$ 即可。

我们考虑在 `dp` 中体现。

我们发现许多状态是冗余的，因为可以从一些状态计算出另一些状态的答案。

事实上就是整体上移和整体下移。

于是我们有转移方程：

$$
\begin{cases}
    f_{i+1,x\bmod a_i}\leftarrow f_{i,x}+(x-x\bmod a_i)\times(i-1)&\text{（之前已经是卡上界了，这次直接取模）}\\
    f_{i+1,a_i}\leftarrow f_{i,x}+a_{i+1}(x-x\bmod a_i - a_i)\times(i-1)&\text{（比较难理解，画个图会比较清晰，大概是整体下移了一些，使得$x\bmod a_i=a_i-1$）}
\end{cases}
$$

这个东西直接用 `map` 维护即可。

一个结论是如果 $x>y$，则 $x\bmod y\le \frac{x}{2}$。这个东西好像曾经 cf 有道数据结构题就用的是这个结论。大概就是考虑 $y\le \frac{x}{2}$ 和 $y>\frac{x}{2}$ 讨论即可。所以复杂度是 $\mathcal{O}(n\log n\log a_1)$

代码：[58244734](https://codeforces.com/contest/889/submission/58244734)

## CodeForces 886E Maximum Element

题意就是有一个老哥发明了一种~~神奇的~~求序列最大值的算法：

```cpp
int fast_max(int n, int a[]) {
    int ans = 0;
    int offset = 0;
    for (int i = 0; i < n; ++i) {
        if (ans < a[i]) {
            ans = a[i];
            offset = 0;
        } else {
            offset = offset + 1;
            if (offset == k) {
                return ans;
            }
        }
    }
    return ans;
}
```

看起来挺牛皮，但是有一定错误率。给出 $n,k$，求有多少个 $1\sim n$ 的排列能把这位老哥给卡掉，答案对 $10^9+7$ 取模。

我们令 $f_i$ 表示长度为 $i$ 的排列时，且 $i$ 在第 $i$ 个数的答案。

转移时我们考虑第 $i-1$ 个数放在哪儿：

如果放在前 $i-k-1$ 位，因为二元组 $(i-1,i)$ 是不合法的，所以另外的可以乱放，即 $(i-k-1)\cdot (i-2)!$。

如果放在最后 $k$ 位（当然最后一位是 $i$），那么假设它放在了第 $j$ 位，则 $j\sim i$ 这一段肯定是合法的，所以有 $P_{i-2}^{i-j-1}=\frac{(i-2)!}{(j-1)!}$ 种方案，又因为前 $j$ 个必须不合法，所以有 $f_j$ 种方案。综上，有 $f_j\cdot \frac{(i-2)}{(j-1)!}$ 种方案。

综上，我们可以得到方程：

$$
f_i=(i-k-1)\cdot(n-2)!+\sum_{j=i-k}^{i-1}f_j\cdot \frac{(i-2)!}{(j-1)!}
$$

发现这个 $\sum$ 可以前缀和，维护一下就变成 $\mathcal{O}(n)$ 的了。

代码：[58319515](https://codeforces.com/contest/886/submission/58319515)

## CodeForces 878E Numbers on the blackboard

有一个长度为 $n$ 的序列 $\{a\}$，每次询问其中一段区间 $[l,r]$，对这个区间内部的点进行操作，每次操作可以找到两个相邻的数 $x,y$ 将其合并成 $x+2y$，询问把这个区间缩成一个数是，这个数最大可能是多少，每个询问独立，答案对 $10^9+7$ 取模。

不知道为什么，交了 60 多发还是 `T on 40`，然后就去膜拜别人代码了……

我们发现其实就是求 $\sum_{i=l}^r 2^{k_i}a_i$，其中 $k_l=0$，其余的 $k_i\in [1, k_{i-1}+1]$。

那么我们发现，对于每一个询问，我们都可以把 $k$ 分成若干段区间，每一段区间 $[s, t]$ 表示 $k_s=1$，$k_i=k_{i-1}+1(i\in \left(s, t\right])$，当然，第一段 $k_s=0$。

我们考虑离线枚举右端点 $r$，显然，如果 $a_r<0$，那么 $a_r$ 单独成一段，否则与前一段合并，知道该段的值小于 $0$，我们发现合并是 $\mathcal{O}(1)$ 的（然而一开始的时候我硬生生地写成了 $\log$）。

我们考虑用并查集维护每一段，每次查询即可。

不过讲道理这跟 `dp` 有关系吗？~~不管反正标签有 `dp`。~~

代码：[58520589](https://codeforces.com/contest/878/submission/58520589)

## CodeForces 924E Wardrobe

有 $n(n\le 10^4)$ 个箱子，每个箱子有一个高度 $h_i(\sum h_i\le 10^4)$，一些箱子是重要的。现在要把所有箱子叠放在一起。问有多少个箱子底部的高度位于 $[l,r]$。

一道有趣的背包问题，感觉跟那道[小矮人](https://www.luogu.org/problem/P4823)差不多。

首先我么需要发现一个性质，那就是最优解肯定是先一段不重要的，在一段重要的，最后一段不重要的。正确性显然。

我们考虑到箱子底部比较难受，于是我们想到用把整个系统倒过来，这样我们就相当于是在考虑箱子顶部了。

我们发现我们需要知道这样一些东西：最低端那些不重要的箱子是那些（因为顺序无关），当然这样其实也知道了最顶端的情况。

我们还需要知道重要箱子的排列情况。

先考虑不重要的箱子，我们发现这些箱子只是给我们打一个“底座”，所以我们可以直接 `dp` 出来，其实就是个背包。

然后我们考虑重要的箱子。

有一个结论是把这些重要的箱子从大到小排序，然后直接做一遍背包（在之前不重要的箱子的那个 `dp` 数组之上直接做就可以了）就是对的。

那为什么要从大到小排序呢？

我们考虑这个背包的本质其实就是先把这些箱子按照一定顺序从下往上排，我们可以删掉任意多的箱子使得 $[l,r]$ 内重要的箱子顶最多。

我们大概考虑是把最小的那些放在 $[l,r]$ 内，而一些大的要么删掉，要么和不重要的箱子一起当“底座”。

所以我们考虑从大到小排序，如果不删，就是当“底座”，否则就是把它删掉。

代码：[58638973](https://codeforces.com/problemset/submission/924/58638973)

## CodeForces 1218A BubbleReactor

给你 $n(3\le n\le 15000)$ 一棵环套树，一开始全是白点。先给一个点染成黑色，获得 $n$ 的收益。然后每次可以选择一个与黑色点相邻的白点并将其染成黑色，获得收益是其所在连通块的大小。求最大收益。

$\mathcal{O}(n^2)$ 居然过了，然后去围观了一下标算发现也是 $\mathcal{O}(n^2)$ 的。

CF 机子真快。

把环上的边全部删除，以换上点为根，可以得到一个森林。

先令 $f_i$ 表示从 $i$ 开始把 $i$ 的所有子树全部染黑所能获得的代价，这个很好 `dp`。

然后令 $g_i$ 表示从 $i$ 点开始往子树外把 $i$ 的所有子树全部染黑所获得的代价。特殊地，第一次也就是染第 $i$ 个点时的贡献为 $n-s_i$ 而不是 $n-s_i+1$，其中 $s_i$ 表示 $i$ 的子树大小。因为这样才能让 $f_i+g_i$ 直接表示从 $i$ 点开始染色的答案。

我们考虑先 `dp` 出环上的 $g$ 数组，然后往儿子 `dp`。

我们令 $h_{l,r}$ 表示环上将 $[l,r]$ 这些点染黑并将其子树染黑的答案，显然 $h_{i,i}=f_i$。

我们令 $pre(i)$ 表示环上 $i$ 的上一个，$nxt(i)$ 表示 $i$ 的下一个，比如如果环大小为 $m$，则 $nxt(m)=1,pre(1)=m$。

如果 $l>r$，那其实就是越过了 $m$ 点，重新回到了 $1$ 点。

我们有转移：

$$
h_{l,r}=\max\left\{h_{nxt(l),r}+f_l+\sum_{k\in [nxt(l),r]}s_k,h_{l,pre(r)}+f_r+\sum_{k\in[l,pre(r)]}s_k\right\}
$$

于是最终答案

$$
g_{i}=h_{nxt(\text{$i$在环上的位置}),pre(\text{$i$在环上的位置})}
$$

我们考虑对 $h$ 数组压位。

考虑到 `dp` 第一层循环是枚举 $len$（即 $r-l+1$），于是我们可以直接令状态为 $h_{len,l}$，然后就可以把 $len$ 压掉了。

最后余下的点直接从上往下 `dp` 即可。

代码：[60925813](https://codeforces.com/problemset/submission/1218/60926419)

## CodeForces 1203F2 Complete the Projects (hard version)

Div. 3 的题好难啊……

有 $n(n\le 100)$ 个任务，初始有一个分数 $r(r\le 30000)$，做第 $i$ 个任务需要达到 $a_i(1\le a_i\le 30000)$ 的分数，完成后分数会增加 $b_i(-300\le b_i\le 300)$。每一时刻分数都需要大于等于 $0$，求最多能完成的任务数量。

首先肯定想到的是背包，和[小矮人](https://www.luogu.org/problem/P4823)（完了去看题目的时候发现为什么现在小矮人变成 $n\log n$ 的了，不管了，[先记录一下](https://www.cnblogs.com/812-xiao-wen/p/11545341.html)，写完这篇题解再说）差不多，我们考虑背包的顺序。

显然 $b_i\ge0$ 和 $b_i<0$ 是要分类的，先做 $b_i\ge 0$ 的，因为 $b_i<0$ 的只能让分数下降，在最前面肯定不优。

显然对于 $b_i\ge0$ 的，我们可以对于 $a_i$ 从小到大排序。

我们考虑如何对 $b_i<0$ 的进行排序。

我们假设有 $i,j$，$i$ 放在 $j$ 前面更优，那么我们就优，那只能是如果取完 $j$，就不能再取 $i$ 了。

我们假设开始有 $r$ 的积分，我们有：

$$
\begin{cases}
r\ge \max(a_i,a_j)\\
r+b_i\ge a_j\\
r+b_j< a_i
\end{cases}
$$

于是我们有：

$$
a_j-b_i\le r<a_i-b_j
$$

即：

$$
a_i+b_i>a_j+b_j
$$

于是我们按 $a_i+b_i$ 从大到小排序即可。

代码：[61593790](https://codeforces.com/contest/1203/submission/61593790)

## CodeForces 1234F One Node is Gone

感觉现在沉迷于 Div. 3 了……

题目大意是给你一个字符集为 $20$，长度为 $10^6$ 的字符串，你可以翻转其中的一个子串，使操作后的串最大完美子串最长。完美子串就是该子串中没有字符是相同的。

显然就是让你找两个不相交的字符串他们拼起来是完美的。

然后我们发现我们不用考虑相交，因为两个子串相交就肯定是不完美的了。

考虑到找到的两个串首先肯定分别都是完美子串，我们考虑把所有完美子串都找出来。

不难证明暴力找子串的复杂度是 $\mathcal O(n\left|\sum\right|)$，因为对于每个字符，以他们为结尾的完美子串最多不过 $n$ 个。

然后我们直接类似高维前缀和一样预处理一下高维前缀 $\max$，最后统计一下答案即可。

代码：[61748541](https://codeforces.com/contest/1234/submission/61748541)

## CodeForces 1218H Function Composition

题目大意是给你一个长度为 $n$ 的数列 $a$，定义 $f(x,y)=\begin{cases}x&y=0\\a_{f(x,y-1)}&y>0\end{cases}$，让你求在 $1\sim n$ 中，有多少个 $x$ 满足 $f(x,m)=y$，$q$ 次询问，$1\le n\le 2\cdot 10^5,1\le a_i\le n,1\le q\le 10^5,1\le m\le {10}^{18},1\le y\le n$。

我们考虑 $i$ 向 $a_i$ 连一条有向边，不难发现这张图变成了环套内向森林。

我们考虑将询问离线。

首先考虑 $y$ 为不在环上点的询问。这个显然只要 `dp` 一下即可，就是记 $f_{i,j}$ 表示到第 $i$ 个点需要 $j$ 步的答案，向上转移的时候启发式合并一下即可。当然用 `dfs` 序是可以 $\mathcal{O}(n)$ 做的。

考虑 $y$ 在环上的询问。我们对每个环找到环上一条边，将这条边断开，分别处理路径经过这条边的答案和不经过这条边的答案，这两个都可以类似上面的 `dp` 做，最后对加一下即可。

代码：[61582213](https://codeforces.com/contest/1218/submission/61582213)

## Footnotes

1. 翻译来自[luogu.org](https://www.luogu.org/problem/CF908G)

2. 摘自[zory.ink](http://zory.ink/posts/90dc#CF889E-Mod-Mod-Mod)