[SHOI2011] 扫雷机器人 题解

[SHOI2011] 扫雷机器人 题解

前言

显然，一个炸弹可以引爆另一个，而另一个炸弹却不一定能引爆这一个。

考虑假设炸弹一能引爆炸弹二，则建一条一到二的有向边。

推导过程

期望，就是平均值，也就是所有情况的权值总和除以情况总数的值。

可是，情况总数足足有n ! n!n!种，显然会超时到没边。

当你走投无路的时候，可以尝试化简式子。

令全部的引爆次数为c n t cntcnt，期望为a n s ansans，可以写出以下式子：

a n s = c n t n ! ans=\frac{cnt}{n!}ans=n!cnt​

考虑c n t cntcnt该如何计算。

考虑每个炸弹对于c n t cntcnt的贡献。

显然这个炸弹被手动引爆一次，那么c n t cntcnt就会多1 11。

考虑什么时候这个炸弹能够被手动引爆。

显然，每个炸弹都有若干个炸弹可以将其引爆，所以为了被手动引爆，这个炸弹的引爆时间必须在能引爆它的炸弹的前边。

令对于第i ii个炸弹，有k i k_iki​个炸弹可以将它引爆，为了方便计算，此处的k i k_iki​包含第i ii个炸弹本身。

显然第i ii个炸弹被手动引爆的概率s i s_isi​如下：
s i = 1 k i ! s_i=\frac{1}{k_i!}si​=ki​!1​
那么第i ii个炸弹能够被手动引爆的次数t i t_iti​为：
t i = 1 k i ! ⋅ n ! t_i=\frac{1}{k_i!}\cdot n!ti​=ki​!1​⋅n!
将这些式子代入计算期望的式子，得：
a n s = ∑ i = 1 n 1 k i ! ⋅ n ! n ! ans=\frac{\sum_{i=1}^n\frac{1}{k_i!}\cdot n!}{n!}ans=n!∑i=1n​ki​!1​⋅n!​
提取公因式，得：
a n s = n ! ⋅ ∑ i = 1 n 1 k i ! n ! ans=\frac{n!\cdot \sum_{i=1}^n\frac{1}{k_i!}}{n!}ans=n!n!⋅∑i=1n​ki​!1​​
化简，得：
a n s = ∑ i = 1 n 1 k i ! ans=\sum_{i=1}^n\frac{1}{k_i!}ans=i=1∑n​ki​!1​
这个式子就能计算了，但k i k_iki​该如何计算？

一下子就想到了拓扑排序。

可是可能存在环。

考虑使用 Tarjan 算法进行 缩点，再进行拓扑排序。

参考代码

#include<bits/stdc++.h>usingnamespacestd;structbomb{intx;intd;}a[4010];intn;bitset<4010>k[4010];vector<int>e[4010];set<int>b[4010];intlow[4010];intdfn[4010];intvis[4010];intd[4010];stack<int>s;intidx;vector<vector<int>>ans;intid[4010];voidTarjan(intx){s.push(x);low[x]=dfn[x]=++idx;vis[x]=1;for(inti:e[x]){if(!dfn[i]){Tarjan(i);low[x]=min(low[x],low[i]);}elseif(vis[i]){low[x]=min(low[x],dfn[i]);}}if(low[x]==dfn[x]){vector<int>q;while(s.top()!=x){autoh=s.top();s.pop();vis[h]=0;q.push_back(h);id[h]=ans.size();}s.pop();vis[x]=0;q.push_back(x);id[x]=ans.size();ans.push_back(q);}}intmain(){cin.tie(0)->sync_with_stdio(false);cin>>n;for(inti=1;i<=n;i++){cin>>a[i].x>>a[i].d;}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i^j&&a[i].x-a[i].d<=a[j].x&&a[i].x+a[i].d>=a[j].x){e[i].push_back(j);}}}for(inti=1;i<=n;i++){if(!dfn[i]){Tarjan(i);}}for(inti=0;i<ans.size();i++){for(intj:ans[i]){k[i][j]=1;for(intk:e[j]){if(i==id[k])continue;b[i].emplace(id[k]);}}}for(inti=0;i<ans.size();i++){for(intj:b[i]){d[j]++;}}queue<int>q;for(inti=0;i<ans.size();i++){if(!d[i])q.push(i);}while(!q.empty()){autoh=q.front();q.pop();for(inti:b[h]){k[i]|=k[h];d[i]--;if(!d[i])q.push(i);}}longdoublee=0.000000;for(inti=0;i<ans.size();i++){e+=(1.000000)/(k[i].count()*1.000000)*ans[i].size();}cout<<fixed<<setprecision(4)<<e;return0;}

如有错误，还请指出。

注. 我的洛谷账号即为 lonys，本篇文章同步在洛谷专栏发布。