UVA10883 题解

· · 题解

卡常大法好，1.78s 暴力模拟代码爆切蓝题！

题意就是有 n 个数，不断对相邻的两个数求平均值，输出最后剩下的那个数。

这不就纯模拟嘛，开个双重循环算就可以了，这还蓝啊？

卡常，打个 Ofast 和 cin 加速。

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;

const ll N = 5e4 + 9;

ll t, n, num = 1;
double a[N]; 

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (ll i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (ll i = n - 1; i >= 1; i--) {
            for (ll j = 1; j <= i; j++) {
                a[j] = (a[j] + a[j + 1]) / 2.0;
            }
        }
        printf("Case #%lld: %.3lf\n", num, a[1]);
        ++num;
    }
    return 0;
}

成功地用 1.78s 草过去了，遥遥领先。也许是暴力方法的最优解？

或许可以用快读快写，循环展开等方式卡到更少的用时，但我没试。

建议用 C++20 交，会更快一些。

给蓝题一点尊严，写个正解。

设数列为 \{a_n\}，操作次数为 p，则有：

\begin{aligned} p=0&:\{a_1,a_2,...a_n\}\\ p=1&:\{\dfrac{a_1+a_2}{2},\dfrac{a_2+a_3}{2},...,\dfrac{a_{n-1}+a_n}{2}\}\\ p=2&:\{\dfrac{a_1+2a_2+a_3}{4},\dfrac{a_2+2a_3+a_4}{4},...,\dfrac{a_{n-2}+2a_{n-1}+a_n}{4}\}\\ p=3&:\{\dfrac{a_1+3a_2+3a_3+a_4}{8},\dfrac{a_2+3a_3+3a_4+a_5}{8},...,\dfrac{a_{n-3}+3a_{n-2}+3a_{n-1}+a_n}{8}\} \end{aligned}

手玩几个样例，可以推出最多能操作 n - 1 次。

不看分母，看每次操作完后每项的系数，可以发现这个系数规律和杨辉三角是一样的，那我们就可以推出：操作 n - 1 次后，剩下的数为

\displaystyle\sum^{n}_{i=1}\dfrac{\mathrm C_{n-1}^{i-1}a_i}{{2^{n-1}}} 设 $ans=\displaystyle\sum^{n}_{i=1}\dfrac{\mathrm C_{n-1}^{i-1}a_i}{{2^{n-1}}}$，则有 $$ \begin{aligned} ans&=\displaystyle\sum^{n}_{i=1}\dfrac{\mathrm C_{n-1}^{i-1}a_i}{{2^{n-1}}}\\ &=\displaystyle\sum^{n}_{i=1}2^{\log_2\frac{\mathrm C_{n-1}^{i-1}a_i}{{2^{n-1}}}}\\ &=\displaystyle\sum^{n}_{i=1}2^{\log_2(\mathrm C_{n-1}^{i-1}a_i)-\log_22^{n-1}}\\ &=\displaystyle\sum^{n}_{i=1}2^{\log_2(\mathrm C_{n-1}^{i-1})+\log_2a_i-{n+1}}\\ \end{aligned} $$ 由于 $a_i$ 可以小于 $0$，那么 $$ \begin{aligned} ans&=\displaystyle\sum^{n}_{i=1}2^{\log_2(\mathrm C_{n-1}^{i-1})+\log_2a_i-{n+1}}\\ &=\displaystyle\sum^{n}_{i=1}\mathrm{sgn} (a_i)\times 2^{\log_2(\mathrm C_{n-1}^{i-1})+\log_2|a_i|-{n+1}}\\ \end{aligned} $$ 其中 $$ \mathrm{sgn}(x)= \begin{cases} 1,x>0\\ 0,x=0\\ -1,x<0 \end{cases}. $$ 接着考虑解决 $\mathrm C_{n-1}^{i-1}$，因为 $$ \mathrm C_{n}^{m}=\dfrac{n!}{m!(n-m)!} $$ 则有 $$ \begin{aligned} \mathrm C_{n}^{m+1}&=\dfrac{n!}{(m+1)![n-(m+1)]!}\\ &=\dfrac{n!}{(m+1)!(n-m-1)!}\\ &=\dfrac{n!}{m!\times(m+1)\times\dfrac{(n-m)!}{n-m}}\\ &=\dfrac{n!}{m!\times(n-m)!\times\dfrac{m+1}{n-m}}\\ &=\dfrac{n!}{m!\times(n-m)!\times\dfrac{m+1}{n-m}}\\ &=\dfrac{n!}{m!\times(n-m)!}\times\dfrac{n-m}{m+1}\\ &=\mathrm C_{n}^{m}\times\dfrac{n-m}{m+1}\\ \end{aligned} $$ 因为是从 $i=1$ 开始计算 $\mathrm C_{n-1}^{i-1}$ 的值，那么就可以用上面推导的公式来减少计算量。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; ll t, n, num = 1; double a; int sgn(double x) { if (x > 0) return 1; if (!x) return 0; if (x < 0) return -1; } int main() { cin >> t; while (t--) { cin >> n; double c = 0, ans = 0, p; for (ll i = 1; i <= n; i++) { cin >> a; ans += sgn(a) * pow(2, c + log2(fabs(a)) - n + 1); c += log2((n - i) * 1.0 / i); } printf("Case #%lld: %.3lf\n", num, ans); ++num; } return 0; } ```