首页 > 代码库 > 【BZOJ】2134: 单选错位

【BZOJ】2134: 单选错位

2024-11-03 02:05:02   208人阅读

【算法】期望DP

【题意】有n道题，第i道题有ai个选项。一个人把所有的正确答案填到了后面一题上（特殊的，当i=n的时候填到1上），问他期望做对几道题？

【题解】每道题的期望与其他题目的期望无关。

对于每道题，有ai-1个可能的选项，ai个可能正确选项，共有ai-1ai种组合，其中只有Min(ai-1,ai)种组合是正确的，则期望是E[i]=Min(ai-1,ai)/ai-1ai=1/Max(ai-1,ai)。

E(x)=ΣE[i]（线性）

技术分享 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000000;
int n,a[maxn];
int main()
{
    int A,B,C;
    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; 
    a[0]=a[n];
    double ans=0;
    for(int i=1;i<=n;i++)ans+=1.0/max(a[i],a[i-1]);
    printf("%.3lf",ans);
    return 0;
}
View Code

 

【BZOJ】2134: 单选错位


联系
我们