UVA 10883 - Supermean(组合数学+数值优化)

题目链接:10883 - Supermean

题意:求超级平均数,就是相邻两个算一个平均数,直到剩下一个数,求数值。

思路:画图很容易推断出公式。就拿最后一组样例来说

1     2      3      4      5

1.5  2.5   3.5   4.5

2       3      4

2.5   3.5

3

观察可以发现都是从顶到底,看又几条路线,就有几次,然后最后每个数字在除上相应次数的2,那几条路线就是C(n - 1, [0 - n - 1])的组合数。

所以ans = sum{C(n - 1, i) * a[i] / 2^(n - 1)}

然后由于n很大,直接算会悲剧的。

所以每一项都先取log值,最后在次方乘回去,那么每一项为

log(C(n - 1, i) * a[i] / 2^(n - 1)) = log(C(n - 1, i)) + log(a[i]) - (n - 1) * log(2);

最后再利用exp函数计算回去,从而求出总和即可

代码:

#include <stdio.h>
#include <string.h>
#include <math.h>
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 50005;
int t, n;
double a, c;

double cal(int i, double a) {
	return c + log(a) - (n - 1) * log(2);
}

int main() {
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		double sum = 0;
		c = 0;
		for (int i = 0; i < n; i++) {
			scanf("%lf", &a);
			if (a < 0) sum -= exp(cal(i, -a));
			else sum += exp(cal(i, a));
			c = c + log(n - i - 1) - log(i + 1);
		}
		printf("Case #%d: %.3lf\n", ++cas, sum);
	}
	return 0;
}

UVA 10883 - Supermean(组合数学+数值优化),布布扣,bubuko.com

时间: 05-10

UVA 10883 - Supermean(组合数学+数值优化)的相关文章

UVA - 10883 Supermean

Description Problem F Supermean Time Limit: 2 second "I have not failed. I've just found 10,000 ways that won't work." Thomas Edison Do you know how to compute the mean (or average) of n numbers? Well, that's not good enough for me. I want the s

UVa 10003 (可用四边形不等式优化) Cutting Sticks

题意: 有一个长为L的木棍,木棍中间有n个切点.每次切割的费用为当前木棍的长度.求切割木棍的最小费用. 分析: d(i, j)表示切割第i个切点到第j个切点这段所需的最小费用.则有d(i, j) = min{d(i, k) + d(k, j)} + a[j] - a[i]; ( i < k < j ) 最后一项是第一刀的费用. 时间复杂度为O(n3) 最后还要注意一下输出格式中整数后面还要加一个句点. 1 //#define LOCAL 2 #include <iostream>

Uva 11609 Teams (组合数学)

题意:有n个人,选不少于一个人参加比赛,其中一人当队长,有多少种选择方案. 思路:我们首先C(n,1)选出一人当队长,然后剩下的 n-1 人组合的总数为2^(n-1),这里用快速幂解决 代码: #include <iostream> #define ll long long using namespace std; const ll mod = 1000000007; ll qmod(ll a, ll b) { ll ans=1; while(b) { if(b&1) { ans=(a

UVA 11609 Teams 组合数学+快速幂

In a galaxy far far away there is an ancient game played among the planets. The specialty of the gameis that there is no limitation on the number of players in each team, as long as there is a captain inthe team. (The game is totally strategic, so so

uva - 10833 Supermean(二项式系数,对指数)

模拟发现,每个元素求和时,元素的系数是二项式系数,于是ans=sum(C(n-1,i)*a[i]/2^(n-1)),但是n太大,直接求会溢出,其实double的范围还是挺大的,所以可以将组合数转化成对数: e^(lnC(n-1, k)*A[k]/(2^n-1) )  ==>  e^( ln C(n-1,k) + ln A[k] - (n-1)*ln2 ); 又直接利用公式求二项式系数:C(n, k+1)/C(n, k) = (n-k)/(k+1); 而且对数还有递推求法: logC(n,k+1)

python科学计算_scipy_常数与优化

scipy在numpy的基础上提供了众多的数学.科学以及工程计算中常用的模块:是强大的数值计算库: 1. 常数和特殊函数 scipy的constants模块包含了众多的物理常数: import scipy.constants as CC.c ?#真空中的光速C.h ?#普朗克常数C.pi #圆周率? 在C.physical_constants字典中,通过物理常数的名称访问该物理常数,如: C.physical_constants['speed of light in vacuum'] (2997

西瓜书第三章 线性模型

读书笔记 周志华老师的<机器学习> 因为边看边记,所以写在随笔里,如果涉及版权问题,请您联系我立马删除,[email protected] 3.1 基本形式 给定d个属性描述的示例 x = (x_1;x_2;...;x_3), 其中x_i是X在第i个属性上的取值,线性模型视图学得一个通过属性的线性组合来进行预测的函数,即 f(x) = w_1*x_1 + w_2*x_2 + ... + w_d*x_d + b, 向量形式 其中 w = (w_1;w_2;...;w_d). w直观表达了各属性在

视觉机器学习读书笔记--------BP学习

反向传播算法(Back-Propagtion Algorithm)即BP学习属于监督式学习算法,是非常重要的一种人工神经网络学习方法,常被用来训练前馈型多层感知器神经网络. 一.BP学习原理 1.前馈型神经网络 是指网络在处理信息时,信息只能由输入层进入网络,随后逐层向前进行传递,一直到输出层,网络中不存在环路:前馈神经网络是神经网络中的典型分层结构,根据前馈网络中神经元转移函数.网络层数.各层基本单元数目以及权重调整方式的不同,可以形成不同功能特点的神经网络.前馈型神经网络由输入层.中间层(隐

关于机器学习和深度学习的资料

声明:转来的,原文出处:http://blog.csdn.net/achaoluo007/article/details/43564321 编者按:本文收集了百来篇关于机器学习和深度学习的资料,含各种文档,视频,源码等.而且原文也会不定期的更新,望看到文章的朋友能够学到更多. <Brief History of Machine Learning> 介绍:这是一篇介绍机器学习历史的文章,介绍很全面,从感知机.神经网络.决策树.SVM.Adaboost 到随机森林.Deep Learning. &