Posts dp选做1 By Oscar
Post
Cancel

dp选做1 By Oscar

1528E

题意

输入 $n$ ,求有多少无标号有向树满足下列条件:

  1. 每个点入度+出度不超过3
  2. 任意两个点要么存在公共祖先,要么存在公共后代
  3. 直径为 $n$

$1\leq n\leq 10^6$

题解

性质:树的形态一定是先收缩至一条链再散开

如果有链部分,那么每个点度数不超过2,否则根(只有收缩部分则根看作收缩终点)度数不超过3,其余点度数不超过2

dp 求出深为 $n$ 的二叉树个数,再分类讨论+前缀和分别求出含链的和不含链的答案

后面是废话

具体来说令 $g[n]$ 代表深为 $n$ 的二叉树个数,$f[n]$ 代表根度数强制为2的深为 $n$ 的二叉树个数,$sg[n]$ 和 $sf[n]$ 分别是 $g[n]$ 和 $f[n]$ 的前缀和

那么 $g[n]=g[n-1]+f[n], f[n]=cal2(g[n-1])+g[n-1]*sg[n-2]$

其中 $g[n-1]$ 是一棵子树的情况, $cal2(g[n-1])$ 是两棵深度相同子树的情况,$g[n-1]*sg[n-2]$ 是两棵深度不同子树的情况

边界是 $g[0]=f[0]=1$ (单个点)

$cal2(x)=C_{x+1}^{2}$ 是去重用的,用来在一个大小为 $x$ 的集合中选出一个无序2元组

最终答案\(ans = 2*(cal3(g[n-1])+g[n-1]*cal2(sg[n-2])+cal2(g[n-1])*sg[n-2])\\+2*f[n]\\+ \sum_{L=0}^{n-1} f[L]*sf[n-L-1]\)

第一行是没有链,根有三个孩子的情况,第二行是没有链,根有两个孩子的情况,最后一行是有链的情况

$cal3(x)=C_{x+2}^{3}$ 也是去重用的,用来在一个大小为 $x$ 的集合中选出一个无序3元组

1527E

题意

长度为 $n$ 的序列,划分为 $k$ 段,最小化每段 $\sum_x last[x]-first[x]$ 之和

$1 \leq k \leq n \leq 35000,1\leq k \leq 100$

题解

$nk\log n$ 呗

所有前缀分 $i$ 段可以由所有前缀分 $i-1$ 段递推过来,拿个线段树维护一下

区间的贡献可以拆到每一个位置,从右往左扫的过程中把区间外元素的贡献丢掉(前缀减),更新线段树后区间求min,再更新答案

1525F

题意

$n$ 个点的DAG,$k$ 波怪物,第 $i$ 波怪物会选择 $i$ 条点不相交路径,如果覆盖整个图则 lose lose

第 $i$ 波之前可以砍断若干个点的所有入边或所有出边,消耗 $min(x_i*t,y_i)$ 代价( $t$ 是操作次数),目标是使得 $k$ 波都 win win

输出方案

$2\leq n \leq 50, 1\leq k \leq n-1$

题解

考虑网络流求最小路径覆盖的那个建图,发现是个二分图最小覆盖集问题,操作相当于删掉一个点

每次删掉一个最小覆盖集中的任意点可以使得需要的路径数 $+1$ ,因此可以直接 dp 出 $i$ 波之前总共做 $j$ 次操作的最小代价,限制是 $j\geq i+s-n+1$ ,$s$ 是初始最小覆盖集大小,方案的话可以记录每波操作了多少次

1523E

题意

$n$ 个灯排成一排,每次随机亮一个,直到存在连续 $k$ 个灯中亮了2个为止,求次数期望

$2\leq n,k \leq 10^5$ ,10组数据

题解

答案相当于对所有 $i$ ,次数 $\geq i$ 的概率之和,也就是 $i-1$ 次仍未满足条件的概率之和

$i$ 次时亮了 $i$ 盏灯,每两个之间至少 $k-1$ 盏没亮的,合法方案数是 $C_{n-(i-1)*(k-1)}^{i}$ ,总共方案数是 $C_{n}^{i}$ ,除一下求和就是答案

1523D

题意

$n$ 个人,每个人喜欢 $m$ 种货币种的至多 $p$ 种,求最大的货币子集使得至少一半的人(上取整)喜欢,输出方案

$1\leq n \leq 2\times 10^5,1\leq p \leq m \leq 60,1\leq p\leq 15$

题解

每次随机一个人$r$,最终答案有一半概率是这个人喜欢的货币子集

把每个人的货币和 $r$ 的货币求个交,值域只有32768,做个fwt求出每个子集是多少人的子集,用所有出现次数$>\lceil\frac n2\rceil$ 的子集更新答案,重复整个过程100次就完事了

This post is licensed under CC BY 4.0 by the author.
Contents

CF1479Div1

-

Loading comments from Disqus ...