自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:02:10，当前版本为作者最后更新于2022-08-05 22:32:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

洛谷 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;
}