首页 > 其他 > 详细

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

时间:2014-05-21 16:07:22      阅读:402      评论:0      收藏:0      [点我收藏+]

题目链接:uva 10883 - Supermean

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

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

例:

中间的2可以通过蓝色和红色两条路径影响最后的答案。
bubuko.com,布布扣

#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;
}

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

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

原文:http://blog.csdn.net/keshuai19940722/article/details/26381253

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!