Explosion
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 259 Accepted Submission(s): 67
Problem Description
Everyone knows Matt enjoys playing games very much. Now, he is playing such a game. There are N rooms, each with one door. There are some keys(could be none) in each room corresponding to some doors among these N doors. Every key can open only one door. Matt has some bombs, each of which can destroy a door. He will uniformly choose a door that can not be opened with the keys in his hand to destroy when there are no doors that can be opened with keys in his hand. Now, he wants to ask you, what is the expected number of bombs he will use to open or destroy all the doors. Rooms are numbered from 1 to N.
Input
The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.
In the first line of each test case, there is an integer N (N<=1000) indicating the number of rooms.
The following N lines corresponde to the rooms from 1 to N. Each line begins with an integer k (0<=k<=N) indicating the number of keys behind the door. Then k integers follow corresponding to the rooms these keys can open.
In the first line of each test case, there is an integer N (N<=1000) indicating the number of rooms.
The following N lines corresponde to the rooms from 1 to N. Each line begins with an integer k (0<=k<=N) indicating the number of keys behind the door. Then k integers follow corresponding to the rooms these keys can open.
Output
For each test case, output one line "Case #x: y", where x is the case number (starting from 1), y is the answer which should be rounded to 5 decimal places.
Sample Input
2
3
1 2
1 3
1 1
3
0
0
0
Sample Output
Case #1: 1.00000
Case #2: 3.00000
题意:
给出 T 组 case,后给出 N 个房间,后有 N 行,第 i 行代表打开 i 号门后拥有的钥匙有什么,首先给出 K 代表有 K 条钥匙,后给出 K 条钥匙是什么。如果没有钥匙能打开这扇门则可以用 boom 炸开它,求能打开所有门所有 boom 数的数学期望。
思路:
统计 S 表示该扇门能被打开的房间总数有多少个,则 1 / S 则表示这扇门能被打开的概率,则 Sum { 1 / Si (1 <= i <= n ) } 即为所求。则题目转化为求传递闭包问题,用 bitset 优化可节省时间。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <bitset> using namespace std; const int VMAX = 1005; bitset<VMAX> Map[VMAX]; double res; int n; void floyd () { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (Map[j][i]) Map[j] |= Map[i]; } } for (int i = 1; i <= n; ++i) { int ans = 0; for (int j = 1; j <= n; ++j) { if (Map[j][i]) ++ans; } res += 1.0 / (double) ans; } } int main() { int t; scanf("%d", &t); for (int tt = 1; tt <= t; ++tt) { scanf("%d", &n); res = 0; for (int i = 1; i <= n; ++i) { Map[i].reset(); Map[i][i] = 1; } for (int i = 1; i <= n; ++i) { int ans; scanf("%d", &ans); while (ans--) { int j; scanf("%d", &j); Map[i][j] = 1; } } floyd(); printf("Case #%d: %.5lf\n", tt, res); } return 0; }
相关推荐
Unity中使用的插件,仅供个人开发者使用,希望能帮助大家!
unity3d 游戏插件 Mesh Explosion 物体破碎特效
explosion.unitypackage爆炸的unity的资源,增加学习的。。。。。
Make it pop with iMG's Explosion FX package! Ten high quality animation texture sheets with alpha channel. Make your project stand out from the masses with stunning fire, smoke and explosion ...
指标Waddah Attar Explosion。
unity3d 游戏插件 Mesh Explosion 物体破碎特效资源包
物体破碎特效插件Mesh Explosion14,亲测2018.4.7无报错
unity3d 火焰爆炸特效 Realistic Fire Explosion Pack 1.2 最新 Requires Unity 5.0.2 or higher.
Unity3d特效粒子 爆炸合集特效包 Explosion Volume1!!!部分特效包,代码可能比较老!!!!
Toon Explosion Volume 1是一款精美多变的精灵表动画包!(核爆炸,火灾爆炸,分解爆炸,烟雾......) 你可以在各种各样的项目中使用它们(粒子发射器,2D游戏,其他......)。 图片以PNG格式(2048x2048 32 => 64帧...
Mega cool nuclear blast! Also blast have shock wave!. YOU NEED IMPORT POST PROCESS STACK FOR ENABLE PROFILE POWERFUL DX11 SHADER FOR PC & CONSOLE SHOCK WAVE ( IN SONIC SPEED) ...COMPLETE SETTING ...
Mesh Explosion.rar
xpaider pixel explosion 01
xpaider pixel explosion 02
Ians Explosion Pack特效包
explosion_underground.k
This volcanic disaster environment will provide you with a breathtaking landscape atmosphere. Resources include: -1 Volcanoes -3 Meteorite special effect -1 Fog effects -1 Smoke ...
GAS EXPLOSION HANDBOOK 中文机器翻译
explosion_in_water.k
The Biointelligence Explosion 生物智能爆炸式增长