专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip6o24y
此快照首次捕获于
2025/12/03 07:02
3 个月前
此快照最后确认于
2025/12/03 07:02
3 个月前
查看原文
背景知识请先阅读 https://www.luogu.com.cn/article/xs2uucwg
有 nn 个随机变量 X1,X2,…,XnX_1,X_2,\ldots,X_n，其中 XiX_i 有 pip_i 的概率为 11，否则为 −1-1。你选择一个 kk，再选择其中的 kk 个随机变量，求最优决策下你选择的随机变量的和 ≥t\ge t 的概率。
1≤t≤n≤500001 \le t \le n \le 50000，误差在 10−610^{-6} 以内。
首先，可以贪心地选随机变量，因为希望和尽可能大，所以优先选 pip_i 大的随机变量。
将所有 pip_i 排完序后，最终答案一定是一段前缀。
可以设计一个简单的 DP，记 fi,jf_{i,j} 为选长度为 ii 的前缀，和为 jj 的概率。
每一次和只会 +1+1 或者 −1-1，则有转移式：
fi,j=pi⋅fi−1,j−1+(1−pi)⋅fi−1,j+1f_{i,j}=p_i \cdot f_{i-1,j-1} + (1-p_i) \cdot f_{i-1,j+1}
这样做是 Θ(n2)\Theta(n^2) 的。
考虑优化，令 ε\varepsilon 为误差，我们断言，对于每一个 ii，使得 fi,j>εf_{i,j} > \varepsilon 的位置不会很多。
转移时只需舍去 fi,j≤εf_{i,j} \le \varepsilon 的状态，精细实现即可通过本题。
下面给出这个做法的复杂度证明。
考虑对于每一个 ii 分析复杂度。事实上，事件 {\{所有随机变量取值为 −1-1 或 11，且和 ≥t}\ge t\} 等价于事件 {\{所有随机变量取值为 00 或 11，且和 ≥i+t2}\ge \frac{i+t}{2}\}，这样我们就把问题转化为了若干次的 Bernoulli\text{Bernoulli} 分布，此时和的期望 μ=∑k=1ipi\mu=\sum \limits_{k=1}^{i} p_i。
容易注意到的是，满足 fi,j>εf_{i,j} > \varepsilon 的 jj 应该是一段连续区间，不妨设这一段区间为 [(1−B1)μ,(1+B2)μ][(1-B_1)\mu,(1+B_2)\mu]，且 B1,B2>0B_1,B_2>0。
代入 Multiplicative Chernoff Bound\text{Multiplicative Chernoff Bound} 可以得到：
Pr(X≥(1+B2)μ)≤e−B22μB2+2≤ε\textbf{Pr}\big(X \ge (1+B_2) \mu \big) \le e^{-\frac{B_2^2 \mu}{B_2+2}} \le \varepsilon
Pr(X≤(1−B1)μ)≤e−B12μ2≤ε\textbf{Pr}\big(X \le (1-B_1) \mu \big) \le e^{-\frac{B_1^2 \mu}{2}} \le \varepsilon
不等式两边同时取对数的相反数：
B22μB2+2≥ln⁡ε−1\frac{B_2^2 \mu}{B_2+2} \ge \ln \varepsilon^{-1}
B12μ2≥ln⁡ε−1\frac{B_1^2 \mu}{2} \ge \ln \varepsilon^{-1}
解二次不等式组得：
B2≥ln⁡ε−1+ln⁡2ε−1−8μln⁡ε−12μB_2 \ge \frac{\ln \varepsilon^{-1} + \sqrt{\ln^2 \varepsilon^{-1}-8\mu \ln \varepsilon^{-1}}}{2\mu}
B1≥2ln⁡ε−1μB_1 \ge \sqrt{\frac{2\ln \varepsilon^{-1}}{\mu}}
舍去常数，由于 0≤μ≤i0 \le \mu \le i，所以可以视为 n,μn,\mu 同阶，且 ln⁡ε−1\ln \varepsilon^{-1} 相对于 nn 是小量，所以：
B1,B2≥ln⁡ε−1nB_1,B_2 \ge \sqrt{\frac{\ln \varepsilon^{-1}}{n}}
取等号时最优，得到满足条件的区间为 [μ−nln⁡ε−1,μ+nln⁡ε−1][\mu - \sqrt{n \ln \varepsilon^{-1}},\mu + \sqrt{n \ln \varepsilon^{-1}}]，即对于每个 ii，合法状态数为 Θ(nln⁡ε−1)\Theta(\sqrt{n \ln \varepsilon^{-1}}) 个。
综上，总时间复杂度为 Θ(nnln⁡ε−1)\Theta(n \sqrt{n \ln \varepsilon^{-1}})。
经过测试，实际 ε\varepsilon 的值大约取到 10−1110^{-11}，此时总时间复杂度不超过 6×1076 \times 10^7。
核心代码：
C
constexpr int N=5e4+5;
constexpr double eps=1e-11;
namespace Junounly
{
    int n,K;
    double p[N];
    vector<pair<int,double> > q[2];
    void main()
    {
        scanf("%d%d",&n,&K);
        for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
        sort(p+1,p+n+1,greater<double>());
        q[0].emplace_back(0,1);
        double res=0;
        for(int i=1,op=0;i<=n;i++,op^=1)
        {
            for(auto [X,Y]:q[op])
            {
                int x=X-1;double y=Y*(1-p[i]);
                if(y>eps)
                {
                    if(q[op^1].size()&&q[op^1][q[op^1].size()-1].first==x) q[op^1][q[op^1].size()-1].second+=y;
                    else if(q[op^1].size()>1&&q[op^1][q[op^1].size()-2].first==x) q[op^1][q[op^1].size()-2].second+=y;
                    else q[op^1].emplace_back(x,y);
                }
                x=X+1;y=Y*p[i];
                if(y>eps) q[op^1].emplace_back(x,y);
            }
            q[op].clear();
            double now=0;
            for(auto [X,Y]:q[op^1])
                if(X>=K) now+=Y;
            res=max(res,now);
        }
        printf("%.11lf\n",res);
    }
}

评论

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

正在加载评论...