dp选做
dp选做
省选dp挂了不会来补一补
刷题记录-2022暑假前
UVA1626 括号序列 [dp] [区间dp]
区间dp(似乎括号类的都是区间dp? )
设 $f_{l, r}$ 表示把区间l到r中补到合法的操作步数, 则转移是:
最外侧是匹配的括号: $f_{l, r}=f_{l+1, r-1}\ \ s. t. \ s_l=s_r$
区间由若干 $f_{l, r}=\min_{l\le k\le r}{f_{l, k}+f_{k+1, r} }$
在最右侧添加一个与最左侧的括号匹配的括号或相反, 发现这种情况不优于直接在与这个新添加的括号匹配的括号旁边直接匹配
然后初始情况就是 $f_{i, i}=2$ , 表示为每个括号加一个反括号匹配
这题输出方案, 所以记录最有解位置即可.
P1220 关路灯 [dp] [区间dp]
由于老王走过去关一盏灯时顺手关掉路上经过的一定不劣, 所以被关掉的灯是一个区间, 于是记 $f_{l, r}$ 表示已经被关了的灯的区间, 发现这样转移不了, 比如当我们向右扩展一位时我们不知道老王是刚刚关完左端点的灯还是右端点的, 所以设 $f_{l, r, 0/1}$ 表示区间 $[l, r]$ 已经关掉, 老王此时正在左端点或右端点转移即可.
UVA1362 Exploring Pyramids [dp] [区间dp] [计数dp]
每个子树对应欧拉序上一段区间, 可以区间dp统计答案
设 $f_{l, r}$ 表示 $[l, r]$ 这段区间的方案数, 转移就是枚举第一棵子树划分到哪里, 即
$$
f_{l, r}=f_{l+1, k-1}*f_{k+1, r-1}\ s. t. \ s_k=s_l=s_r\ \mathrm{and}\ k\in[l+2, r-2]
$$
$s$ 为颜色区间, 因为 $l$ , $r$ , $k$ 对应的都是根的颜色.
P7914 [CSP-S 2021] 括号序列 [dp] [区间dp] [计数dp]
仍然区间dp
$f_{i, j}$ 表示区间 $[i, j]$ 的方案数, 则转移就是同UVA1626最外层相等的情况和中间划分的情况, 但这题要求方案数, 发现对于中间划分时, 形如”()()()”的括号既可以划分成”()+()()”也可以划分成”()()+()”, 会被计算多次, 所以设 $g_{l, r}$ 表示 $l$ 和 $r$ 恰好匹配的情况, 转移就成了 $f_{l, r}=g_{l, k}*f_{k+1, r}$ , 然后考虑亿点点细节.
P8352 [SDOI/SXOI2022] 小 N 的独立集 [dp] [计数dp] [树形dp]
终于不是区间dp
一开始觉得设 $f_{u, i, 0/1}$ 表示u子树最大独立集为i, 在u选/不选时取得, 显然无法转移
设 $f_{u, i, j}$ 表示 $u$ 的子树中, 如果选 $u$ 最大独立集为 $i$ , 如果不选最大独立集为 $j$ 的方案数.
转移时加入每个儿子, 对每个儿子枚举 $i’$ 和 $j’$ , 式子就是
$$
f_{u, i+j’, j+\max(i’, j’)}+=f_{v, i’, j’}
$$
然后要注意到若对于节点 $u$ , 其 $i-j\le k$ 因为选的情况强制不选根节点只会减少 $k$ , 而对于 $j-i>k$ 的情况, 对于它转移时的 $j$ 和 $i$ , $\max(i, j)$ 一定不是i且再也不会和它有关系, 可以压到一起处理.
P5504 [JSOI2011] 柠檬 [dp] [斜率优化]
首先显然相当于把序列划分成若干段的方案
重要结论是对于划分的每一段, 两端点贝壳大小相同, 否则把它划分到其他部分或单独成段一定不劣.
所以我们可以只考虑相同颜色的转移, 令 $f_i$ 表示考虑前i个的答案, $cnt_i$ 表示第i个贝壳的大小包含它的前缀中的出现次数, $size_i$ 表示它的大小, 则转移可以枚举前面的j, 就是
$$
\begin{aligned}
f_i&=f_{j-1}+size_i\times(cnt_i-cnt_j+1)^2\\
&=f_{j-1}+size_i\times cnt_i^2+size_i\times cnt_j^2+size_i\\
&\ \ \ \ -2size_i\times cnt_i\times cnt_j - 2size_i\times cnt_j+2size_i\times cnt_i\\
\end{aligned}\\
$$
发现可以斜率优化, 所以整理式子:
$$
\begin{aligned}
(2size_i\times cnt_i)\times (cnt_j) \\
+(f_i-size_i\times cnt_i^2-size_i-2size_i\times cnt_i) \\
=f_{j-1}+size_j\times cnt_j^2-2size_j\times cnt_j
\end{aligned}\\
$$
这里用到刚才结论 $size_i=size_j$ , 式子中的四个括号分别是直线的 $k$ , $x$ , $b$ , $y$ .
注意式子对颜色不相同的情况是不成立且不保证答案更小的, 所以要对每种颜色单独维护凸包. 右发现对于同种颜色, $cnt_j$ 和 $2size_i\times cnt_j$ 单调增, 所以用单调栈维护上凸壳即可.
这类先分类再每一类分别进行斜率优化的dp值得思考
P3515 [POI2011]Lightning Conductor [dp] [决策单调性]
每个点 $i$ 对后面的贡献函数是 $\sqrt x$ 的平移, 发现一旦一个决策点的答案到另一个之上, 另一个再也没有机会反超, 所以这个题满足决策单调性.
于是有几种可以的方法利用决策单调性:
分治法: 设当前区间为 $[l, r]$ , 可能的决策在 $[pl, pr]$ , 每次扫一遍算出序列上mid的答案, 则 $[l, mid-1]$ 中决策点在 $[pl, p]$ 中 $[mid+1, r]$ 中决策点在 $[p, pr]$ 中, 可以递归处理
单调队列或栈, 此题为单调队列: 用容器存储三元组 $(l, r, p)$ 表示以p为最有决策点的区间为 $[l, r]$ , 每次加入一个节点时, 如果它最后也不优秀就不用管, 否则二分出它和队尾的决策点切换的分界点 $k$ , 即它在 $[k, n]$ 更优秀而队尾在 $[l, k]$ 更优秀, 把原本队尾的区间修改并把它push进去
SMAWK: to do
等我先学会了
分治法适用于离线决策单调性, 即 $f_i$ 的计算不依赖 $f_{[1, n]}$ 的答案, 而单调队列或栈的方法适用于可以快速计算在某个决策点下的答案的情况.
这种相同凸函数的平移, 常常存在决策单调性, 还有常见的 $y=\max{(a(x-b), c)}$ 和 $y=ax^2+bx+c$ , 其中要求所有a均相同, b单调(不单调可能也行? )
P2497 基站建设, P4655 Build Bridges [斜率优化] [dp] [李超树] [cdq分治]
方程过于模板了不放了.
推出方程后可以斜率优化, 没什么单调性所以用李超树或cdq或平衡树或二进制分组维护斜率优化dp, 基站建设注意第一步要初中几何一下.
P4027 [NOI2007] 货币兑换 [dp] [斜率优化] [李超树] [cdq分治]
设 $f_i$ 表示第i天能拥有多少钱(在把所有券都卖光的情况), 转移就是考虑它能卖的券是之前的哪一天买的, 但这题给的比较麻烦, 首先要做一些转换, 设 $a_i, b_i, c_i, d_i, r_i$ 分别为两种券的钱数, 两种券的数量和题目中的 $Rate_i$ , 列出方程:
$$
\begin{cases}
a_ic_i+b_id_i=f_i\\
\frac {c_i} {d_i}=r_i
\end{cases}
$$
解出来得到:
$$
\begin{cases}
c_i=\frac{f_ir_i}{r_ia_i+b_i}\\
d_i=\frac{f_i}{r_ia_i+b_i}
\end{cases}
$$
于是方程就是:
$$
\begin{aligned}
f_i&=c_ja_i+d_jb_i\\
\frac {f_i}{b_i}&=c_j\frac {a_i}{b_i}+d_j\\
\end{aligned}
$$
现在就已经是斜率优化的形式了, 对于这种没有单调性的题目, 常见做法是cdq, 李超树和平衡树维护, 个人感觉李超树是最简单好用的. 复杂度 $O(n \log n)$
实现细节: 注意这里李超线段树的下标域是 $[1, 10]$ 的有理数, 可以先把所有 $\frac {a}{b}$ 离散化, 加速并不用卡精度.
HDU4991 Ordered Subsequence [dp] [线段树] [树状数组]
真正的线段树树状数组优化dp模板, 然而我是先做的后面那个基站选址, 但它更模板所以被我放到前面
首先暴力式子应该还挺显然的, 设 $f_{i, j}$ 表示以第 $i$ 个结尾, 长度为 $j$ 的LIS长度, 式子就是
$$
f_{i, j}=\sum_{k < i, a_k < a_i} {f_{k, j-1} }
$$
初始条件 $f_{i, 1}=1$
然后和基站选址类似的是它的 $m$ 最大100, 可以承受 $O(nm\log n)$ , 所以把j改为在外层枚举, 考虑优化式子
$$
f_i=\sum_{k < i, a_k < a_i} f_k
$$
然后就是简单二维数点求和, 这里可以线段树也可以离散化后树状数组上
P2605 基站选址 [dp] [线段树]
首先要推出暴力dp式子, 设 $f_{i, j}$ 表示考虑前i个村庄, 在第i个村庄建了第j个基站的花费, 这里不考虑i到n部分的赔偿, 记 $i$ 到 $j$ 部分的补偿为 $cost(i, j)$ , 第i个村庄建立基站的花费为 $c_i$ , 则转移就是看上一个基站在哪:
$$
f_{i, j}=\min_l {f_{l, j-1}+cost(l, i)} + c_i
$$
暴力转移为 $O(n^2k)$ , 发现这里n很大而j不大, 所以可以只优化i的转移, 外层暴力枚举j, 另外发现式子只和 $j-1$ 有关, 可以滚动掉一维空间, 式子就成了
$$
f_{i}=\min_l {f_{k}+cost(k, i)} + c_i
$$
困难在于计算 $cost(k, i)$ , 正向计算在 $f_i$ 时哪些村庄在选 $k$ 时要赔偿较为困难, 可以反过来想对于每个村庄选择那些 $k$ 需要时需要赔偿这个村庄, 首先可以预处理对于每个村庄向左右最远到哪里建设不需要赔偿, 分别记为 $l_k$ , $r_k$ , 则对于一个村庄, 仅当处理到的 $i>r_k$ 且选择的 $k < l_k$ 时需要赔偿, 所以可以数据结构维护 $f_{k}+cost(k, i)$ , 则转移时就是查询 $[1, i-1]$ 的区间最小值, 每次处理完 $i$ 后, 对于所有 ${r_i=l_k}$ 的村庄, 如果k在 $[1, r_i]$ 中需要赔偿, 所以给这个区间加上它的赔偿费用, 由于是区间加, 区间最小值, 可以使用线段树完成
第一次做线段树优化dp, 所以开始找其他类似题目. . .
CF675E Trains and Statistic [dp] [贪心] [RMQ]
然后发现被骗了, 这题并不需要线段树优化dp, 因为这就一个RMQ根本不用线段树. . .
首先发现如果我们能到达 $i$ , 则一定能到达任意 $j s. t. \ j < i$ , 因为我们可以在任意时刻中途下车
由于上面的性质, 可以对每个i找出 $\max_j{a_j}\ s. t. j\in[i, a_i]$ , 这个 $j$ 的意义是如果我们要走的这次到不了, 那么应该走到 $j$ , 记它为 $next_i$
这个可以用静态RMQ直接求, 我觉得猫树最可爱容易理解而好用
要求的这个答案应该可以想到计算对于每一个i的 $\sum_j {\operatorname{dis}(i, j)}$ , 记为 $f_i$ , 要想办法求 $f_i$ , 你可以画出下面的示意图
1 | ------------------------------------------- |
发现对于 $f_i$ 相比 $f_{nxt_i}$ 有两段距离增加, 一段是 $[i+1, nxt_i]$ , 是原来不需要走的, 另一段是 $[a_i+1, n]$ , 需要先用一步走到 $nxt[i]$ 再继续走, 所以转移为
$$
f_i=f_{nxt_i} + (n - a_i) + (nxt_i - i)
$$
倒序递推即可
CF946G Almost Increasing Array [dp] [树状数组]
我认为这个也不是严格的线段树优化dp, 它只是在值域上树状数组维护最大值而已
首先套路的可以把每个数减去他们的下标, 把问题转化为非严格递增, 这样转化的好处是, 我们可以任意在两个数中间添加一个值, 而原来如果这两个数相邻我们不能添加小数.
然后可以反向思考能留下哪些, 发现留下的就是已有的非严格LIS, 所以我们要在可以删一个数的前提下求这个LIS
思考删除这个数造成哪些影响, 发现对于它后面的每个数, 删去它后下标前进了一个, 也就是变大了一个
于是在原有LIS的dp上进行修改, 设 $f_{i, 0/1}$ 表示考虑前i个, 是否已经删除过一个数, 则转移有三种:
- 尚未删除任何数: $f_{i, 0}=\max {f_{j, 0} } + 1, \ s. t. \ j < i, a_j\le a_i$
- 已经删除过一个数: $f_{i, 1}=\max {f_{j, 1} } + 1, \ s. t. \ j < i, a_j\le a_i$
- 现在正要删一个数, 仍然考虑子序列里上一个数是谁, 因为这个与上一个间删除了一个数, 所以这个数的值变大了1, 所以式子为 $f_{i, 1}=\max {f_{j, 0} } + 1, \ s. t. \ j < i, a_j\le a_i+1$
然后用树状数组记录值域上前缀max即可
CF739E Gosha is hunting [dp] [wqs二分] [二维wqs二分] [费用流]
这题可以从费用流考虑, 从源点连到左边一排点表示宝可梦, 边权为2, 费用为0, 从宝可梦连向右边两个点表示两种球, 这一步边权为1, 费用为用这个球能捉住的概率, 从右边的球向汇点连边, 容量 inf , 边权为0, 但是发现同时对一个宝可梦使用两种球时还要减去两个同时发生的概率(独立事件), 所以把源点到宝可梦的每条边拆成两个, 一个容量为1边权为0, 另一个容量为1边权为两概率相乘, 就有了一个费用流做法, 已经可以通过.
有了费用流能说明关于流量(使用球总个数)有凸性, 所以可以进行二分一种球的使用数量把朴素的 $O(n^3)$ dp优化成 $O(n^2)$ 的, 然后又可以二分另一种的优化成 $O(n \log^2 n)$ 的, 可以更稳通过此题
然而这个题直接这么两重wqs二分是假的, 一重wqs二分时有两种写法, 分别找到:
- 最大的斜率满足使用球数小于要求的
- 最小的斜率满足使用球数大于要求的
这两个的选择要和二分时的 check 函数相对应, 比如题目 P4694 Raper 中有些买光盘决策收益为0, 这类光盘如果不购买则使用个数较少, 购买则个数较多, 分别对应前面两种情况, 所以二分时是要有这种对应的, 而当拓展到二维时, 就需要我们找到两者都最少的, 这里以谁为第一关键字似乎是个问题. 目前有两种解法:
- 给每个数再加一个很小的随机权值, 直接避免出现这类二分遇到直线和平面的情况
- 二分过程中mid不再等于l+r, 而是等于两者之间的一个随机位置, 这个样跑一次成功概率较小, 需要重复多次选一个答案最小的(来自机房大佬qyc), 注意这种方法保证正确性的同时会TLE并不能通过
所以还是很玄, 我再思考能不能在dp决策过程中使某个最小但仍然很困难. 有人有好办法了告诉我.
P2619 Tree I [wqs二分] [最小生成树]
是时候来点清新WQS二分了
凸性的证明是困难的(目前还没看到), 先尽量感性理解, 就是考虑总边数一定的情况下, 使用白边少时会需要用一些不优点黑边顶上, 多时要必须选一些不优的白边, 说明它是有一个谷的. . . 然后就不会了
在通过打表, 瞎猜等方式得到凸性之后就很简单了, 二分给每个白色边加上一个权值C(给所有黑色边也是一样), 再按照新的权值跑Kruskal, 统计有多少条白边去调整二分区间即可.
P4983 忘情 [wqs二分] [斜率优化]
中规中矩的wqs二分
首先把给的式子拆开后发现npy很善良其实就是 $(sum+1)^2$ , 那么不考虑段数情况下就是简单斜率优化, 考虑段数的情况就再使用wqs二分, 给每一段一个附加代价二分
这个题凸性证明由qyc给出, 先考虑原始dp方程, 即 $f_{i, j}$ 表示前 $i$ 个划分 $j$ 段, 则有
$$
f_{i, j}=\min(f_{k, j-1}+(sum_i-sum_k)^2)
$$
对于类似 $f_{i, j}=\min(f_{k, j-1}+w(k, i))$ 这种方程, 或者更泛化一些, 对于在一个 DAG 上走k步从1走到n的最短路问题, 如果边权满足四边形不等式, 那么答案是关于k的凸函数
然后再把sum变成前缀和形式拆开, 平方也拆开, 就有了一个显然斜率优化, 其中k和x都是单增多, 单调队列即可
几个关于决策单调性/凸性结论
wqs二分实现难点
为了统一, 把wqs二分中二分的值为 $C$ , 通过二分改变的题目要求的值为 $K$ , 答案为 $A$
问题主要是二分时二分区间变化的选择要与check函数相对应, 比如如果check函数选择的是给定 $C$ 下 $K$ 最小的, 那么二分时就应二分最大的小于等于 $K$ 的, 否则如果是给定 $C$ 下 $K$ 最大的, 则二分最小的大于等于 $K$ 的, 是一个十分重要的细节, 例子:
- Tree I中, 出现黑色白色边权值相同时, 如果选择白色边, 则相当于选择 $K$ 最小的, 我们要二分出最大的小于 $K$ 的
- 忘情中, 对于斜率优化中是否取等, 不取等相当于选择 $K$ 最小的, 要二分出最大都满足条件段数的
- Gosha is hunting中, 对于遇到使用不使用球期望相同的情况, 选择不使用相当于 $K$ 最小, 要二分最大的球数小于 $K$ 的
- Raper中对于获益为0的光盘是否要买也是相同的
凸性证明
- 费用流问题, 费用是关于流量的凸函数
- 忘情中写的对于在一个 DAG 上走k步从1走到n的最短路问题, 如果边权满足四边形不等式, 那么答案是关于k的凸函数
- 打表出奇迹
- 四边形不等式的一个思考方式, 首先只要证明 $f(l, r)+f(l-1, r+1)$ 与 $f(l-1, r)+f(l, r+1)$ 的关系, 其次一个常用方法是, 因为问题常常是每个位置有一个贡献, 这个贡献和区间的其他位置有关(而不是直接跟区间), 那就仅考虑 $l-1$ 位置从区间 $[l-1, r+1]$ 移动到 $[l, r]$ 的贡献
P4481 BJWC2018 序列合并 [dp] [区间dp]
qyc说这是他童年阴影题, 然而他只用了两分钟就秒了
首先它长的这么像石子合并, 让人想到一个区间dp, 于是一种做法是记 $f_{l, r}$ 表示区间 $[l, r]$ 合并成一个的代价, 转移时就相当于要把这一段划分成k段, 所以可以用一个 $O(n^3)$ 的dp, 然后会得到一个五次方TLE做法
然后简单想一下发现对每个l向右跑一遍就能得到所有的r, 就成了四次方, 卡卡常就过了
不过还有一种长的更像区间dp的理解, 设 $f_{l, r, k}$ 表示把区间 $[l, r]$ 合并成k段, $g_{l, r}$ 表示这一段合并成一段的答案, 则方程就是
$$
\begin{aligned}
f_{l, r, k}&=g_{l, p}+f_{p+1, r, k-1} \ s. t. \ , k\ge 2 \
g_{l, r}&=\min f_{l, r, k} \ s. t. \ k \in [L, R] \
f_{l, r, 1}&=g_{l, r}
\end{aligned}
$$
P4767 邮局
[结论] : 对于一个区间中的一个邮局, 若区间长度为奇数则邮局建在中位数上, 偶数则建在中间两个数的任意一个上小学奥数经典
于是就可以考虑把原序列分成 $P$ 个区间, 每个区间里放一个邮局, 所以设 $f_{i, j}$ 表示前 $i$ 个村庄分了 $j$ 段(也就是建了 $j$ 个邮局)的代价, 转移即
$$
f_{i, j}=\min f_{k, j-1}+cost(k+1, i)
$$
其中 $cost(l, r)$ 表示在区间 $[l, r]$ 中建立一个邮局的最小代价, 这个代价可以 $n^2$ 递推, 但我认为这种方法更好: 考虑知道中位数后, 距离就是对中位数两边的位置一一匹配后匹配位置间距离的和, 如图:
! [示意图](https: //raw. githubusercontent. com/FireInIceCode/imgs/main/imgs/202205291347317.png)
可以结合图理解, 蓝色点表示村庄, 红色即表示一对位置的匹配, 总代价就是所有匹配点之间距离的和, 也就是右边的每个点位置分别减去左边每个点位置之和, 可以先处理一个前缀和之后 $O(1)$ , 用这个式子去做复杂度就成了 $O(n^2p)$ , 由于奇数偶数时的差异, 式子是
$$
cost(l, r)=(sum_r-sum_{\lfloor \frac {l+r}{2} \rfloor})-(sum_{\lfloor \frac {l+r-1}{2} \rfloor}-sum_{l-1})
$$
接下来遍历能进行的优化策略, 式子有与 $k$ , $i$ 均有关的项废掉了单调队列, 这个项里与 $i$ , $k$ 相关的东西在下标里废掉了斜率优化, 只剩下wqs二分和决策单调性, 由于我在上面wqs二分总结的结论, 问题就转化为证明 $cost$ 满足四边形不等式
抛开式子会发现包含单调性的显然, 在原有区间上增加新村庄代价一定不会降低
对于四边形不等式的证明复杂一些, 首先因为 $x$ 单调递增, 所以 $sum$ 是凸函数, 此外在证明 $cost_{l, r}+cost_{l+1, r-1}\ge cost_{l+1, r}+cost_{l, r-1}$ 时会消掉所有 $sum_r$ 和 $sum_{l-1}$ , 剩下的可以套用琴森不等式证明
这样同时证明了四边形不等式和凸性, 单用四边形不等式可达到 $n^2$ 通过, 使用 wqs 二分和决策单调性可以达到 $n \log n\log v$
汪娟的一套dp题
[BJOI2019]光线
若干层玻璃叠在一起, 一束光照到玻璃上时会有 $\dfrac{a}{100}$ 的光透过而 $\dfrac{b}{100}$ 的光反射. 不保证 $a+b=100$ 求从一边射入1, 从另一边射出多少.
$n\le t\times 10^5$
$f_{i, 0/1, 0/1}$ 表示第 $i$ 个玻璃从前/后方向射进去光从前/后出来的大小是进去的多少倍即可.
[SCOI2009]粉刷匠
$n$ 条木板, 每条有 $m$ 个格子, 要被涂成0/1, 每次只能选择一个木板上连续的一段涂成0/1, 每个格子只能被涂一次, 只能粉刷 $t$ 次, 求能对多少.
$n, m\le 50, t\le 2500$
考虑一条木板上的情况, 显然设 $f_{i, j}$ 表示前 $i$ 个涂了 $j$ 次的最多个数即可.
那么现在有多条木板, 做一个泛化背包合并即可. 复杂度 $nm^2$ 之类的
P1373 小a和uim之大逃离
$n\times m$ 的网格, 每个格子上有一个数, 从任意格子开始任意格子结束, 每次向右或向下走一步. 手上有两个数初始都为 $0$ , 站在走到的第奇数个格子时(包括开始和结束格子)让第一个数加上网格上的数, 否则让第二个数加上. 每次加上之后都与 $k+1$ 取模. 求由多少种方案结束的时候两个数相同.
$n, m\le 800, k\le 15$ .
如果从 $(1, 1)$ 起点是简单的, 设 $f_{i, j, k, l}$ 表示走到 $(i, j)$ 左右手分别是 $k$ , $l$ 的方案数, 复杂度 $n^2k^2$ .
可以进一步优化, 由于我们只关心是否相同, 可以用emiya家今天的饭的方法只记录差, 去掉一个 $k$
从任意位置结束只要求所有位置的dp值累加, 从任意位置开始只要每个位置转移的时候都额外算上这个位置的. 同时注意因为起始位置不同还要记录一维 $0/1$ 表示这一步加给哪个数.
杜赢的blog上的P8580 [CoE R5] 罚球
有 $n$ 个人在玩罚球游戏, 游戏规则如下:
- 每个人编号为 $1, 2, \dots, n$ , 最开始由 $1$ 号罚球, 接下来让下一个没有出局的人罚球. 特殊地, $n$ 号的下一个是 $1$ 号.
- 如果罚球者没有碰到篮板, 那么直接出局.
- 如果罚球者碰到篮板但没有进球, 那么如果上一个人进球了, 这个人就会出局, 否则不会出局.
- 游戏结束的条件是最后只剩下一个人.
注意最开始的那个人碰到篮板但没有进球不出局.
这 $n$ 个人中, 第 $i$ 个人碰不到篮板的概率为 $\dfrac{a_i}{1000}$ , 碰到篮板但没有进球的概率为 $\dfrac{b_i}{1000}$ , 求游戏结束时所有人总共罚球数量的期望值.
$n\le 18$
$n$ 很小, 直接状压, 设 $f_{S, i, 0/1}$ 表示还活着的是 $S$ , 然后现在是 $i$ 投球, 上一个人是否投中情况下期望值. 设 $next$ 表示 $i$ 之后下一个投球的人, 按照期望反向递推的套路写, 显然有:
$$
f_{S, i, 0}=a_if_{S/i, nxt, 0}+b_if_{S, nxt, 0}+(1-a_i-b_i)f_{S, nxt, 1}+1\
f_{S, i, 1}=a_if_{S/i, nxt, 0}+b_if_{S/i, nxt, 0}+(1-a_i-b_i)f_{S, nxt, 1}+1\
f_{ {i}, i, 0/1}=0
$$
显然转移成环, 考虑分析:
首先, 环只有在同一个 $S$ 内部出现, $S$ 间不会有, 那么上来先按 $\vert S\vert$ 排序按顺序转移.
其次, 对于同一个 $S$ 内的, 发现 $f_{S, i, 1}$ 只在内部有环, 确定了 $f_{S, i, 1}$ 后 $f_{S, i, 0}$ 也只在内部有环, 考虑高消, 发现列出来每个方程都只有两个变量还是长成循环的样子, 用主元高消消元, 两个复杂度都是 $\vert S \vert$ 的.
主元高消指的是用一个变量表示其他变量(这也配起个名///cf), 这里发现只要确定一个就能表示所有变量所以线性.
CFdp乱做
是选择通过人数降序, 难度2600, 标签dp.
带有combination/greedy的可能没有, 被收录到数数/贪心中.
CF1431G
给一个 $n$ 个数的集合, 每轮A选一个不是最大值的数删掉, 然后B选一个比A选的大的数删掉, 并给得分累加两数的差, A希望最大得分, B希望最小得分, 求最后得分.
$n\le 400, k\le \lfloor \dfrac{n}{2} \rfloor$
首先发现, 任意情况B选的一定是A选的后继, 只要B按照这个选就一定是最小的, 即使 $[1, 2, 3, 4]$ 中A选 $2$ , B选 $3$ 后下一次强制 $1$ 和 $4$ 也不比 $(3-1)+ (4-2)$ 更劣, 于是B的方案就是确定了. 所以实际上选出的是若干连续段, 对于一个连续段 $[l, l+2x-1]$ , 其得分为 $\sum_{i=l}^{l+x-1}+ a_i-\sum_{i=l+x}^{l+2x-1} a_i$
接下来就考虑A要如何选, 考虑dp, 设 $f_{i, j}$ 表示前 $i$ 个元素中, 两人选了 $2j$ 个数的情况下的得分, 转移是这个数不选或枚举最后选的一段, 复杂度 $nk^2$
注意这题只能Kotlin交哦.
CF1740F Conditional Mix
给定 $n$ 个数, 每次可以把两个不交集合并起来, 求任意次合并后集合大小组成的可重集的方案数. 膜998244353.
$n\le 2000$
值排序, 从小往大扫的好处是对不用考虑交.
$f_{i, j}$ 表示前 $i$ 个值, 组成 $j$ 个集合, 加入这一层的时候可以选择新开若干层或者加到已有的里面去. 但是 $S$ 只关心大小就死了.
考虑一个多重集 $S$ 合法当且仅当其和为 $n$ 并且降序排列时 $\sum_{i\in[1, k]} S_i\le \sum_{i\in [1, n]} \min(k, cnt_i)$ . $cnt_i$ 为数 $i$ 的出现次数.
感觉必要性比较显然(前 $k$ 个集合最多每个选 $1\ldots n$ 各一个), 充分性就直接体会把可以合并的拆开肯定是没问题的.
于是直接dp, 设 $f_{i, sum, last}$ 表示选了前 $i$ 个, 总和是 $sum$ , 最后一个是 $last$ 的即可. 复杂度 $n^3$ .
进一步分析, 考虑 $n\ge last\times i$ , 于是 $last$ 的取值是自然对数, 总复杂度就是 $n^2\log n$ 了.
321E Ciel and Gondolas
给定 $a_n$ , 要求你把它分成 $k$ 组, 若 $a_i$ 和 $a_j$ 分为一组会产生 $w_{i, j}$ 的代价, 最小化代价和.
$n\le 4000, k\le 800, w_{i, j}\ge 0$
看一看发现是简单题, 显然 $cost(l, r)$ 是满足四边形不等式, 直接分治就结束了.
CF631E Product Sum
给定序列 $a_n$ , 移动一个数最大化 $\sum i\times a_i$
$n\le 2\times 10^5$
可以先假定是往后移动, 再反过来做一遍即可.
考虑 $f_i$ 表示从某个位置插入到 $i$ 后面的答案最大值, 那么就是
$$
\max_j suf_{i+1}+pre_{i}-a_j j+a_j(i+1)+sum_i-sum_j
$$
直接斜率优化.
CF662C Binary Table
给定 $n\times m$ 01矩阵, 每次选择一行或一列翻转01, 求翻转任意次后1的个数的最小值.
$n\le 20, m\le 10^5$
对每一种行的是否翻转情况, 列是否翻转是确定的. 只是不能直接计算.
猜到是FWT, 但不会. 做法是, 设 $a_i$ 表示 $i$ 这种状态的出现次数, $b_i$ 表示二进制数 $i$ 的0/1个数的较小值, 那么当行的状态为 $S$ 的时候答案就是
$$
f_S=\sum_T a_T\cdot b_{T\operatorname{xor}S}\
f_{S \operatorname{xor} T}=a_S\cdot b_T
$$
于是直接FWT-XOR即可.
CF1208F Bits And Pieces
给定 $d_n$ , 求 $i<j<k$ 最大化 $d_i\operatorname{or}(d_j\operatorname{and}d_k)$
$n\le 10^6$
又是FWT.
考虑从高到低贪心, 那么要确定是否有三个数这样运算起来包含一个前缀.
先解决后两个的与运算, 做一遍高维后缀和得到包含每个位置下标的最大值, 次大值即可.
然后再解决或, 做一遍高维前缀和得到每个位置被贡献的最小位置即可.
然后就简单贪心.
CF1344C Quantifier Question
给定 $n$ 个变量 $x_n$ 和 $m$ 个关系, $m$ 个关系每个形如 $x_i<> x_j$ , 求序列 $q_n, q_i\in{\exists, \forall}$ , 使得拼出来 $q_i x_i$ 满足这 $m$ 个关系. 求最大的任意的个数和一个 $q$ 的方案, 或判断无解
我天什么烂题面, 举个例子:
假设 $n=2, m=1$ , 关系是 $x_1<x_2$ , 那么可以 $\forall x_1, \exists x_2, x_1<x_2$ , 不能 $\exists x_1, \forall x_2, x_1<x_2$ 或两个都是 $\forall$ , 所以最大个数是1.
$n, m\le 2\times 10^5$
考虑建一个图, 若要求 $x_1<x_2$ 则 $x_1\to x_2$ , 如果有环肯定无解, 注意到序列维和图上都是有意义的. 考虑若 $i<j$ 且 $x_i\to x_j$ , 那么显然 $x_j$ 不能是任意, 如果有 $i<j$ 且 $x_j\to x_i$ 同理, 于是一个点可以选当且仅当没有一个在它之前的点与它连通. 注意到有向图所以不能直接搞连通块, 而是类似dp的做法: $f_u$ 表示能走到 $u$ 的最小的, 那么 $f_u=\min { u, \min f_v}\ s. t. \ v\to u$ 即可. 反着也是类似.
CF6D. Lizards and Basements 2
给定序列 $a_n$ , 每次可以选定 $i\in (1, n)$ , 对 $a_i$ 减去 $c_1$ , 对相邻的两个减去 $c_2$ , 问几次全小于0.
$n\le 10, 1\le c_2<c_1\le 10, a_i\le 15$
不是, 为啥数据范围有点小啊?
显然顺序无所谓, 于是 $f_{i, j}$ 表示前 $i$ 个位置, 第 $i+1$ 个位置减去了 $j$ 的代价, 那么转移到 $f_{i+1, k}$ 的时候只要枚举 $i+1$ 上被减了几下即可. 但这个是不对的, 发现可能干 $i+1$ 的时候 $i$ 死了, 所以再多记一维即可.
CF750E New Year and Old Subsequence
给定 $a_n$ , $q$ 次询问给定区间 $l, r$ , 删去最少的使得其没有子序列 $\texttt{2016}$ 而有子序列 $\texttt{2017}$
$n\le 2\times 10^5$
画出识别2016, 2017的自动机
然后设 $f_{i, j}$ 表示前 $i$ 个自负, 走到节点 $j$ 至少要删多少, 用静态ddp做就好了.
CF1363F Rotating Substrings
给定 $s_n, t_n$ , 每次可以选择 $s_{l\ldots r}\to s_{r, l, l+1, \ldots r-1}$ , 求最少次数让两者相等.
$n\le 2000$
把循环移位操作看成插入, 就不考虑除了 $r$ 以外字符的影响了.
于是 $f_{i, j}$ 表示前 $i$ 个字符相等, 已经插入 $j$ 个字符的最小代价, 那么现在让 $i$ 这一位相等, 发现根本不会. 因为后面可能有若干字符跑到前面去, $s_{1 \ldots i}$ 不会和 $t_{1\ldots i}$ 相等, 所以改为 $f_{i, j}$ 表示 $s_{1\ldots i}=t_{1\ldots j}$ 的最小代价.
可能的转移包括:
- $s_i=t_j$ , $f_{i, j}=f_{i-1, j-1}$
- $s_i$ 需要被插入到前面去, $f_{i, j}=f_{i-1, j}+1$
- $s_i$ 从后面被插入过来, $f_{i, j}=f_{i, j-1}$
取个 $\min$ 即可.
CF650D Zip-line
给定 $a_n$ 和 $m$ 个操作 $x_i, v_i$ , 表示把 $x_i$ 改成 $v_i$ , 对每个操作求出操作后的LIS, 操作独立.
$n, m\le 4\times 10^5$
是修改一次后的LIS. LIS分为不跨过 $i$ 的, 当前包含 $i$ 的, 将来包含 $i$ 的三种, 第一种显然直接解决.
考虑当前包含 $i$ 的影响, 只要求出 $f_i$ 和 $g_i$ 分别表示 $i$ 往前, 往后的LIS长度. 删掉 $i$ 就是 $f_i+g_i-1$ .
最后一种是将来包含 $i$ 的, 新的 $f_i, g_i$ 的dp值就是直接矩形数点, 就做完了.
CF1554D You
给定 $T=Tree(n)$ , 生成 $a_n$ 的过程是每次选择一个未被标记的点 $u$ , $a_u$ 为与 $u$ 相邻的点未被标记的个数, 然后将它标记, 求 $T$ 生成的排列中 $\gcd=k$ 的数量
膜 $998244353$ , $n\le 10^5$
本质是给边定向, $a_u$ 是点 $u$ 的入度.
那么任意两种不同定向方式 $a_u$ 是否可能相同? 你感觉一下发现只有有环才有可能, 所以合法的 $a$ 到定向方式是双射.
考虑若 $a$ 可以得到, 一定要满足 $\sum a_i=n-1, a_i<d_i$ , 显然不充分.
不会凑, 那只好从树上看定向方式, 设 $f_{u, v, 0/1}$ 表示子树内和 $u$ 的父边所有定向方式中, 父边朝外/内形成的 $gcd$ 为 $v$ 的方案数, 每次转移考虑父边的方向. 似乎是可以的. $u$ 取值范围只有 $\log$ . 转移的时候就先合并子树内的方案, $g_{i, j}$ 表示 $u$ 度数为 $i$ , 当前 $gcd$ 为 $j$ 的方案数, 加入一个子树时是gcd卷积, 最后复杂度应该是 $n\log n\log\log n$ 吧.
看题解, 原来 $k>1$ 的的时候方案最大是1///kx, $k=1$ 的时候减去大于1的///kx
考虑如何判定大于1的即可, 首先所有叶子边都是内向(不能有入度是1), 然后叶子全删了到下一层, 这样每次定向叶子即可. 原来我才是智障啊.
CF755F PolandBall and Gifts
给定 $p_n$ , 点 $u$ 是好的当且仅当点 $u$ 不是坏的且 $p_v=u$ 的点 $v$ 也不是坏的, 现在已知有 $k$ 个点是坏的, 求此时最少/最多有多少点不是好的.
$n\le 10^6$
看到排列想形成了若干环.
考虑根据这个定义一个点坏了其实是坏了它和它连向的点, 所以是每次干掉一条边, 求答案.
那么对于最大值, 一定要先让它每次干掉两个点, 最后干长奇数的环剩下的一个点即可. 对于最小值, 最好的方式显然是干满若干环, 这样平均每次干都是1的贡献.
于是最大值可以直接统计奇环个数, 最小值要找若干环加起来是环, 所以就成了多重背包.
$10^6$ 卷起来上过不了了, 但显然不同的环长只有根号个, 就多重背包直接结束了.
CF258D Little Elephant and Broken Sorting
给定排列 $p_n$ , $m$ 次操作交换 $p_i, p_j$ , 每一个操作有0. 5概率执行, 求逆序对期望.
$n, m\le 1000$
交换和逆序对没有简单关系, 因为 $n\le 1000$ 考虑拆贡献.
于是求每一对数 $i, j, p_i<p_j$ 的概率. 设这个为 $f_{i, j}$
初始状态应该是 $f_{i, j}=[p_i>p_j]$ . 每次进来一个操作 $a, b$ , 考虑:
$$
f_{i, a}=\dfrac{1}{2}f_{i, a}+\dfrac{1}{2}f_{i, b}
f_{a, b}=f_{b, a}=\dfrac{1}{2}
$$
最后求个和就做完了.
CF1223F Stack Exterminable Arrays
对于一个序列, 定义其可消除当且仅当从头开始扫它, 若栈顶等于当前元素就弹, 否则就入栈, 最后栈是空的.
给定 $a_n$ , 求有多少子区间是可消除的.
$n\le 3\times 10^5$
从前往后扫, 一个序列可以消除当且仅当其第一个元素入栈前和最后一个元素出栈后栈相等.
直接hash变成求相等元素对数.
就是dwtoj 括号序列加强版
CF1389F Bicolored Segments
给定 $n$ 条线段 $[l_i, r_i]$ , 每个线段有颜色 $t_i$ , 要选择最多的线段满足没有两个颜色不同的线段有交集(包括包含)
$n\le 2\times 10^5$
考虑结束时, 一定是若干段颜色相同的, 之间没有交.
于是设 $f_{i, 0/1}$ 表示前 $i$ 个位置, 最后一段是 $0/1$ , 就要找 $f_{k, 0/1}+w(k, i)$ 最大, 然后发现是线段树优化dp, 移动到一条线的右端点就区间加即可.
CF1566F Points Movement
数轴上有 $n$ 个点 $a_i$ , $m$ 个区间 $[l_i, r_i]$ , 你可以任意次花费1的代价将一个点向左向右移动1, 求保证每个区间都有过某个时刻含有至少一个点的最小代价.
$n\le 2\times 10^5, \vert a_i\vert, \vert l_i\vert, \vert r_i\vert \le 10^9$
读错题了. ///kk
那么先删掉显然多余的区间(已经有点的, 包含另一区间的). 可以把区间, 点排序.
于是现在是若干段点和区间, 每个点一定只会折返一次并且不会跨过起点.
于是现在每个点走过包含自己的一个区间. 如果一个点跑过一段区间编号 $[i, j]$ , 那么一定是走过 $[r_i, l_j]$ , 代价是 $r_i-l_j+\min(x-r_i, x-l_j)$ .
于是考虑dp: $f_{i, j}$ 表示前 $i$ 个点干掉了前 $j$ 个区间的最小代价, 注意状态数线性因为每个点的区间不会越过相邻点, 于是只要考虑转移, 现在的情况是
$$
f_{i, j}=f_{i-1, k}+cost(k+1, j, i)
$$
$cost$ 是单增的, $f_{i-1, k}$ 是单减的, 二分就完了.
CF797F Mice and Holes
$n$ 个老鼠, $m$ 个洞, 告诉你他们的一维坐标和 $m$ 个洞的容量限制, 问最小总距离.
$n, m\le 5000$
模拟费用流!
(我感觉这题网络流直接冲)
可以dp. $f_{i, j}$ 表示前 $i$ 个老鼠, 进前 $j$ 个洞的最小总距离, 转移可以枚举这个洞装了几个老鼠, $f_{i, j}=f_{k, j-1}+cost(k+1, i, j)$ , $cost$ 是区间中的点到另一个点的最小距离, 直接前缀和, 于是单调队列优化, 于是做完了.
CF813D Two Melodies
给定 $a_n$ , 求找两个不交子序列使得长度和最大, 要求子序列满足相邻两个元素差为 $1$ 或膜 $7$ 同余.
$n\le 5000$
一个子序列很显然, 两个子序列设两维, $f_{i, j}$ 表示第一个子序列选到 $i$ , 第二个选到 $j$ . 因为影响一个序列后面能不能选的只有最后一个元素所以我们是正确的.
CF917D Stranger Tree
给定 $T=Tree(n)$ , 对每个 $k\in [0, n-1]$ , 求有多少 $T’=Tree(n)$ 与 $T$ 有恰好 $k$ 条边相同. 相同指边的两个顶点相同.
$n\le 100$
见到这种是不是应该立刻容斥, 钦定 $k$ 条边相同, 于是现在有 $n-k$ 个连通块, exCaylay说你要算 $\sum \prod siz$ , 注意选完这 $k$ 条边的连通块一定是树上的连通块, 所以就 $f_{i, j, k}$ 表示子树 $i$ 内选了 $j$ 个连通块, 连到 $i$ 上的这个里有 $k$ 个点. 复杂度 $n^4$ .
然后发现组合意义: $\prod siz$ 相当于每个连通块选一个点, 于是第三维改成 $0/1$ 表示是否已经选过, $j$ 一维合并的时候用树上背包的办法, 复杂度就 $n^2$ .
CF1051E Vasya and Big Integers
Vasya 有三个大数字 $a, l, r$ . 求把 $a$ 划分成连续的若干段使得每一段的数字大小在区间 $[l, r]$ 之内(注意是按照数字大小比较而非按字符串大小比较), 且不含前导零的方案总数. 由于答案可能很大, 只需输出答案对 $998244353$ 取模的结果.
$n\le 10^6$
首先地球人都知道的dp是 $f_{i}$ 表示前 $i$ 个, 想了想你觉得设后 $i$ 个更好, 此时满足条件的 $i$ 一定是一个区间.
那不就直接做了, 每次满足条件的一个区间, 区间长度与 $l, r$ 不同的可以直接搞掉, 现在还剩下判断相等的怎么弄, 可以二分/exkmp算一算lcp然后比较lcp的下一位即可.
CF441E Valera and Number
给定 $x$ , $k$ 次操作, 每次有 $p$ 概率乘 $2$ , 否则加 $1$ , 问最终 $x$ 二进制末尾0个数的期望.
s
$x\le 10^9, k\le 200$
考虑这个是左移和加一.
发现加一的影响相对有点小. 感觉可以设最后8位表示的数是 $x$ 之类的, 但一个全1段就死了, 那再记录一个从最后8位开始的1长度是不是就行了, 现在状态成了 $f_{i, j, k, l}$ 表示 $i$ 次操作, 最后8位是 $j$ , 从最后8位往上有 $k$ 个0, $l$ 个1.
你想了想, 发现 $k$ 和 $l$ 有一个一定是0, 所以就解决战斗了吧.
可以去杜赢那里看另外两个做法.
