程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5425 Rikka with Tree II(暴力)

hdu 5425 Rikka with Tree II(暴力)

編輯:關於C++

 

 

直接枚舉就好了,當概率極小時貢獻值可以忽略。

 

 

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 1e5 + 5;

int N, D[maxn];
vector G[maxn];

void init () {
	for (int i = 1; i <= N; i++) G[i].clear();

	int t;
	for (int i = 2; i <= N; i++) {
		scanf(%d, &t);
		G[t].push_back(i);
	}

	queue Q;
	D[1] = 0;
	Q.push(1);

	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();

		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			D[v] = D[u] + 1;
			Q.push(v);
		}
	}
	sort(D + 1, D + 1 + N);
}

int main () {
	while (scanf(%d, &N) == 1) {
		init ();

		double ans = 0;
		for (int i = 0; i < N && i < 100; i++) {
			int u = N - i;
			double w = 0;
			for (int j = N; j > u; j--)
				w += 1.0 * (D[u] + 1) * (D[j] + 1) / (D[u] + D[j] + 2);
			double t = pow(2, N-u+1) - (N+1) / pow(2, u-1);
			ans += w / t;
		}
		printf(%.6lf
, ans);
	}
	return 0;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved