首页 > 其他分享 >题解:AT_abc194_d [ABC194D] Journey

题解:AT_abc194_d [ABC194D] Journey

时间:2024-03-12 20:55:46浏览次数:36  
标签:frac int 题解 abc194 Journey ABC194D

题意简述

有一张 \(n\) 个节点的无边图,图在连通之前每次随机抽取一个点然后建边,求期望操作次数(即最大多少次)。

思路

这道题似乎和图论没什么关系,首先我们看 \(n\) 个球抽出一个的概率是 \(\frac{1}{n}\) ,那么抽第二个时概率是 \(\frac{1}{n-1}\) 以此类推。所以最坏情况下就是抽第 \(n-1\) 个球是都没有抽到,所以我们就只需要把 \(1\) 到 \(n-1\) 每个球抽中的概率加起来就行了。

code

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	double ans=0.0;
	for(double i=1;i<n;i++) ans+=(double)n/(n-i);
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

标签:frac,int,题解,abc194,Journey,ABC194D
From: https://www.cnblogs.com/wenzhihao2023/p/18069260

相关文章

  • 力扣hot100题解(python版69-73题)
    69、有效的括号给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例1:输入:s="()"输出:true示例2:输入:s="()[......
  • 【解题报告】THOI2023核心素养一题解
    THOI核心素养一题解展开目录目录THOI核心素养一题解比赛结果:A沙粒的记忆B远星的守望C国王的诞生E坏齿的舞曲F山麓的回音EXTRA群星的闪耀比赛页面(题目已公开,邀请码:yspm)赛时公告板看得出来出了相当多锅(由于D出锅严重,现已撤下,比赛延长10min.还请各位海涵(为什么延长......
  • 【计算机网络01】网卡——链接5G热点网速较慢问题解决方法。
    计算机网络:网卡一、网卡带宽查询二、高速带宽设置一.在电脑连接手机热点的时候,查询网络属性,找到网络频带是2.4GHz,带宽是72(Mbps):查找原因,发现是手机热点页面中AP频带设置的原因,AP频带设置成了2.4GHz:二.更改手机热点页面中AP频带,将AP频带设置成了5GHz频段:再在电......
  • Dwango Programming Contest 6th D 题解
    正好测试一下专栏的题解系统。我省选寄了都怪洛谷/fn/fn/fn/fn/fn/fn/fn题解显然可以对于所有关系建有向边,显然是基环外向树森林。由于是字典序最小,因此找到最小的上一个点没有直接连向边的点一定最优。但是有时取最优会导致最后无法选完,我们考虑无法选完的情况。第一种是......
  • AtCoder Beginner Contest 344 A-G 题解
    AtCoderBeginnerContest344A-SpoilerQuestion删除两个|之间的字符Solution按照题意模拟即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;stringp1,p2;for(inti=0;i<s.size();i++){......
  • LeetCode - 高频SQL50题(基础版)部分题解(上)
    1581.进店却未进行过交易的顾客原题:https://leetcode.cn/problems/customer-who-visited-but-did-not-make-any-transactions/题意:有一些顾客可能光顾了购物中心但没有进行交易。请你编写一个解决方案,来查找这些顾客的ID(customer_id),以及他们只光顾不交易的次数(count_no_trans......
  • node: /lib64/libm.so.6: version `GLIBC_2.27‘ not found问题解决方案
    场景centos7服务器使用nvm安装的node之后,只要使用npm或者node,均会出现以下问题。npm-vnode:/lib64/libm.so.6:version`GLIBC_2.27'notfound(requiredbynode)node:/lib64/libc.so.6:version`GLIBC_2.25'notfound(requiredbynode)node:/lib64/libc.so.6:ver......
  • 开摆题解
    开摆--更新ing没有详解(大概目录开摆--更新ingA题B题C题D题E题A题不配文字讲解了,具体的直接问我本人吧前缀和视频C++代码voidsolve(){intn,m,w,x,i,ans=0;cin>>n;vector<int>qwq(49);//前缀和数组for(i=0;i<n;++i){cin>......
  • rosdep update超时问题解决
    此问题的解决也适用ros11、初始化$sudorosdepinit2、下载rosdistro到本地$gitclonehttps://github.com/ros/rosdistro.git3、修改以下文件,将其url指向本地(1)文件1:20-default.list地址路径:/etc/ros/rosdep/sources.list.d/20-default.list原来内容:#os-specificl......
  • 随机逆序对 题解
    题意给定$1\simn$的排列$a_{1...n}$。在上面进行依次如下操作:首先在$[1,n]$​中选取一个子序列(可以为空);然后将这个子序列内的数重新排列。两个操作不同,当且仅当选取的子序列不同或者重新排列的方式不同。对于所有不同的操作,求他们产生的排列的逆序对个数和,答案......