HDU5036(bitset加速传递闭包+期望)
2024-09-06 21:20:08
HDU5036 题解
思路:
求出破坏or打开所有门所需要的期望炮弹数量,那么根据期望的线性性质,我们可以求出每一个门的期望值最后累加起来就行了。
我们最后的目标就是求对于一个门\(i\),有多少门可以到达\(i\),假设有\(s\)个门(包含\(i\)),那么\(E_i=1*\frac{1}{s}\)。
那么我们就需要知道如果打开一个门,还能打开什么其它的门,这有点类似于传递闭包,但这题\(n\)最高有1000,这里我们用\(bitset\)加速一下就好了。这里的floyd还是挺有意思的,可以仔细琢磨一下。
代码如下:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef long long ll;
const int N = 1005;
int T;
int n;
bitset <N> d[N];
int main() {
cin >> T;
for(int Case = 1; Case <= T; Case++) {
scanf("%d", &n) ;
for(int i = 1; i <= n; i++) d[i].reset() ;
for(int i = 1, k; i <= n; i++) {
scanf("%d", &k);
d[i].set(i) ;
for(int j = 1, x; j <= k; j++) {
scanf("%d", &x) ;
d[x].set(i) ;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(d[j].test(i)) d[j] |= d[i] ;
double ans = 0;
for(int i = 1; i <= n; i++) ans += 1.0 / d[i].count() ;
printf("Case #%d: %.5f\n", Case, ans) ;
}
return 0;
}
最新文章
- 创业15条经验总结:温饱之后,创业公司CEO如何树“三观”?
- true是表示使用身份验证,否则不使用身份验证
- 20145208 《Java程序设计》第6周学习总结
- CoreCLR源码探索(二) new是什么
- 复制、移动和删除:cp, rm, mv
- 计算机管理cmd命令行
- 【IOS开发】UItextfield输入电话号码,自动调整格式
- Java线程间通信
- Dynamics CRM2016 Web Api之分页查询
- java 保留字段volatile、transient、native、synchronized
- 21.命名空间别名限定符::和global全局名称空间限定符
- PAT—优化Java从控制台读取信息的速度
- webpack学习笔记(六)优化
- TomCat 再次发布我的程序
- 步步为营-17-FileStream-文件加密/解密
- js实现截取或查找字符串中的子字符串
- ubuntu16.4菜单栏不见,终端不见解决方法
- eclipse debug Liunx服务器上的svn项目
- html打造动画【系列2】- 可爱的蛙蛙表情
- dvwa 源码分析(四) --- dvwaPhpIds.inc.php分析
热门文章
- 使用vue搭建应用五引入Mock.js
- Solr7.x学习(8)-使用spring-data-solr
- jquery的Layer弹出框操作
- nginx返回file not found原因
- linux免费https证书申请教程
- vue-cli中的element-ui的主题更改
- 连上Microbit板
- java ---- 认识类和对象
- 026 Elastic----全文检索技术01---概述及windows安装
- RuntimeError: Model class myapp.models.Test doesn&#39;t declare an explicit app_label and isn&#39;t in an application in INSTALLED_APPS.