【BZOJ2830/洛谷3830】随机树(动态规划)
题面
题解
先考虑第一问。
第一问的答案显然就是所有情况下所有点的深度的平均数。
考虑新加入的两个点，一定会删去某个叶子，然后新加入两个深度为原先叶子\(+1\)的点。
那么新加入的叶子的深度的期望是未加入之前的期望+1，假设\(f_i\)为\(i\)个点的期望。
那么\(f_i=(f_{i-1}*({i-1})-f_{i-1}+2*(f_{i-1}+1))/i=f_{i-1}+2/i\)
含义就是平均的深度乘上点的个数等于深度总和，减去删去的点的深度，加入两个新的深度为原先点\(+1\)的点。
考虑第二问
不难想到一个状态\(f[i][j]\)表示拥有\(i\)个节点，深度为\(j\)的概率。
那么答案就是\(\sum_{i=0}^nf[n][i]*i\)
这个转移不难，我们根节点已经固定，并且它一定拥有左右子树，我们转移的时候分开考虑左右子树，然后再在根节点的位置合并，即
\[f[i][max(k,l)+1]\rightarrow f[j][k]*f[i-j][l]/(i-1)
\]
除掉\(i-1\)的原因是一开始我们直接把左右儿子都当成整棵树来看，所以最终合并的时候要把总方案除掉。
还有一种做法，大同小异，然而复杂度更优秀。
设\(f[i][j]\)表示\(i\)个叶子的树，深度至少为\(j\)的概率。
转移和上面的东西类似，容斥去重。
\[f[i][j]=\frac{1}{i-1}\sum f[k][j-1]*1+f[i-k][j-1]*1-f[i][j-1]*f[i-k][j-1]
\]
答案是\(\sum f[n][i]\)
#include
#include
using namespace std;
int n,Q;
double ans,f[101][101];
int main()
{
cin>>Q>>n;
if(Q==1)
{
for(int i=2;i<=n;++i)
ans+=2.0/i;
printf(“%.6lf\n”,ans);
}
else
{
for(int i=1;i<=n;++i)f[i][0]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=i;++j)
for(int k=1;k
f[i][j]+=(f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1])/(i-1);
for(int i=1;i<=n;++i)ans+=f[n][i];
printf(“%.6lf\n”,ans);
}
return 0;
}
洛谷P3830 随机树(SHOI2012)概率期望DP
题意:中文题,按照题目要求的二叉树生成方式,问(1)悲凉的飞机深度 (2)树平均深度 解法:这道题看完题之后完全没头绪,无奈看题解果然不是我能想到的qwq.题解参考https://blog.csdn.ne …
BZOJ2830 &; 洛谷3830：[SHOI2012]随机树——题解
https://www.luogu.org/problemnew/show/P3830#sub
洛谷1087 FBI树 解题报告
洛谷1087 FBI树 本题地址:http://www.luogu.org/problem/show?pid=1087 题目描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全 …
洛谷P3018 [USACO11MAR]树装饰Tree Decoration
洛谷P3018 [USACO11MAR]树装饰Tree Decoration树形DP 因为要求最小,我们就贪心地用每个子树中的最小cost来支付就行了 #include
NOIP2017提高组Day2T3 列队 洛谷P3960 线段树
原文链接https://www.cnblogs.com/zhouzhendong/p/9265380.html 题目传送门 – 洛谷P3960 题目传送门 – LOJ#2319 题目传送门 – Vij …
洛谷P3703 [SDOI2017]树点涂色(LCT，dfn序，线段树，倍增LCA)
洛谷题目传送门 闲话 这是所有LCT题目中的一个异类. 之所以认为是LCT题目,是因为本题思路的瓶颈就在于如何去维护同颜色的点的集合. 只不过做着做着,感觉后来的思路(dfn序,线段树,LCA)似乎要 …
洛谷P3372线段树1
难以平复鸡冻的心情,虽然可能在大佬眼里这是水题,但对蒟蒻的我来说这是个巨大的突破(谢谢我最亲爱的lp陪我写完,给我力量).网上关于线段树的题解都很玄学,包括沉静的小蝴蝶的中的 …
洛谷P1280 && caioj 1085 动态规划入门(非常规DP9：mldpj的任务)
这道题我一直按照往常的思路想 f[i]为前i个任务的最大空暇时间 然后想不出来怎么做– 后来看了题解 发现这里设的状态是时间,不是任务 自己思维还是太局限了,题做得太少. 很多网上题解都反着做,那么 …
洛谷3830 [SHOI2012]随机树 【概率dp】
题目 输入格式 输入仅有一行,包含两个正整数 q, n,分别表示问题编号以及叶结点的个数. 输出格式 输出仅有一行,包含一个实数 d,四舍五入精确到小数点后 6 位.如果 q = 1,则 d 表示叶结 …
随机推荐
来玩Play框架05 数据库
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明.谢谢! 数据库是整个站点的数据储藏室.用户提交的数据可以存储在数据库中,以便未来使用.Pl …
oracle课堂笔记
1.DOS登录1.1.sqlplus 输入用户名.密码1.2.sqlplus /nolog conn 用户名/密码@ip地址/数据库名称 [如果是sys登录则必须加上as sysdba ,as sys …
append appendChild appendTo区别
1.append和appendChild的区别 append是jquery文档操作用法 ① append() 方法在被选元素的结尾(仍然在内部)插入指定内容. $(selector).append(c …
防范 DDoS 攻击的 15 个方法
为了对抗 DDoS(分布式拒绝服务)攻击,你需要对攻击时发生了什么有一个清楚的理解. 简单来讲,DDoS 攻击可以通过利用服务器上的漏洞,或者消耗服务器上的资源(例如 内存.硬盘等等)来达到目的.DD …
BZOJ3105: [cqoi2013]新Nim游戏
题解: 线性基?类似于向量上的基底. 此题题解戳这里:http://blog.csdn.net/wyfcyx_forever/article/details/39477673 代码: #include …
数据库(学习整理)—-4–Oracle数据查询(基础点1)
其他: 计算机中的内存是线性的,一维. length(”)计算字符的个数,而不是字节的个数 Oracle中的日期类型和数值类型的数据可以做运算符(>,=,)比较 如果 …
【动态规划】XMU 1028 Game Boy Advance
题目链接: http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1028 题目大意: 求01背包最优解的方案.物件数和物件编号. 题目思路: [动态规划] …
svn 提交 working copy is not up-to-date
svn在提交时报错信息如下: working copy is not up-to-date svn:commit failed(details follow): svn:file “xxxx …
安装配置Oracle 12c RAC
http://www.lab128.com/rac12_installation_using_vb/article_text.html
Vue用axios跨域访问数据
Vue用axios跨域访问数据axios是vue-resource的替代品,vue-resource不再维护.安装axios:npm install axios使用vue-cli开发时,由于项目本身启 …