当前位置: 首页 > news >正文

2023河南萌新联赛第(六)场:河南理工大学-C 旅游

2023河南萌新联赛第(六)场:河南理工大学

https://ac.nowcoder.com/acm/contest/63602/C

文章目录

  • 2023河南萌新联赛第(六)场:河南理工大学
    • 题意
    • 解题思路
    • 代码

题意

小C喜欢旅游,现在他要去DSH旅游,DSH里有 n n n个城市和 n − 1 n−1 n1条双向道路(每条道路长度为1),每条道路连接两个城市,并且任意两个城市都可以通过这些的道路互相到达。现在小C要使用魔法指定传送到DSH里的一个城市,作为他旅游的出发城市,小C旅游遵从以下原则:

  1. 当小C抵达一个城市的时候,他会去跟当前这个城市相连的城市;
  2. 他只去他以前没有去过的城市;
  3. 在每个城市,小C以相同的概率移动去上述符合要求的城市;

当没有这样的城市(可走)时,小C就停下了。
由于小C太喜欢DSH了,所以请你告诉小C,在他可以指定传送出发城市的情况下,他的旅游路径的期望最大值是多少。

解题思路

先确定 1 1 1为根节点,设 d p x dp_x dpx表示以 x x x为根的子树内走过节点个数的期望值,则 d p x = 1 + 1 ∣ s o n x ∣ ∑ s ∈ s o n x d p s dp_x=1+\frac{1}{|son_x|}\sum_{s\in son_x}dp_s dpx=1+sonx1ssonxdps,求出后,设 f x f_x fx表示以 x x x为出发点,经过节点个数的期望值,显然 f 1 = d p 1 f_1=dp_1 f1=dp1,可以用换根 d p dp dp O ( n ) O(n) O(n)求出 { f } \{f\} {f},对于 f x f_x fx,其值包括其原来的子树的贡献和原来的父亲 f a fa fa的贡献。首先考虑子树,贡献为 1 ∣ s o n x + 1 ∣ ∑ s ∈ s o n x f s \dfrac{1}{|son_x+1|}\sum_{s\in son_x}f_s sonx+1∣1ssonxfs,可以发现 ∑ s ∈ s o n x f s = ( d p x − 1 ) × ∣ s o n x ∣ \sum_{s\in son_x}f_s=(dp_x-1)\times|son_x| ssonxfs=(dpx1)×sonx,所以为 ∣ s o n x ∣ ∣ s o n x + 1 ∣ ( d p x − 1 ) \dfrac{|son_x|}{|son_x+1|}(dp_x-1) sonx+1∣sonx(dpx1)。对于 f a fa fa的贡献,包括以 f a fa fa为根的树的期望减去以 x x x为儿子的贡献,为 v e c f a . s i z e ( ) × f f a − d p x − 1 v e c f a . s i z e ( ) − 1 × 1 ∣ s o n x ∣ + 1 \dfrac{vec_{fa}.size()\times f_{fa}-dp_x-1}{vec_{fa}.size()-1}\times\dfrac{1}{|son_x|+1} vecfa.size()1vecfa.size()×ffadpx1×sonx+11(之所以用 v e c f a . s i z e ( ) vec_{fa}.size() vecfa.size()是避免 f a = 1 fa=1 fa=1时再分类讨论),加上其本身,整理可得:
f x = 1 ∣ s o n x ∣ + 1 ( ( d p x − 1 ) × ∣ s o n x + 1 ∣ + v e c f a . s i z e ( ) × f f a − d a x − 1 v e c f a . s i z e ( ) − 1 ) + 1 f_x=\dfrac{1}{|son_x|+1}((dp_x-1)\times|son_x+1|+\dfrac{vec_{fa}.size()\times f_{fa}-da_x-1}{vec_{fa}.size()-1})+1 fx=sonx+11((dpx1)×sonx+1∣+vecfa.size()1vecfa.size()×ffadax1)+1
记得 g g g表示的是节点数,答案要求路径长,要将最大值减一。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
double dp[N],f[N],ma;
vector<int>ve[N];
void dfs1(int u,int fa){int cnt=(ve[u].size()-(u!=1?1:0));for(auto v:ve[u]){if(v==fa)continue;dfs1(v,u);dp[u]+=1.0/cnt*dp[v];}dp[u]=dp[u]+1;
}
void dfs2(int u,int fa){ma=max(f[u],ma);int sum=ve[u].size();for(auto v:ve[u]){if(v==fa)continue;int cnt=ve[v].size()-1;f[v]=(1.0*(dp[v]-1)*cnt+(sum>1?(sum*f[u]-dp[v]-1)/(sum-1):1))/(cnt+1)+1;dfs2(v,u);}
}
int main(){cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;ve[u].push_back(v);ve[v].push_back(u);}dfs1(1,0);f[1]=dp[1];dfs2(1,0);printf("%.3lf",ma-1);
}

相关文章:

2023河南萌新联赛第(六)场:河南理工大学-C 旅游

2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学 https://ac.nowcoder.com/acm/contest/63602/C 文章目录 2023河南萌新联赛第&#xff08;六&#xff09;场&#xff1a;河南理工大学题意解题思路代码 题意 小C喜欢旅游&#xff0c;现在他要去DSH旅…...

C语言 常用工具型API ----------strchr()

函数原型 char *strchr(const char *str, int c) 参数 str-- 要被检索的 C 字符串。 c-- 在 str 中要搜索的字符。 功能 在参数str所指向的字符串中搜索第一次出现字符c&#xff08;一个无符号字符&#xff09;的位置 头文件 #include <string.h> 返回值 返回一…...

建造者模式的理论与实现

本文实践代码仓库&#xff1a;https://github.com/goSilver/my_practice 文章目录 一、定义二、作用三、实现四、总结 一、定义 建造者模式是一种创建复杂对象的设计模式。它将一个复杂对象的构建过程分解为多个简单的步骤&#xff0c;并且允许按照特定的顺序来构建对象。通过…...

非计算机科班如何顺利转码进入计算机领域?

文章目录 如何规划才能实现转码&#xff1f;计算机岗位发展前景&#xff1f;现阶段转码 总结 &#x1f389;欢迎来到Java学习路线专栏~探索非计算机科班如何顺利转码进入计算机领域 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT陈寒的博客&#x1f3…...

【C++类和对象】类有哪些默认成员函数呢?(下)

文章目录 一、类的6个默认成员函数二、日期类的实现2.1 运算符重载部分2.2 日期之间的运算2.3 整体代码1.Date.h部分2. Date.cpp部分 三. const成员函数四. 取地址及const取地址操作符重载扩展内容 总结 ヾ(๑╹◡╹)&#xff89;" 人总要为过去的懒惰而付出代价ヾ(๑╹◡…...

springboot自定义banner的输出与源码解析

文章目录 一、介绍二、演示环境三、自定义banner1. 文本2. 图片3. placeholder占位符4. 关闭banner 四、源码分析1. 关闭banner2. banner模式3. banner打印器4. 打印banner① 获取banner② 打印banner 5. 版本号占位符的解析器6. 文本格式占位符的解析器7. 应用标题占位符的解析…...

LeetCode 141.环形链表

文章目录 &#x1f4a1;题目分析&#x1f4a1;解题思路&#x1f514;接口源码&#x1f4a1;深度思考❓思考1❓思考2 题目链接&#x1f449; LeetCode 141.环形链表&#x1f448; &#x1f4a1;题目分析 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中…...

Spring-Bean的生命周期

目录 生命周期汇总 细分生命周期 1.实例化 2.属性赋值&#xff08;依赖注入&#xff09; 3.Aware接口 4.BeanPostProcessor接口 5.初始化 6.销毁 测试验证 类结构 业务类 测试类 生命周期汇总 Spring Bean 的生命周期见下图 &#xff08;一定记忆好下图&#x…...

Cat(3):客户端集成—简单案例

接下来编写一个简单的springboot与Cat整合的案例 1 新建springboot项目 首先创建一个Spring Boot的初始化工程。只需要勾选web依赖即可。 2 添加 Maven 添加依赖 <dependency><groupId>com.dianping.cat</groupId><artifactId>cat-client</artifa…...

虚拟机/双系统Ubuntu扩容

虚拟机Ubuntu扩容 1.需要删除所有的快照 2.扩展虚拟机磁盘大小 虚拟机(M)→设置(s)→硬盘(SCSI)→扩展磁盘容量 3.Ubuntu内调整分区大小 安装gparted分区工具&#xff1a;sudo apt-get install gparted 启动gparted并resize分区 4.最后最好建一个快照&#xff0c;不然gg了…...

Nginx搭建本地服务器,无需购买服务器即可测试vue项目打包后的效果

一.前言 本文是在windows环境&#xff08;Linux环境下其实也大同小异&#xff09;下基于Nginx实现搭建本地服务器&#xff0c;手把手教你部署vue项目。 二.Nginx入门 1&#xff09;下载安装 进入Nginx官网下载&#xff0c;选择stable版本下的windows版本下载即可 2&#xff09;…...

SpringBoot 接口调用出现乱码解决 中文乱码

SpringBoot 接口调用出现乱码解决 package com.cxjg.mvc.util;import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.http.converter.HttpMessageConverter; import org.springfra…...

JDBC封装与设计模式

什么是 DAO &#xff1f; Data Access Object(数据存取对象) 位于业务逻辑和持久化数据之间实现对持久化数据的访问 DAO起着转换器的作用&#xff0c;将数据在实体类和数据库记录之间进行转换。 ----------------------------------------------------- DAO模式的组成部分 …...

小程序扫描二维码获取网址,通过Jsoup进行解析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 一、Jsoup是什么&#xff1f; 二、使用步骤 1.引入库 2.读入数据 总结 前言 vx开发小程序使用扫一扫时不同二维码展示的东西不一样,需要进行解析 提示&a…...

Kubernetes+EFK构建日志分析平台

目录 Elasticsearch产品介绍 Fluentd 工作原理 Kibana产品介绍 一、环境准备 前三个主机都要操作 1、主机初始化配置 2、部署docker环境 2、部署kubernetes集群 2.1、组件介绍 2.2、配置阿里云yum源 2.3、安装kubelet kubeadm kubectl 2.4、配置init-config.yaml …...

客服如何减轻工作压力?浅析客服压力管理方法

在现代商业领域中&#xff0c;客服是一项非常重要的工作&#xff0c;负责根据客户需求提供解决方案。客服工作不仅需要一定的专业知识和技能&#xff0c;还需要面对各种复杂、多变的情况&#xff0c;并拥有强大的应对压力的能力。客服从业人员的工作压力往往非常大&#xff0c;…...

知识储备--基础算法篇-二分搜索

1.前言 最近准备开始刷算法题了&#xff0c;搜了很多相关的帖子&#xff0c;下面三个很不错&#xff0c; 计算机视觉秋招准备过程看这个&#xff1a;​​​​​​计算机视觉算法工程师-秋招面经 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/399813916 复习深度学习相关…...

【MySQL系列】表内容的基本操作(增删查改)

「前言」文章内容大致是对MySQL表内容的基本操作&#xff0c;即增删查改。 「归属专栏」MySQL 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 一、MySQL表内容的增删查改1.1 Create1.1.1 单行数据全列插入1.1.2 多行数据指定列插入1.1.3 插入否则更新1.1.4 数据替换 1.2 Ret…...

docker搭建LNMP

docker安装 略 下载镜像 nginx:最新版php-fpm:根据自己需求而定mysql:根据自己需求定 以下是我搭建LNMP使用的镜像版本 rootVM-12-16-ubuntu:/docker/lnmp/php/etc# docker images REPOSITORY TAG IMAGE ID CREATED SIZE mysql 8.0…...

未出现过的最小正整数

给定一个长度为 n 的整数数组&#xff0c;请你找出未在数组中出现过的最小正整数。 样例 输入1&#xff1a;[-5, 3, 2, 3]输出1&#xff1a;1输入2&#xff1a;[1, 2, 3]输出2&#xff1a;4数据范围 1≤n≤105 , 数组中元素的取值范围 [−109,109]。 代码&#xff1a; c…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

Appium下载安装配置保姆教程(图文详解)

目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...

中国政务数据安全建设细化及市场需求分析

(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...