首页 > 代码库 > UVA 10883 - Supermean（组合数学+数值优化）

UVA 10883 - Supermean（组合数学+数值优化）

2024-07-04 00:12:15   223人阅读

题目链接: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;
}


联系
我们