CF513C Second price auction 题解
Moya_Rao
·
·
题解
upd on 2025.11.14 根据要求删除部分“喵”语气词。
题解区怎么只有一篇题解喵。既然这样，本喵也来水一篇！
本喵对数据范围特别敏感，敏锐地发现 n 只有 5！小到离谱对吧。就连 L_i 和 R_i 也只有 10^4 喵。
既然数据范围这么小，不妨大胆一点。上来就枚举这个最终出价！但是这样不好做喵。
所以稍微修一下定义：并非最终出价恰好为 x，而是最终出价不低于 x。
求出来一系列数存进 s 数组后，照样还是可以算出最终出价恰好为 x 的概率！s_{x+1} - s_x 就好了。
所以最终答案的计算方式就定下来了喵！
但是这个 s 究竟该怎么求？
别急，咱们还没请出终极嘉宾——概率 DP！
反正 n 小，随便乱搞。定义 dp_{i,j} 表示前 i 个人出了价，其中有 j 个人的出价不低于我们当前枚举的价格 x。
接下来就是转移了喵。
为了进行转移，我们需要知道第 i 个人的出价不低于 x 的概率。该怎么算？很显然的，就是 \dfrac { R_i - \max( L_i , x ) + 1 } { R_i - L_i + 1 } 。究其根源，不过是简单计算了一下在 [L_i,R_i] 这个区间中有多少个数不低于 x 。但是要注意，当 x 很大的时候，R_i-\max(L_i,x)+1 可能变成负数，记得和 0 取一下 \max 再进行计算。
令 P 为上面那个东西喵。
那么转移就显而易见了，枚举每个 j 从 0 到 i，转移式就是 dp_{i,j} = dp_{i-1,j} \times P + dp_{i-1,j} \times (1 - P) ，非常显然喵。
那么我们的一轮 DP 就结束了喵！
但是 s 呢？我们进行这个概率 DP 的目的是求出 s_x！对啊，所以进行完 DP 以后，咱枚举 i 从 2 到 n（出价高于 x 的至少要有 2 人，不然最终价就只能低于 x 了），让 s_x 加上所有 dp_{n,i} 就行了！
所以总的来说还是非常简单的，[代码](https://codeforces.com/contest/513/submission/328331491)也很短喵：
```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;
}
```
既然都看到这里了，给本喵留个赞好不好？求你了喵！