概率期望+闭包+bitset优化——hdu5036
2024-10-07 19:57:26
我们首先得到:
暴力打开这个箱子,能够开那些箱子。这个可以用bitset来进行状态压缩。
用闭包传递来解决这一步
然后,对于每个箱子,我们考虑有多少种方法,使:暴力打开某些箱子,同时能打开这个箱子。
暴力开这个箱子的期望就是方案数的倒数。然后我们对开每个箱子的期望求和就是最终的打开所有箱子暴力开箱子的数目的期望。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
bitset<>e[maxn];
int n,m; void floyd(){
for(int i=;i<=n;i++)//枚举中介点
for(int j=;j<=n;j++)
if(e[j][i]==)
e[j]|=e[i];
} int main(){
int t;cin>>t;
for(int tt=;tt<=t;tt++){
scanf("%d",&n);
for(int i=;i<=n;i++)e[i].reset(); for(int i=;i<=n;i++){
int k,x;scanf("%d",&k);
while(k--){
scanf("%d",&x);
e[i][x]=;
}
e[i][i]=;
} floyd(); double ans=;
for(int i=;i<=n;i++){
double tot=;
for(int j=;j<=n;j++)
if(e[j][i]==)tot+=;
ans+=1.0/tot;
}
printf("Case #%d: %.5lf\n",tt,ans);
}
}
最新文章
- C语言 &#183; 冒泡排序
- [转载]Js小技巧||给input type=“password”的输入框赋默认值
- 在express项目中有效组织和使用mongoose
- jquery ajax跨域请求详解
- postgresql编译安装与调试(二)
- Oracle 流式制造功能培训
- JVM - 内存溢出问题排查相关命令jcmd jmap
- linux下安装php的mcrypt拓展
- 笨方法学python--参数,解包,变量
- [STM32F429-DISCO-HAL]4.Uart 的使用
- 多租户通用权限设计(基于casbin)
- MySQL 5.7的多源复制
- spark组件笔记
- 002-自定义打开terminal,以及快捷键,其他程序类似,ssh管理-sshpass, Shuttle
- java依赖注入(injection)
- django-media隐射
- 【统一异常处理】@ControllerAdvice + @ExceptionHandler 全局处理 Controller 层异常
- php交叉合并数组
- 关于html5 audio 标签在ios系统上不能正常自动播放的解决办法
- django项目添加新的app