专栏文章

CF513C Second price auction 题解

MMoya_Rao啾？啾！
CF513C题解参与者 4已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@mioxqke5
此快照首次捕获于
2025/12/03 02:52
3 个月前
此快照最后确认于
2025/12/03 02:52
3 个月前
查看原文
upd on 2025.11.14 根据要求删除部分“喵”语气词。
题解区怎么只有一篇题解喵。既然这样，本喵也来水一篇！
本喵对数据范围特别敏感，敏锐地发现 nn 只有 55！小到离谱对吧。就连 LiL_i 和 RiR_i 也只有 10410^4 喵。
既然数据范围这么小，不妨大胆一点。上来就枚举这个最终出价！但是这样不好做喵。
所以稍微修一下定义：并非最终出价恰好为 xx，而是最终出价不低于 xx。
求出来一系列数存进 ss 数组后，照样还是可以算出最终出价恰好为 xx 的概率！sx+1−sxs_{x+1} - s_x 就好了。
所以最终答案的计算方式就定下来了喵！
但是这个 ss 究竟该怎么求？
别急，咱们还没请出终极嘉宾——概率 DP！
反正 nn 小，随便乱搞。定义 dpi,jdp_{i,j} 表示前 ii 个人出了价，其中有 jj 个人的出价不低于我们当前枚举的价格 xx。
接下来就是转移了喵。
为了进行转移，我们需要知道第 ii 个人的出价不低于 xx 的概率。该怎么算？很显然的，就是 Ri−max⁡(Li,x)+1Ri−Li+1\dfrac { R_i - \max( L_i , x ) + 1 } { R_i - L_i + 1 } 。究其根源，不过是简单计算了一下在 [Li,Ri][L_i,R_i] 这个区间中有多少个数不低于 xx 。但是要注意，当 xx 很大的时候，Ri−max⁡(Li,x)+1R_i-\max(L_i,x)+1 可能变成负数，记得和 00 取一下 max⁡\max 再进行计算。
令 PP 为上面那个东西喵。
那么转移就显而易见了，枚举每个 jj 从 00 到 ii，转移式就是 dpi,j=dpi−1,j×P+dpi−1,j×(1−P)dp_{i,j} = dp_{i-1,j} \times P + dp_{i-1,j} \times (1 - P) ，非常显然喵。
那么我们的一轮 DP 就结束了喵！
但是 ss 呢？我们进行这个概率 DP 的目的是求出 sxs_x！对啊，所以进行完 DP 以后，咱枚举 ii 从 22 到 nn（出价高于 xx 的至少要有 22 人，不然最终价就只能低于 xx 了），让 sxs_x 加上所有 dpn,idp_{n,i} 就行了！
ss 求出来了，后面就只需要加和计算一下就行了。
所以总的来说还是非常简单的，代码也很短喵：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 1e4+5;
int n,m,l[N],r[N];
long double dp[N][N],s[M],ans;
int main(){
    cin>>n;dp[0][0]=1.0;
    for(int i=1;i<=n;i++){cin>>l[i]>>r[i];m=max(m,(int)(r[i]));}
    for(int x=1;x<=m;x++){
        for(int i=1;i<=n;i++){
            long double P=1.0*max(r[i]-max(l[i],x)+1,0)/(r[i]-l[i]+1);
            for(int j=0;j<=i;j++)dp[i][j]=dp[i-1][j-1]*P+dp[i-1][j]*(1.0-P);
        }
        for(int i=2;i<=n;i++)s[x]+=dp[n][i];
    }
    for(int x=1;x<=m;x++)ans+=(s[x]-s[x+1])*x;
    printf("%.10Lf",ans);
    return 0;
}
既然都看到这里了，给本喵留个赞好不好？求你了喵！

评论

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

正在加载评论...