专栏文章

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

llittlez_meow
P11918题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipks2eu
此快照首次捕获于
2025/12/03 13:37
3 个月前
此快照最后确认于
2025/12/03 13:37
3 个月前
查看原文
首先 pp 从大到小排序，贪心来看每次作答的必然是前缀。
于是设 dp(i,j)dp(i,j) 表示当前答前 ii 个题获得 jj 分的概率。
转移显然为 dp(i,j)=dp(i−1,j−1)pi−1+dp(i−1,j+1)(1−pi−1)dp(i,j)=dp(i-1,j-1)p_{i-1}+dp(i-1,j+1)(1-p_{i-1})。可以做到 O(n2)O(n^2)。
发现有很多 dp(i,j)dp(i,j) 都很小，我们不妨只对 dp(i,j)>ϵdp(i,j)>\epsilon 转移。
本题中，每道题的得分服从两点分布，方差可以视为常数。根据中心极限定理，总得分应服从正态分布。
如果你不会很多概率论知识，我们可以用人教版数学选择性必修三的内容解释。数学书上提到了 3σ3\sigma 原则——对于均值为 μ\mu、方差为 σ2\sigma^2 的正态分布，绝大部分样本都落在 [μ−3σ,μ+3σ][\mu-3\sigma,\mu+3\sigma] 的地方。由于每道题得分的方差视为常数，故总得分服从的正态分布的方差 σ2=O(n)\sigma^2=O(n)，也就是绝大部分样本落在的区间长度约为 O(n)O(\sqrt n)。
如果你学过概率论，你应该听说过切尔诺夫引理。具体内容比较复杂就不展开了，这个引理表明 >ϵ>\epsilon 的样本落在的区间长度为 O(−nlog⁡ϵ)O(\sqrt{-n\log\epsilon})。故时间复杂度为 O(n−nlog⁡ϵ)O(n\sqrt{-n\log\epsilon})。如果把精度视为常数，这和上面使用高中课本知识推出来的吻合。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...