首页 > 其他分享 >Alice's Adventures in the Rabbit Hole

Alice's Adventures in the Rabbit Hole

时间:2024-12-09 19:56:04浏览次数:9  
标签:结点 frac Alice fa Rabbit rm Hole 递推

算法

显然的, 每次掷硬币, 女王(以下称为 \(B\)) 一定会将 \(\rm{Alice}\) (以下称为 \(A\)) 丢到下面, \(A\) 一定会将自己拉到上层

带到这道题里面去, 我们显然要做类似于树上的概率 \(\rm{dp}\)

一眼发现, 令 \(f_u\) 表示第 \(i\) 个点的逃脱概率, 那么有

\[f_u = \frac{1}{2} (f_{fa} + f_v) \]

其中 \(v\) 是贪心的选择叶子结点深度最低

但是这样子怎么递推呢?

然后去看了无比之久的 \(\rm{TJ}\) , 大概看出来了几种做法

方法 \(1\) : 按照 \(\rm{dp}\) 的方式推导, 拓展到树上

注意到 \(f\) 在链的情况下是一个等差数列, 直接带进去解

又有 \(f_{root} = 1, f_{leaf} = 0\)
得到 \(f_i = \frac{n - i}{n - 1}\)

但是树上的操作不太能这样做, 我们考虑先转化为递推形式 \(f_i = \frac{n - i}{n - i - 1} f_{son}\)
注意到 \(n - i\) 实际上是到叶子结点的距离
那么能不能拓展到树的链上呢

这里引入短链剖分的思想, 树被剖成了 \(l\) 条短链 ( \(l\) 为叶子个数), 这样每条链上都归为了以上情况, 稍微计算一下可以知道递推柿子不变

具体怎么处理呢, 从下往上递推, 直接计算

代码就不放了, 这里 有一份思路一样的代码

方法 \(2\) : 数学推导保平安

以下 \(f_u\) 表示从 \(u\) 点到达 \(fa_u\) 的概率

注意到对于每一个点, 我们枚举其下去再上来的次数

仍然是令 \(v\) 是贪心的选择叶子结点深度最低, 那么有

\[f_u = \sum_{i = 0}^{+\infty} \left( \frac{1}{2} \right) ^ {i + 1} \cdot {f_v}^i = \frac{1}{2} \sum_{i = 0}^{+\infty} \left( \frac{f_v}{2} \right) ^ i \]

这个是可以直接 \(\mathcal{O} (n \log M)\) 求, 其中 \(\log M\) 逆元, 杀掉逆元直接线性

那么答案怎么计算呢, 不难发现, 对于点 \(u\) , 我们只需要知道 \(fa_u\) 的答案, 乘上 \(f_u\) 即可, 那么就做完了, 递推从上到下

总结

很好的一道题, 可惜早早看题解影响了自己的思考

注意 链 \(\to\) 树的常见转化

注意退柿子的能力

标签:结点,frac,Alice,fa,Rabbit,rm,Hole,递推
From: https://www.cnblogs.com/YzaCsp/p/18595881

相关文章

  • Rabbitmq 开机启动脚本
     vi/etc/init.d/rabbitmq#!/bin/bash##chkconfig:23458005#description:rabbitmq#processname:rabbitmq#RabbitMQ安装目录RABBITMQ_HOME=/usr/local/rabbitmq_server-3.8.16exportRABBITMQ_HOMEcase"$1"instart)echo"StartingRabbitMQ......
  • SpringBoot整合RabbitMQ
    RabbitMQ简介消息中间件:它接收消息并且转发,就类似于一个快递站,卖家把快递通过快递站,送到我们的手上,MQ也是这样,接收并存储消息,再转发。RabbitMQ在2007年由Rabbit科技有限公司发布,是一个在AMQP(高级消息队列协议)基础上完成的,可复用的企业消息系统,是当前最主流的消息中间件之......
  • 使用Redis防止重复发送RabbitMQ消息
    问题今天遇到一个问题,发送MQ消息的时候需要保证不会重复发送,注意不是可靠到达(可靠到达可以通过消息确认机制和回调接口保证),这里保证的是不会生产多条一样的消息。方法综合讨论下来决定使用Redis缓存来解决,因为相比于将记录插入数据库Redis更为高效和便捷。检验是否已经发送在......
  • Net中RabbitMq.Client7.0通过依赖注入DI来管理RabbitMQ客户端的生命周期
    在RabbitMQ.Client7.0.0版本中,IModel在RabbitMQ.Client7.0.0-alpha2版本中已经被重命名,现在应该使用IChannel替代IModel,IChannel不再提供CreateBasicProperties方法。需要直接使用BasicProperties类来创建消息属性。前言关于RabbitMq的更多知识点在:https://ww......
  • RabbitMq 入门教程看这一篇就够了 (超详细!!!)
    目录一、RabbitMQ简介二、安装指南2.1Erlang2.2RabbitMQ三、RabbitMQ基本概念3.1RabbitMQ基础架构四、实战编程4.1引入依赖4.2创建连接获取Channel​​​​​​​4.3声明Exchange(可选)4.4声明queue​​​​​​​4.5声明Exchange与Queue的绑定关系(可......
  • RabbitMQ26问,基本涵盖了面试官必问的面试题(知识满满!!!)
    目录1.RabbitMQ是什么?2.RabbitMQ特点?3.AMQP是什么?4.AMQP协议3层?5.AMQP模型的几大组件?6.说说生产者Producer和消费者Consumer?7.为什么需要消息队列?8.说说Broker服务节点、Queue队列、Exchange交换器?9.消息队列有什么优缺点10.如何保证消息的可靠性?11.什么是Routi......
  • RabbitMQ 双机 镜像集群模式
    目录准备工作组建集群rabbitmq01rabbitmq02设置HA策略注意补充命令行检验登录管理界面检验准备工作#/etc/hosts172.16.0.11rabbitmq01172.16.0.12rabbitmq02组建集群rabbitmq01rabbitmq-server-detachedrabbitmqctlstatus#复制cookiecp~/.erlang.cookierabbitmq......
  • 用rabbitmqadmin 模拟消息的创建、发布、订阅
    前言rabbitmqadmin工具可以方便地管理RabbitMQ的资源,包括创建交换机Exchanges、队列Queues、绑定Bindings,以及发布Publish和订阅Subscribe消息。确保你已经下载并安装了rabbitmqadmin,并且RabbitMQ管理插件是启用的。你可以从http://localhost:15672/cli/下载......
  • SpringBoot集成RabbitMQ的四种交换机(Direct、Topic、Fanout、Headers)
    以下是四种RabbitMQ交换机类型(Direct、Topic、Fanout、Headers)的详细实例代码,展示如何分别实现并使用它们。1.DirectExchange(直连交换机)DirectExchange将消息根据路由键(RoutingKey)发送到指定的队列。配置代码@ConfigurationpublicclassDirectExchangeConfig{​......
  • 【消息队列】RabbitMq-声明队列与交换机
    通过Spring配置,Bean注入的形式依赖配置<!--AMQP依赖,包含RabbitMQ--><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-amqp</artifactId></dependency>yaml文件配置spring:rabbitmq:host:......