正文 

当前位置： 首页 > 程序 > java教程

bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)

LuYouQi233 LuYouQi233     2022-11-07     576

关键词：

https://www.luogu.org/problemnew/show/P3830#sub   <-题面看这里~

https://www.lydsy.com/JudgeOnline/problem.php?id=2830

感觉智商被压制了的一题……后面放吐槽。

参考：https://www.cnblogs.com/GuessYCB/p/8462490.html

——————————————

对于叶结点平均深度，我们令f(x)=(a1+...+ax)/x来表示（a可以每个叶子结点（人为标号）深度的期望）。

那么我们只需要枚举每个a，然后在a上面展开？再除x？

我们为什么不用f(x-1)表示我们要展开的叶子的深度呢？于是第一问我们做完了。

——————————————

第二问设f[x][d]表示叶子数为x深度大于等于d的树的期望。

最后答案就是f[n]累加的结果（简单思考就知道为什么了）

那么对于根，枚举左右儿子挂了多少叶子即可。

一次转移就是f[x][d]=sigma f[i][d-1]+f[x-i][d-1]-f[i][d-1]*f[x-i][d-1] 最后除以x-1即可。

第一个概率是左子树深度为d-1，第二个是右子树深度为d-1，第三个是容斥。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef double dl;
const int N=105;
int q,n;
dl f[N][N];
void solve1()
    dl ans=0;
    for(int i=2;i<=n;i++)ans+=2.0/i;
    printf("%.6lf\\n",ans);

void solve2()
    dl ans=0;
    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<i;k++)
                f[i][j]+=f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1];
            
            f[i][j]/=i-1;
        
    
    for(int i=1;i<=n;i++)
        ans+=f[n][i];
    
    printf("%.6lf\\n",ans);

int main()
    scanf("%d%d",&q,&n);
    if(q==1)solve1();
    else solve2();
    return 0;

吐槽时间：

第一问我是真的傻没想到用f(x-1)来表示我们展开的结点（我还考虑a要怎么求呢……后来发现我根本不会。）

第二问考虑过设f[i]为i个叶子结点时的期望深度，设g[i]为i个叶子结点的最深的叶子的期望个数，答案就是f[i]=f[i-1]+g[i]/i。

但是推g很恶心，反正推了半天也没过样例就很gg。

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

p3830[shoi2012]随机树题解(代码片段)

P3830随机树坑题，别人的题解我看了一个下午没一个看得懂的，我还是太弱了。题目链接 P3830 [SHOI2012]随机树 题目描述输入输出格式输入格式： 输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的... 查看详情

p3830[shoi2012]随机树(代码片段)

P3830[SHOI2012]随机树链接分析：　　　第一问：f[i]表示有i个叶子结点的时候的平均深度，$f[i]=\fracf[i-1]+2+f[i-1]*(i-1)2$，表示新增加一个叶子结点，深度增加2，加权后取平均值。　　第二问：f[i][j]表示有i个叶子结点，树的深度大于... 查看详情

bzoj4869：[shoi2017]相逢是问候——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=4869题面复制于洛谷：https://www.luogu.org/problemnew/show/P3747#sub 参考洛谷的前两篇（也是仅有的两篇）题解。首先我们要知道一个公式：这又被叫做扩展欧拉定理，证明我们并不关心。有了扩展... 查看详情

luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)

题意非常的复杂，考虑转化一下：每次选择一个叶节点，删除本叶节点（深度为$dep$）的同时，加入两个深度为$dep+1$的叶节点，重复$n$轮首先考虑第$1$问，（你看我这种人相信数据绝对是最大的数据，直接$f[i][S]$表示$i$个叶子结... 查看详情

bzoj1934：[shoi2007]善意的投票&bzoj2768：[jloi2010]冠军调查——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=1934https://www.lydsy.com/JudgeOnline/problem.php?id=2768幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的... 查看详情

bzoj4868：[shoi2017]期末考试——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=4868题目复制于洛谷：https://www.luogu.org/problemnew/show/P3745#sub有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所有课程的... 查看详情

bzoj1934:[shoi2007]vote善意的投票

二次联通门: BZOJ1934:[Shoi2007]Vote善意的投票    /*BZOJ1934:[Shoi2007]Vote善意的投票最小割*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgcharc=getc 查看详情

[bzoj4868][shoi&sxoi2017]期末考试（贪心）

Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的... 查看详情

bzoj4416:[shoi2013]阶乘字符串

可以大胆猜想n>21时无解，至于依据，不开O2，1s，n<=21刚好能卡过去==并不会证==#include<cstdio>voidup(int&a,intb){ a=a<b?b:a;}inttest,n,m,i,j;chart[500];intf[1<<21],s[500][21];intmain(){ scanf("%d",&test) 查看详情

bzoj3339：rmqproblem&bzoj3585&洛谷4137：mex——题解(代码片段)

前者：https://www.lydsy.com/JudgeOnline/problem.php?id=3339后者：https://www.lydsy.com/JudgeOnline/problem.php?id=3585https://www.luogu.org/problemnew/show/P4137有一个长度为n的数组a1,a2,…,an。m次询问，每次询问一个区间内最 查看详情

bzoj1933[shoi2007]bookcase书柜的尺寸

神奇的dp优化。考虑6维状态的dp,分别表示三行高和宽，显然MLE&&TLE。把高排个序，从大到小往架上放，那么若不是重开一行便对高度没有影响。然后求出宽度的sum,dp[i][j]表示第一行放了i的宽度，二行放了j的宽度，三行放了... 查看详情

bzoj-4591:[shoi2015]超能粒子炮·改(lucas+排列组合)

4591:[Shoi2015]超能粒子炮·改TimeLimit: 10Sec  MemoryLimit: 256MBSubmit: 960  Solved: 360[​​Submit​​​][​​Status​​​][​​Discuss​​]Description曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTS 查看详情

bzoj千题计划143：bzoj1935:[shoi2007]tree园丁的烦恼

http://www.lydsy.com/JudgeOnline/problem.php?id=1935 二维偏序问题排序x，离散化树状数组维护y #include<cstdio>#include<iostream>#include<algorithm>#definelowbit(x)x&-xusingnamespacestd;#de 查看详情

bzoj3262：陌上花开&洛谷3810：三维偏序——题解

两者题一样，方便没有bzoj权限的朋友。http://www.lydsy.com/JudgeOnline/problem.php?id=3262https://www.luogu.org/problemnew/show/3810Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级... 查看详情

bzoj1229&洛谷2917：[usaco2008nov]toy玩具&洛谷4480：[bjwc2018]餐巾计划问题——题解(代码片段)

标题很长emmm……[USACO2008NOV]toy玩具https://www.luogu.org/problemnew/show/P2917https://www.lydsy.com/JudgeOnline/problem.php?id=1229[BJWC2018]餐巾计划问题https://www.luogu.org/problemnew/show/P4480其中 查看详情

bzoj千题计划112：bzoj1022:[shoi2008]小约翰的游戏john

http://www.lydsy.com/JudgeOnline/problem.php?id=1022 http://www.cnblogs.com/TheRoadToTheGold/p/6744825.html #include<cstdio>#include<iostream>usingnamespacestd;voidread(int&x 查看详情

bzoj3343&洛谷2801：教主的魔法——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3343https://www.luogu.org/problemnew/show/2801题目描述教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一... 查看详情

bzoj4943&洛谷3823&uoj315：[noi2017]蚯蚓排队——题解(代码片段)

....luogu.org/problemnew/show/P3823#sub题面太长自己看吧orz。参考：洛谷题解。用链表暴力维护每个蚯蚓，每次合并和分离只对k*k的元素有影响，哈希一下存起来query时候比较就好了。没了。（ 查看详情