题解：P15932 [TOPC 2021] Drunk Passenger

smalbug · 2026-07-24 11:39:34 · 题解

蒟蒻又能写题解了嘿嘿嘿齁齁齁齁齁齁齁齁。。

分析

六百六十六数据范围这么小还分析什么 O(1) 公式，这个人直接开始定义 dp 如下

那么对于第 i 人，他的座位有 dp_i 的概率被占，于是他去炸座。
剩下 n-i+1 个座位有相等的概率被他占（当然第一个大聪明特判），
所以我们给满足 i<j<=n 的 dp_j 加上 \frac{1}{n-i+1} 然后就结束了。
复杂度 O(n^2) 可以通过本题。
Of course 进行数学推导也是可以得到 ans = \frac{n}{2 \times (n - 1)} 的喵。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
double dp[350];
int main(){
    cin>>n;
    dp[1]=1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            dp[j]+=dp[i]*(double)1/(n-i+(i!=1));
        }
    }
    printf("%.10f",dp[n]);
    return 0;
}