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