题目链接:
http://codeforces.com/problemset/problem/696/B
题目大意:
给一棵树,从根节点开始递归,time=1,每次递归等概率随机访问这个节点的子节点,走过不会再走,每访问到一个新节点time+1,求访问每个节点的时间的期望。
题目思路:
【数学规律】
这题其实是一道概率DP的题目,但是找规律后发现答案和当前结点的子树大小有关。
ans[v]=ans[u]+1+0.5*(child[u]-child[v]-1),child为当前节点的子树大小。
//
//by coolxxx
////<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 100004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
int fa[N],s[N],last[N];
double c[N];
struct xxx
{
int next,to;
}a[N];
void add(int x,int y)
{
a[++lll].next=last[x];
a[lll].to=y;
last[x]=lll;
}
void cal(int u)
{
int i,v;
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
cal(v);
s[u]+=s[v];
}
s[u]++;
}
void dfs(int u)
{
int i,v;
for(i=last[u];i;i=a[i].next)
{
v=a[i].to;
c[v]=c[u]+(s[u]-s[v]-)*0.5+;
dfs(v);
}
}
void print()
{
int i;
for(i=;i<=n;i++)
{
printf("%d ",s[i]);
}
puts("");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j;
// for(scanf("%d",&cas);cas;cas--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
mem(s,);mem(last,);lll=;
for(i=;i<=n;i++)
{
scanf("%d",&fa[i]);
add(fa[i],i);
}
cal();
c[]=1.0;
dfs();
for(i=;i<=n;i++)
printf("%.1lf ",c[i]);
puts("");
}
return ;
}
/*
// //
*/
【数学相关、规律】Codeforces 696B Puzzles的更多相关文章
-
CodeForces - 696B Puzzles
http://codeforces.com/problemset/problem/696/B 题目大意: 这是一颗有n个点的树,你从根开始游走,每当你第一次到达一个点时,把这个点的权记为(你已经到过不 ...
-
codeforces 696B Puzzles 树形概率计算
题意:给一棵有根树,从根节点深搜,每次随机走,问每个点的dfs序的期望是多少 分析:对于每一个点,它的所有祖先节点dfs序肯定在它之前,它所在的子树的节点一定在它后面, 剩下的是既不是子树又不是祖先的 ...
-
codeforces 687B - Remainders Game 数学相关(互质中国剩余定理)
题意:给你x%ci=bi(x未知),是否能确定x%k的值(k已知) ——数学相关知识: 首先:我们知道一些事情,对于k,假设有ci%k==0,那么一定能确定x%k的值,比如k=5和ci=20,知道x% ...
-
[自用]多项式类数学相关(定理&;证明&;板子)
写在前面 由于上一篇总结的版面限制,特开此文来记录 \(OI\) 中多项式类数学相关的问题. 该文启发于Miskcoo的博客,甚至一些地方直接引用,在此特别说明:若文章中出现错误,烦请告知. 感谢你的 ...
-
[总结]多项式类数学相关(定理&;证明&;板子)
目录 写在前面 前置技能 多项式相关 多项式的系数表示 多项式的点值表示 复数相关 复数的意义 复数的基本运算 单位根 代码相关 多项式乘法 快速傅里叶变换 DFT IDFT 算法实现 递归实现 迭代 ...
-
[总结]其他杂项数学相关(定理&;证明&;板子)
目录 写在前面 一类反演问题 莫比乌斯反演 快速莫比乌斯变换(反演)与子集卷积 莫比乌斯变换(反演) 子集卷积 二项式反演 内容 证明 应用举例 另一形式 斯特林反演 第一类斯特林数 第二类斯特林数 ...
-
【3D研发笔记】之【数学相关】(一):坐标系
现在开始学习3D基础相关的知识,本系列的数学相关笔记是基于阅读书籍<3D数学基础:图形与游戏开发>而来,实现代码使用AS3,项目地址是:https://github.com/hammerc ...
-
[总结]数论和组合计数类数学相关(定理&;证明&;板子)
0 写在前面 0.0 前言 由于我太菜了,导致一些东西一学就忘,特开此文来记录下最让我头痛的数学相关问题. 一些引用的文字都注释了原文链接,若侵犯了您的权益,敬请告知:若文章中出现错误,也烦请告知. ...
-
Python学习笔记17:标准库之数学相关(math包,random包)
前面几节看得真心累.如今先来点简单easy理解的内容. 一 math包 math包主要处理数学相关的运算. 常数 math.e # 自然常数e math.pi # 圆周率pi 运算函数 math ...
随机推荐
-
google地图引入网页
<script src=);//指定坐标,缩放级别,setcenter 设置地图中心位置 //var mapControl = new GMapTypeControl() ...
-
Hashtable和HashMap区别
Hashtable和HashMap区别 相同点: 实现原理,功能相同,可以互用 主要区别: a.hashtable继承Directionary类,HashMap实现Map接口 b.Hashtable线 ...
-
sql server 2008 r2 中的oracle发布使用笔记
sql server 2008 r2 中的oracle发布功能,能够将oracle数据库作为发布服务器,将oracle中的数据自动同步到sql server 数据库中,在新建oracle发布前确保sq ...
-
Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)
描述 http://codevs.cn/problem/1040/ 与Codevs_1017_乘积最大很像,都是划分型dp. 给出一个字符串和几个单词,要求将字符串划分成k段,在每一段中求共有多少单词 ...
-
软件包管理_rpm命令管理_yum工具管理_文件归档压缩_源码包管理
rpm命令管理软件 对于挂载的像U盘那种都会在midea目录下,但是会显示在桌面上 安装软件(i:install,v:verbose冗长的,h:human):rpm -ivh xxxx.rpm 安 ...
-
NEU OJ 1651 Great number
循环节是2000000016 字符串读入,用一下高精度对2000000016取个模,用一下快速幂就可以算出答案了. #include <cstdio> #include <iostr ...
-
多线程面试题系列(6):经典线程同步 事件Event
上一篇中使用关键段来解决经典的多线程同步互斥问题,由于关键段的"线程所有权"特性所以关键段只能用于线程的互斥而不能用于同步.本篇介绍用事件Event来尝试解决这个线程同步问题.首先 ...
-
Android Exception Type ";share_dialog_title"; is not translated in en, zh-rTW strings
异常出现的场景:打包Android项目时出现 解决办法: Eclipse > Preference > Android > Lint Error Checking搜索Messages ...
-
QEvent postEvent/sendEvent
可以自訂事件類型,最簡單的方式,是透過QEvent::Type指定事件類型的常數值,在建構QCustomEvent時作為建構引數並透過postEvent()傳送事件,例如: const QEvent: ...
-
python 客户端点对点通信小案例
点对点通讯分为客户端和服务器,多个客户端通过服务器进行信息的交流 服务器端代码 service端 #!/usr/bin/env python # -*- coding:utf-8 -*- impor ...