首页 > 其他分享 >agc049a-ti-jie

agc049a-ti-jie

时间:2024-05-08 18:23:04浏览次数:22  
标签:jie int siz sum ans maxn agc049a ti

agc049a

思路

期望。

CF280C 相似的思路。

每个点最多被做一次,或者被其他点影响。设 $f_i$ 表示 $i$ 是否被选,为 $0$ 或 $1$。答案为 $E[\sum f_i]$,即 $\sum f_i$ 的期望。

$$ans=E[\sum f_i]=\sum E[f_i]=\sum p_i$$

所以答案为每个点被选的概率的和。

能影响点 $i$ 使其不被选的点,是那些能到达 $i$ 的点,如果在 $i$ 之前被选,那么 $i$ 就不用选了。所以设 $siz$ 为能影响点 $i$ 的点数(包括自己),则 $p_i=\frac{1}{siz}$ 。

$n\leq100$ ,用 弗洛伊德 看一个点能去哪些点。

code

double n,ans,siz;
char c[maxn];
int e[maxn][maxn];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c+1;
		for(int j=1;j<=n;j++)e[j][i]=c[j]-'0';
	}
	for(int i=1;i<=n;i++)e[i][i]=1;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(e[i][k]&&e[k][j])e[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		siz=0;
		for(int j=1;j<=n;j++){
			if(e[i][j])++siz;
		}
		ans+=1.0/siz;
	}
	printf("%.10lf",ans);
}

标签:jie,int,siz,sum,ans,maxn,agc049a,ti
From: https://www.cnblogs.com/yhddd/p/18180556

相关文章

  • abc349g-ti-jie
    abc349g思路从前往后枚举$i$,每次对$i+1\lej\lei+a_i$的$j$赋值$b_j=b_{i\times2-j}$。同时有$b_{i+a_i+1}\neb_{i-a_i-1}$。用$ban_{i,j}$记录$i$不能是$j$,如果要给$i$赋值就选最小的。最直接的就是并查集倍增将两段区间并起来。可以用类似马拉车的思路得......
  • Elements in iteration expect to have 'v-bind:key' directives.
    当组件中使用v-for时,如果不指定key,则会有红色警告信息。解决方案如下。方案一:绑定key(亲试有效)//方式一<liv-for="(item,index)inlist":key="index">//方式二<liv-for="(item,index)inlist":key="item.id">//方式三<liv-for="(item,in......
  • GeometryCollection 的类型映射器(TypeHandler)
    byemanjusakafromhttps://www.emanjusaka.top/2024/05/mybatis-typeHandler-geometryCollection彼岸花开可奈何本文欢迎分享与聚合,全文转载请留下原文地址。GeometryCollection是GeoJSON数据模型中的一个类型,用于表示一个几何对象的集合。MySQL8中支持了GeometryCol......
  • 为什么在有@Transactional注解的方法,一定要加rollbackFor异常回滚的异常类型?
    在spring项目中,@Transactional注解默认会回滚运行时异常(RuntimeException)及其子类当你在一个有@Transactional注解方法里面抛了一个Expection类型的异常,呢它是不支持事务回滚的,异常继承体系我们在一个方法里面要对事务进行操作,如果要抛异常,应该抛出untimeException,不能直接......
  • spring刷题记录——to be continue
    在牛客网刷的题目,类似于补基础了?这里按照知识点进行分类,因为发现有些同样的知识点不同的题目还是很痛苦。这里就不用颜色标记了,因为我觉得都要记。Spring容器篇Spring容器也叫做Ioc容器(Ioc,在我之前写的随笔里面也有谈到),本质上就是一个工厂。Sp......
  • Windows下使用ONNXRuntime推理YOLOv8
    一、准备工作将训练好的pt文件转为onnx格式。yoloexportmodel=best.ptformat=onnxdevice=0opset=13dynamic#如果是动态Shape的话,命令行参数dydynamic一定要加上,不然就是static的模型二、下载与安装ONNXRuntime注意:下载安装onnxruntime-gpu时需要保证其与cuda的兼容......
  • c# Dictionary<TKey,TValue>.TryAdd
    原文链接:https://learn.microsoft.com/zh-cn/dotnet/fundamentals/code-analysis/quality-rules/ca1864Dictionary<TKey,TValue>.ContainsKey(TKey) 和 Dictionary<TKey,TValue>.Add 都执行查找操作,这是冗余设置。如果字典中已存在键,Dictionary<TKey,TValue>.Add 也会引发异......
  • Server-side vulnerabilities :path traversal
    来自bp的学院,提供了靶机,是个学习好地方服务器漏洞之路径遍历 就是说网站提供的图片,如果直接通过src="/loadImage?filename=xxx.jpg“读取的话,可以通过构造”filename=../../../etc/passwd"参数,拿到服务器的passwd文件,这样能读取服务器的用户放一个靶机地址:https://portswigg......
  • 【container】【docker-compose】【mysql】【redis】【rabbit mq】【mongo】【elastic
    @目录写在前面mysqlredisrabbitmqmongoelasticsearch单节点多节点参考资料dockerkuberneteshelmk3s写在前面相关博文个人博客首页免责声明:仅供学习交流使用!开源框架可能存在的风险和相关后果将完全由用户自行承担,本人不承担任何法律责任。mysqlversion:'3'services:......
  • sql server时间戳timestamp
    原文链接:https://www.cnblogs.com/hanke123/p/4741561.html在SQLServer中联机丛书是这样说的:SQLServertimestamp数据类型与时间和日期无关。SQLServertimestamp是二进制数字,它表明数据库中数据修改发生的相对顺序。实现timestamp数据类型最初是为了支持SQLServer恢......