题解 P1297 [国家集训队]单选错位

题意简述

小 \(G\) 参加了一次考试,一共有 \(n\) 题,每题一分。第 \(i\) 道题有 \(a_i\) 个选项,小 \(G\) 原定每道题随机选择一个选项,但是她写在答题卡上时,第 \(i\) 题的答案抄到了第 \(i+1\) 题上(第 \(n\) 题抄到了第一题),问小 \(G\) 的期望得分,保留三位小数。

\(1 \leq n \leq 10^7,1 \leq a_i \leq 10^8\)。

Solution

考虑第 \(i\) 题得分的期望,最后总的期望得分就是每一题的期望得分的和,设上一题的选项有 \(last\) 个。

  • 若 \(last>a_i\) ,则要先选中选项,概率为 \(\dfrac{a_i}{last}\) ,再从 \(a_i\) 个选项中选出正确答案概率是, \(\dfrac{1}{a_i}\) ,期望为 \(\dfrac{a_i}{last} \times \dfrac{1}{a_i} \times 1 = \dfrac{1}{last}\)。
  • 若 \(last < a_i\) ,那么正确答案要是 \(1\sim last\) 中的一个才有可能选对,概率是 \(\dfrac{last}{a_i}\) ,再从 \(last\) 选项中选出正确答案,概率是 \(\dfrac{1}{last}\)。期望为 \(\dfrac{last}{a_i} \times \dfrac{1}{last} \times 1=\dfrac{1}{a_i}\)。

综上,每一题得分的期望为 \(\dfrac{1}{\max\{last,a_i\}}\),答案就全部加起来就可以了。

代码如下:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e7 + 5;
int n ,A ,B ,C ,a[N]; double ans;
signed main() {
	scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
	for (int i = 2; i <= n; i++)
		a[i] = ((long long) a[i - 1] * A + B) % 100000001;
	for (int i = 1; i <= n; i++)
		a[i] = a[i] % C + 1;
	for (int i = 1; i < n; i++)
		ans += (double)1.0 / max(a[i] ,a[i + 1]);
	ans += (double)1.0 / max(a[n] ,a[1]);
	printf("%.3f\n" ,ans);
	return 0;
}
上一篇:聚类算法与K-means实现


下一篇:P2152 [SDOI2009]SuperGCD(模拟)