首页 > 代码库 > uva 10883 - Supermean(组合数学+数值优化)

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

题目链接:uva 10883 - Supermean

题目大意:给出n个数,每相邻两个数求平均数,将得到n-1个数,这n-1个数每相邻的两个数求平均值,将得到n-2个数。一次类推,求最后得到的那个数的值。

解题思路:类似与杨辉三角,第i个数起始被加了C(n?1i?1)次。总共有2n?1个数相加。但是因为n有50000,250000根本存不下,所以借助log函数。

例:

中间的2可以通过蓝色和红色两条路径影响最后的答案。

#include <cstdio>
#include <cstring>
#include <cmath>

int main () {
    int cas;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        int n;
        double ans = 0, a, c = 0;

        scanf("%d", &n);
        for (int j = 0; j < n; j++) {
            scanf("%lf", &a);
            double tmp = log2(fabs(a));

            if (j) {
                c += log2(double(n-j)/j);
                tmp += c;
            }

            if (a < 0)
                ans -= pow(2, tmp - n + 1);
            else
                ans += pow(2, tmp - n + 1);
        }

        printf("Case #%d: %.3lf\n", i,  ans);
    }
    return 0;
}