题解：P11918 [PA 2025] 考试 / Egzamin

· · 题解

首先 p 从大到小排序，贪心来看每次作答的必然是前缀。

于是设 dp(i,j) 表示当前答前 i 个题获得 j 分的概率。

转移显然为 dp(i,j)=dp(i-1,j-1)p_{i-1}+dp(i-1,j+1)(1-p_{i-1})。可以做到 O(n^2)。

发现有很多 dp(i,j) 都很小，我们不妨只对 dp(i,j)>\epsilon 转移。

本题中，每道题的得分服从两点分布，方差可以视为常数。根据中心极限定理，总得分应服从正态分布。

如果你不会很多概率论知识，我们可以用人教版数学选择性必修三的内容解释。数学书上提到了 3\sigma 原则——对于均值为 \mu、方差为 \sigma^2 的正态分布，绝大部分样本都落在 [\mu-3\sigma,\mu+3\sigma] 的地方。由于每道题得分的方差视为常数，故总得分服从的正态分布的方差 \sigma^2=O(n)，也就是绝大部分样本落在的区间长度约为 O(\sqrt n)。

如果你学过概率论，你应该听说过切尔诺夫引理。具体内容比较复杂就不展开了，这个引理表明 >\epsilon 的样本落在的区间长度为 O(\sqrt{-n\log\epsilon})。故时间复杂度为 O(n\sqrt{-n\log\epsilon})。如果把精度视为常数，这和上面使用高中课本知识推出来的吻合。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN=5e4+1;
const double EPS=1e-12;
int n,t;
double p[MAXN],ans[MAXN]; 
__gnu_pbds::cc_hash_table<int,double>dp[2];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>t;
    F(i,1,n) cin>>p[i];
    sort(p+1,p+n+1,greater<double>());
    dp[0][n]=1;
    F(i,0,n-1){
        int now=i&1,nxt=now^1;
        dp[nxt].clear();
        for(auto qwq:dp[now]) if(qwq.se>EPS){
            if(qwq.fi>=n+t) ans[i]+=qwq.se;
            dp[nxt][qwq.fi+1]+=qwq.se*p[i+1];
            dp[nxt][qwq.fi-1]+=qwq.se*(1-p[i+1]);
        }
    }
    for(auto qwq:dp[n&1]) if(qwq.se>EPS) if(qwq.fi>=n+t) ans[n]+=qwq.se;
    double res=0;
    F(i,1,n) res=max(res,ans[i]);
    cout<<fixed<<setprecision(10)<<res;
    return 0;
}