洛谷 P3175 [HAOI2015]按位或
2024-10-20 08:42:57
题目分析
与hdu4336 Card Collector相似,使用min-max容斥。
设\(\max(S)\)表示集合\(S\)中最后一位出现的期望时间。
设\(\min(S)\)表示集合\(S\)中最初一位出现的期望时间。
由min-max容斥可得:
\(\max(T)=\sum\limits_{S \subseteq T}(-1)^{|T|-1}\min(S)\)
考虑求每一个\(\min(S)\)。
一个很显然的暴力代码:
for(int i=0;i<(1<<n);i++){
double tot=0;
for(int j=0;j<(1<<n);j++)if(i&j)tot+=p[j];
Min[i]=tot;
}
我们考虑对于每一个集合\(S\),实质上只有与它没有交集的数对它没有贡献。
那么我们可以用总贡献减去与它没有交集的数的贡献。
即对于每一个数,只需要对它的补集的子集全部减去它的贡献即可。
这个很显然能够\(O(nlogn)\)计算出来。
那么就做完啦。
#include <bits/stdc++.h>
using namespace std;
int n;
double p[(1<<20)+5],a[25];
int main(){
scanf("%d",&n);
for(int i=0;i<(1<<n);i++){
double x;
scanf("%lf",&x);
p[((1<<n)-1)^i]+=x;
for(int j=0;j<n;j++)
if(i&(1<<j))a[j]+=x;
}
for(int i=0;i<n;i++)if(!a[i]){puts("INF");return 0;}
for(int j=0;j<n;j++)
for(int i=0;i<(1<<n);i++)
if(i&(1<<j))p[i^(1<<j)]+=p[i];
for(int i=0;i<(1<<n);i++)p[i]=1-p[i];
double ans=0;
for(int i=1;i<(1<<n);i++){
int f=(__builtin_popcount(i)&1)?1:-1;
ans+=f/p[i];
}
cout<<fixed<<setprecision(7)<<ans<<"\n";
}
最新文章
- canvas-图片翻转
- go语言条件语句 if else
- sql server 警报管理,实时监听数据库动向,运筹帷幄之中
- 上下margin重叠传递问题
- CentOS配置FTP(VSFTPD)
- 树莓派 不稳定 ssh经常断 解决
- 判断文件是否为UTF8编码
- ELK初学搭建(kibana)
- Java 基础之 static 静态
- PHP上传文件大小的修改
- JAVA通过继承Thread来创建线程
- k8s滚动更新(六)--技术流ken
- springboot项目logback配置文件示例
- HTML DOM 節點
- 安装xcache3.0.3/3.2,为php加速
- cf789d 图论计数,自环闭环
- Spring学习之SpringMVC框架快速搭建实现用户登录功能
- VS2015 调试 条件和操作设置
- 『科学计算』科学绘图库matplotlib练习
- hdu 4549 矩阵快速幂
热门文章
- 【c++】iostreeam中的类为何不可以直接定义一个无参对象呢
- 深入redis内部--初始化服务器
- [PY3]——创建多值映射字典?/defaultdict默认字典/setdefault()
- jQuery 整体架构
- easyui前后台转义字符和普通字符的相互转换问题
- kafka-php
- How WindowLeaked exception occured?
- Effective C++ .07 virtual析构函数的提供
- csharp: Aspose.Words create table
- Eclipse常用操作