洛谷 P4637 题解

· · 题解

洛谷 P4637 题解

\text{Link}

思路分析

非常强的思维题，推理过程相当精彩

考虑求出期望的过程：

  1. 每种引爆地雷的顺序，共有 n! 种情况
  2. 对于每种顺序，计算出其中实际引爆的地雷个数，也就是所有没有在之前被引爆的地雷个数
  3. 将每种方案中实际引爆的地雷个数当成操作次数，乘上概率 \dfrac1{n!}，求和计算期望

由于期望具有线性性，所以我们可以考虑计算每个地雷对答案的贡献，也就是说，对于每个地雷，求出其会在多少种方案中被实际引爆

求出所有可以导致第 i 个地雷被引爆（直接或间接）的地雷集合，设为 \mathbf S_i，那么 i 第一个被引爆，当且仅当所有 \mathbf S_i 中的地雷都在 i 之后被引爆，

所以问题就转化成了：对于第 i 个元素，求出在所有排列中，满足 i 是 \mathbf S_i 中所有元素里的第一个的情况总数

由于其他的元素在哪里并不重要，所以我们只需要考虑 \mathbf S_i 中的元素之间的相对关系，不难得到满足 i 恰好是其中第一个数的方案数占所有方案数的比例为：\dfrac{(|\mathbf S_i|-1)!}{|\mathbf S_i|!}=\dfrac{1}{|\mathbf S_i|}，因此在所以排列中，第 i 颗地雷被实际引爆的次数应该是 \dfrac{n!}{|\mathbf S_i|} 次，这也是第 i 颗地雷对答案的贡献

套用期望的计算公式可以得到：

\begin{aligned} \text{Answer} &=\dfrac{1}{n!}\sum_{i=1}^n\dfrac{n!}{|\mathbf S_i|}\\ &=\sum_{i=1}^n\dfrac1{|\mathbf S_i|} \end{aligned}

所以问题就转化成求所有的 |\mathbf S_i|

可以将所有地雷向其能够直接引爆的点连一条边，我们需要求出对于每个点 i，有多少个点能够到达 i

考虑缩点，在 DAG 上做拓扑排序转移一个用 bitset 维护的 \mathbf S_i 即可

注意:如果我们直接在原图上做 n 次 BFS，复杂度在完全图上会退化到 \Theta(n^3)

时间复杂度 \Theta(n^2)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4001;
int p[MAXN],d[MAXN];
vector <int> edge[MAXN],g[MAXN];
bool vis[MAXN];
bitset <MAXN> f[MAXN];
int low[MAXN],dfn[MAXN],dfncnt,sk[MAXN],siz[MAXN],bel[MAXN],deg[MAXN],top,scc;
bool ins[MAXN],link[MAXN][MAXN];
inline void tarjan(int p) {
    low[p]=dfn[p]=++dfncnt;
    ins[p]=true; sk[++top]=p;
    for(int v:edge[p]) {
        if(!dfn[v]) {
            tarjan(v);
            low[p]=min(low[p],low[v]);
        } else if(ins[v]) low[p]=min(low[p],low[v]);
    }
    if(low[p]==dfn[p]) {
        ++scc;
        int k;
        do {
            k=sk[top--];
            bel[k]=scc;
            f[scc].set(k);
            ++siz[scc];
            ins[k]=false;
        } while(k!=p);
    }
}
signed main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&p[i],&d[i]);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            if(abs(p[i]-p[j])<=d[i]) {
                edge[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;++i) {
        for(int j:edge[i]) {
            if(bel[i]==bel[j]||link[bel[i]][bel[j]]) continue;
            g[bel[i]].push_back(bel[j]);
            link[bel[i]][bel[j]]=true;
            ++deg[bel[j]];
        }
    }
    queue <int> q;
    for(int i=1;i<=scc;++i) {
        if(!deg[i]) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int p=q.front();
        q.pop();
        for(int v:g[p]) {
            f[v]|=f[p];
            --deg[v];
            if(!deg[v]) q.push(v);
        }
    }
    double res=0;
    for(int i=1;i<=n;++i) res+=1.0/((int)f[bel[i]].count());
    printf("%.4lf\n",res);
    return 0;
}