Accidental Arithmetic 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： Lucius7

设输入数字串长度为 \(n\)，从左到右下标 \(i\) 为 \(0 \dots n - 1\)，第 \(i\) 位数字为 \(d_i\)。

考虑每一位数字对最终答案的期望贡献。

如果 \(d_i\) 之前出现过 - 或 +，由于两者出现概率均为 \(45\%\)，所在数字块的期望将正负抵消为 \(0\)。

因此，\(d_i\) 对答案贡献当且仅当它位于第一个数字块中，即它前面的 \(i\) 个间隙全部是 "无操作"（概率为 \(10\%\)）。该事件发生概率是 \(0.1^i\)，此时数字块的符号必然为正。

接下来考虑 \(d_i\) 在数字块中的位权期望，这取决于它右侧连续出现"无操作"的次数。记 \(d_i\) 右侧的间隙数量为 \(m = n - 1 - i\)。

若在它右侧第 \(j\)（\(0 \le j < m\)）个间隙首次出现 + 或 -，概率为 \(0.1^j \times 0.9\)，此时 \(d_i\) 的位权为 \(10^j\)。其对位权的期望贡献为 \(10^j \times 0.1^j \times 0.9 = 0.9\)。

若直到字符串末尾均未出现符号，概率为 \(0.1^m\)，此时 \(d_i\) 的位权为 \(10^m\)，其对位权的期望贡献为 \(10^m \times 0.1^m = 1\)。

综上，得到第 \(i\) 位数字对总答案的期望贡献： \[ 0.1^i \times (0.9(n - 1 - i) + 1) \times d_i \] 时间复杂度：\(O(n)\)。

#include <bits/stdc++.h>

using i64 = long long;
using real = long double;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;

    const int n = s.size();
    real p = 1;
    real ans = 0;
    for (int i = 0; i < n; i++) {
        ans += p * ((n - i - 1) * 0.9 + 1) * (s[i] - '0');
        p *= 0.1;
    }
    std::cout << std::fixed << std::setprecision(10) << ans << "\n";

    return 0;
}

评论