题解 | #单选错位#

题目链接

单选错位

题目描述

一份试卷有 $N$ 道单项选择题，第 $i$ 题有 $a_i$ 个选项。每道题的正确答案都是从其选项中等概率随机选出的。

旺仔哥哥本来做对了所有题目，但在誊写答案时，发生了错位：

原第 $i$ 题的答案被写到了第 $i+1$ 题的位置 (对于 $1 \le i < N$ )。
原第 $N$ 题的答案被写到了第 $1$ 题的位置。

求在这种情况下，旺仔哥哥期望能答对多少题。

输入:

第一行一个整数 $N$ ，表示题目数量。
第二行 $N$ 个整数 $a_1, a_2, \dots, a_N$ ，表示每道题的选项数。

输出:

输出一个实数，表示期望答对的题目数。

解题思路

本题的核心是利用期望的线性性质。

1. 期望的线性性质

设 $X$ 为总共答对的题目数，这是一个随机变量。我们要求的是 $E[X]$ 。
根据期望的线性性质， $E[X]$ 等于每道题答对的期望之和。
我们可以为每道题定义一个指示器随机变量 $X_i$ ： $X_i = \begin{cases} 1 & \text{如果第 } i \text{ 题答对} \\ 0 & \text{如果第 } i \text{ 题答错} \end{cases}$
那么，总答对数 $X = \sum_{i=1}^{N} X_i$ 。
根据期望的线性性质， $E[X] = E[\sum_{i=1}^{N} X_i] = \sum_{i=1}^{N} E[X_i]$ 。
对于一个指示器随机变量， $E[X_i]$ 等于它取值为 $1$ 的概率，即第 $i$ 题答对的概率 $P(\text{第 } i \text{ 题答对})$ 。
所以，最终的期望答对题目数就是所有题目各自答对的概率之和： $E[X] = \sum_{i=1}^{N} P(\text{第 } i \text{ 题答对})$ 。

2. 计算每道题答对的概率

现在问题转化为计算每一道题答对的概率。

对于第 1 题：
- 写到第 1 题位置上的答案，实际上是原来第 $N$ 题的正确答案。
- 这个答案是第 $N$ 题 $a_N$ 个选项中的一个。
- 而第 1 题的正确答案，是独立地从它自己的 $a_1$ 个选项中随机选出的。
- 这两个答案恰好相等的概率是 $\frac{1}{\max(a_1, a_N)}$ 。
  - 解释：假设 $a_1 \le a_N$ 。第 $N$ 题的答案有 $a_N$ 种可能。第 1 题的答案要与它相同，只有 $1/a_N$ 的概率。同时，这两个答案必须都存在于较小的选项集合中。因为第 $N$ 题的答案是从 $1 \dots a_N$ 中选，第 1 题的正确答案是从 $1 \dots a_1$ 中选。如果第 $N$ 题的答案大于 $a_1$ ，那么第 1 题永远不可能答对。所以，第 $N$ 题的答案必须落在 $1 \dots a_1$ 范围内（概率为 $a_1 / a_N$ ），并且第 1 题的正确答案恰好是这个数（概率为 $1/a_1$ ）。总概率是 $(a_1/a_N) \cdot (1/a_1) = 1/a_N = 1/\max(a_1, a_N)$ 。对称地，当 $a_N < a_1$ 时，概率为 $1/a_1$ 。
对于第 $i$ 题 (其中 $2 \le i \le N$ )：
- 写到第 $i$ 题位置上的答案，是原来第 $i-1$ 题的正确答案。
- 这个答案是第 $i-1$ 题 $a_{i-1}$ 个选项中的一个。
- 第 $i$ 题的正确答案是从它自己的 $a_i$ 个选项中独立随机选出的。
- 同理，这两个答案相等的概率是 $\frac{1}{\max(a_i, a_{i-1})}$ 。

3. 汇总计算

将所有概率相加即可得到最终的期望值： $E[X] = \frac{1}{\max(a_1, a_N)} + \sum_{i=2}^{N} \frac{1}{\max(a_i, a_{i-1})}$

算法很简单：

读取 $N$ 和数组 $a$ 。
计算第 1 题的答对概率 $1.0 / \max(a_1, a_N)$ 。
循环从 $i=2$ 到 $N$ ，累加第 $i$ 题的答对概率 $1.0 / \max(a_i, a_{i-1})$ 。
输出总和。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    double expected_value = 0.0;

    // 计算第 1 题的期望
    if (n > 0) {
        expected_value += 1.0 / max(a[0], a[n - 1]);
    }

    // 计算第 2 到 n 题的期望
    for (int i = 1; i < n; i++) {
        expected_value += 1.0 / max(a[i], a[i - 1]);
    }

    cout << fixed << setprecision(15) << expected_value << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        double expectedValue = 0.0;

        // 计算第 1 题的期望
        if (n > 0) {
            expectedValue += 1.0 / Math.max(a[0], a[n - 1]);
        }

        // 计算第 2 到 n 题的期望
        for (int i = 1; i < n; i++) {
            expectedValue += 1.0 / Math.max(a[i], a[i - 1]);
        }

        System.out.printf("%.15f\n", expectedValue);
    }
}

import sys

def main():
    n = int(sys.stdin.readline())
    if n == 0:
        print(0.0)
        return
        
    a = list(map(int, sys.stdin.readline().split()))

    expected_value = 0.0

    # 计算第 1 题的期望
    expected_value += 1.0 / max(a[0], a[n - 1])

    # 计算第 2 到 n 题的期望
    for i in range(1, n):
        expected_value += 1.0 / max(a[i], a[i - 1])
        
    print(f"{expected_value:.15f}")

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学期望 + 概率计算
时间复杂度：只需要遍历一次输入的数组来累加概率，因此时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度：需要一个数组来存储每道题的选项数，空间复杂度为 $\mathcal{O}(N)$ 。