洛谷3830[shoi2012]随机树概率dp(代码片段)

关键词：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<\' \'; puts("");
using namespace std;
const int maxn = 205,maxm = 100005,INF = 1000000000;
inline int read()
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57)if (c == \'-\') flag = -1; c = getchar();
	while (c >= 48 && c <= 57)out = (out << 3) + (out << 1) + c - 48; c = getchar();
	return out * flag;

double f[maxn][maxn];
int n,t,m;
void solve1()
	double ans = 0;
	for (int i = 2; i <= n; i++)
		ans += 2.0 / i;
	
	printf("%.6lf\\n",ans);

void solve2()
	for (int i = 1; i <= n; i++) f[i][0] = 1;
	for (int i = 2; i <= n; i++)
		for (int d = 1; d < i; d++)
			for (int j = 1; j < i; j++)
				f[i][d] += (f[j][d - 1] + f[i - j][d - 1] - f[j][d - 1] * f[i - j][d - 1]) / (i - 1);
		
	
	double ans = 0;
	for (int i = 1; i < n; i++) ans += f[n][i];
	printf("%.6lf\\n",ans);

int main()
	t = read(); n = read();
	if (t & 1) solve1();
	else solve2();
	return 0;

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

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

luogup3830[shoi2012]随机树期望dp(代码片段)

LINK：随机树非常经典的期望dp.考虑第一问：设f[i]表示前i个叶子节点的期望平均深度。因为期望具有线性性所以可以由每个叶子节点的期望平均深度得到总体的。(f[i]=(f[i-1]cdot(i-1)+(f[i-1]+1)cdot2-f[i-1])/i=f[i-1]+2/i)考虑第二问：可以设... 查看详情

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

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

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

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

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

感觉第一问就非常神仙，还有第二问怎么被我当成组合数学题来做了首先是第一问期望具有线性性，于是深度平均值的期望等于深度和的期望值的平均设(dp_x)表示具有(x)个叶子节点的树的深度和的期望值是多少我们发现扩展一个... 查看详情

●洛谷p1291[shoi2002]百事世界杯之旅

题链：https://www.luogu.org/recordnew/show/5861351题解：dp，期望 定义dp[i]表示还剩下i个盖子没收集时，期望还需要多少次才能手机完。 初始值：dp[0]=0 显然对于一个状态，我们随机得到一个盖子，有两种可能： 1.得到了曾经没有的盖子... 查看详情

[shoi2012]随机树

题面在这里题意随机生成一棵(n)个叶节点的二叉树,方法是从根节点开始,每次等概率选择一个叶子节点(一开始根节点同时也是叶子节点)并生成其左右儿子(称为一次展开),直到该树有(n)个叶节点为止给定(nleq100),求其叶节点平均深... 查看详情

洛谷3833shoi2012魔法树

【题解】　　树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情

bzoj3566[shoi2014]概率充电器树形概率dp

...全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以... 查看详情

bzoj3566:[shoi2014]概率充电器

...法】树型DP+期望DP【题意】一棵树上每个点均有直接充电概率qi%，每条边有导电概率pi%，问期望有多少结点处于充电状态？【题解】引用自：【BZOJ3566】【SHOI2014】概率充电器树形DP概率DP by 空灰冰魂最大的难点在于计算每... 查看详情

bzoj3566:[shoi2014]概率充电器树形概率dp(代码片段)

设g[u]为这个点被儿子和自己充上电的概率，f[u]为被儿子、父亲和自己充上电的概率然后根据贝叶斯公式（好像是叫这个），1.P(A+B)=P(A)+P(B)-P(A)*P(B)，2.P(A)=(P(A+B)-P(B))/(1-P(B))g的转移很好想，根据上面的1公式，g[u]=g[u]+g[e[i].to]*e[i].p-g... 查看详情

洛谷p4332[shoi2014]三叉神经树题解(代码片段)

一、题目：洛谷原题二、思路：这道题怎么说呢？只能说有点意思，让我第一次见识了LCT怎么应用。首先一个非常明显的性质，就是比如我现在修改了某个叶子结点，记为\\(leaf\\)，那么因此而状态发生改变的点一定是从\\(leaf\\)... 查看详情

[shoi2014]概率充电器(代码片段)

嘟嘟嘟这种复杂的概率大题我果然是每做出来……然后我找到了一篇极棒的题解，小学生都能看懂（大佬就是大佬啊）：题解P4284【[SHOI2014]概率充电器】，第二次dp的状态方程真的很妙啊。刚开始我总按照套路想设\(dp[u]\)表示\(u\... 查看详情

●bzoj3566[shoi2014]概率充电器

题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3566题解：概率dp，树形dp 如果求出每个点被通电的概率t， 那么期望答案就是t1×1+t2×1+t3*1+...+tn×1 现在问题就是要去求每个点被通电的概率。 因为是一颗树，所以每个点是否... 查看详情

[shoi2014]概率充电器

...全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以... 查看详情

[shoi2014]概率充电器

...全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以... 查看详情

bzoj4597[shoi2016]随机序列线段树

【BZOJ4597】[Shoi2016]随机序列Description你的面前有N个数排成一行。分别为A1,A2,…,An。你打算在每相邻的两个Ai和Ai+1间都插入一个加号或者减号或者乘号。那么一共有3^(n-1)种可能的表达式。你对所有可能的表达式的值的和非常感... 查看详情

p4340[shoi2016]随机序列(线段树)(代码片段)

P4340[SHOI2016]随机序列(线段树)结论：只有前缀积有贡献。因为第一个数前面是没有符号的，除了前缀积外，都可以通过加号变成减号、减号变加号使其贡献抵消。接下来考虑每个前缀积的贡献。我们可以枚举前缀积的... 查看详情