题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。
思路：状态压缩。用一个二进制串表示每扇门能打开的门的信息，对应的位上为1表示能打开，为0表示不能打开。
状态是可以传递的。。
如果第i扇门能打开门k，那么能打开第i扇门的第j扇门也可以打开门k。
状态压缩以及传递的过程可以很容易用bitset来维护，这才是bitset的正确打开姿势
相当于用floyd做了一个传递闭包。(floyd的有一层循环隐藏在了bitset中，复杂度没有改变，但是常数小)
最后对于期望的计算方法：统计能打开第i扇门的方案数计为cnt,这cnt的方案中，只有一种是用炸弹炸掉，因此用的炸弹数的期望数为1/cnt
由于期望的独立性，因此打开所有门所有的炸弹数的期望就是每个门的期望累加。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
/* *********************************************** Author :111qqz Created Time :2016年08月21日 星期日 18时43分56秒 File Name :code/hdu/5036.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <deque> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <bitset> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1005; int n; bitset<N>b[N]; //b[i]表示第i扇门可以打开的门 int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif int T; cin>>T; int cas = 0 ; while (T--) { printf("Case #%d: ",++cas); scanf("%d",&n); for ( int i = 0 ; i <= n ; i++) { b[i].reset(); b[i].set(i); //第i扇门可以炸开自己。。。 } for ( int i = 0 ; i < n; i++) { int num; scanf("%d",&num); while (num--) { int x; scanf("%d",&x); x--; b[i].set(x); } } for ( int i = 0 ; i < n ; i++) //枚举能打开第i扇门的门j，因为能开的门可以传递，所以门j可以通过打先开门i去开门i能开的门。 for ( int j = 0 ; j < n ; j++) if (b[j][i]) b[j]|=b[i]; //依然是floyd，这里或运算的复杂度是n，只不过常数小。相当于做了一个传递闭包。 double ans = 0 ; for ( int i = 0 ; i < n ; i++) //统计能打开门i的方案数为cnt(cnt至少为1)，那么cnt中一种是炸开门，剩下cnt-1种是其他方式开门。 { //因此第i扇门用炸弹炸开的期望就是1/cnt. 由于期望的独立性。答案把所有门累加即可。 int cnt = 0 ; for ( int j = 0 ; j < n ; j++) if (b[j][i]) cnt++; ans +=1.0/cnt; } printf("%.5f\n",ans); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！