HDU 5036 Explosion （2014年北京赛区网络赛E题）
发布时间
阅读量：
阅读量
题目描述：点击打开链接
解题思路：本题通过期望值的可加性特性来解决概率计算问题。具体而言，在计算所有扇门均能抵达的概率时，默认各扇门之间可达事件相互独立。假设有k扇门均可达目标u号扇门，则由于每次只能选择一个扇门抵达u号扇门（即只能选择其中一个），因此可推断出目标u被抵达的概率为1/k。为了高效确定哪些扇门能够抵达目标扇门u号位置，请问是否有一种有效的方法？一种可行的方式就是利用STL中的bitset结构特点：它能够并行处理n位数据，并且支持快速执行逻辑或运算操作（如按位或运算）。这样一来，在计算过程中只需对每个位置执行或操作即可快速确定哪些扇门外可达目标点位置。这样整个算法的时间复杂度就降到了O(N^2)。
3.代码：
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<complex>
#include<functional>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define me(s) memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;
const int N=1005;
bitset<N>bs[N];
int main()
{
int T;
scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
bs[i].reset();
bs[i][i]=1;
}
int num,v;
for(int i=0;i<n;i++)
{
scanf("%d",&num);
while(num--)
{
scanf("%d",&v);v--;
bs[i][v]=1;
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(bs[j][i])
bs[j]|=bs[i];
double ans=0;
for(int i=0;i<n;i++)
{
int cnt=0;
for(int j=0;j<n;j++)
if(bs[j][i])cnt++;
ans+=1.0/cnt;
}
printf("Case #%d: %.5lf\n",kase,ans);
}
}全部评论 (0)
还没有任何评论哟~