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

CF148D Bag of mice

news 来源：原创 2025/8/10 22:59:13

题目传送门

思路

状态设计

设 $dp_{i, j}$ 表示袋中有 $i$ 个白鼠和 $j$ 个黑鼠时， $A$ 能赢的概率。

状态转移

现在考虑抓鼠情况：

$A$ 抓到白鼠：直接判 $A$ 赢，概率是 $\frac{i}{i + j}$ ；
$A, B$ 都抓到一只黑鼠，并且跑出来一只黑鼠：概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2}$ ，然后转移到 $dp_{i, j - 3}$ ，故此情况下 $A$ 获胜的概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2} \times dp_{i, j - 3}$ ；
$A, B$ 都抓到一只黑鼠，并且跑出来一只白鼠：概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2}$ ，然后转移到 $dp_{i - 1, j - 2}$ ，故此情况下 $A$ 获胜的概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2} \times dp_{i - 1, j - 2}$ ；
$B$ 抓到白鼠：此情况 $A$ 失败，故不考虑。

所以总得转移方程就是：
$dp_{i, j} = \frac{i}{i + j} + \frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2} \times dp_{i, j - 3} + \frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2} \times dp_{i - 1, j - 2}$
当然转移的时候得分别判断【 $j$ 是否大于等于 $3$ 】和【 $i$ 是否大于等于 $1$ 且 $j$ 是否大于等于 $2$ 】。

边界条件

在没有老鼠或全是黑鼠的情况下， $A$ 一定输，即： $\forall i \in [0, m], \ dp_{0, i} = 0$ ；
在只有白鼠的情况下， $A$ 一定赢，即： $\forall i \in [1, n], \ dp_{i, 0} = 1$ 。

复杂度

时间复杂度： $\times m)$ ；
空间复杂度： $\times m)$ 。

代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3 + 7;int n, m;
double dp[maxn][maxn];
int main() {scanf("%d%d", &n, &m);for (int i = 0; i <= m; ++i) dp[0][i] = 0;  // 没有老鼠或只有黑鼠, B 赢 for (int i = 1; i <= n; ++i) dp[i][0] = 1;  // 只有白鼠, A 赢for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {dp[i][j] += 1.0 * i / (i + j);if (j >= 3) {dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) *1.0 * (j - 2) / (i + j - 2) * dp[i][j - 3];}if (i >= 1 && j >= 2) {dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) * 1.0 * i / (i + j - 2) * dp[i - 1][j - 2];}}}printf("%.9lf\n", dp[n][m]);return 0;
}

CF148D Bag of mice

题目传送门思路状态设计设 d p i , j dp_{i, j} dpi,j 表示袋中有 i i i 个白鼠和 j j j 个黑鼠时， A A A 能赢的概率。状态转移现在考虑抓鼠情况： A A A 抓到白鼠：直接判 A A A 赢，概率是 i i j \frac{i}{i j}…...

编程日记 2025/8/10 22:59:13

精益数据分析（6/126）：深入理解精益分析的核心要点

精益数据分析（6/126）：深入理解精益分析的核心要点在创业和数据驱动的时代浪潮中，我们都在不断探索如何更好地利用数据推动业务发展。我希望通过和大家分享对《精益数据分析》的学习心得，一起在这个充满挑战和机遇的领…...

编程日记 2025/8/10 22:57:07

package.json ^、~、＞、＞=、* 详解

package.json ^、~、>、>、* 详解在 Vue 项目中，package.json 文件的依赖项（dependencies）和开发依赖项（devDependencies）中，版本号前可能会带有一些特殊符号，例如 ^、~、>、<、&g…...

编程日记 2025/8/10 22:57:08

2025年赣教云智慧作业微课PPT模板

江西的老师们注意，2025年赣教云智慧作业微课PPT模版和往年不一样，千万不要搞错了，图上的才是正确的2025年的赣教云智慧作业微课PPT模版，赣教云智慧作业官网有问题，无法正确下载该模板，需要该模板的&#xf…...

编程日记 2025/8/10 22:58:53

Java PrintStream 类深度解析

Java PrintStream 类深度解析便捷： 1.直接输出各种数据 2.自动刷新和自动换行（println方法） 3.支持字符串转义 4.自动编码（自动根据环境选择合适的编码方式） 1. 核心定位 PrintStream 是 FilterOutputStream 的子类，提供格式化输出能力，是标准输出 System.out 的…...

编程日记 2025/8/9 1:30:15

超简单的git学习教程

本博客仅用于记录学习和使用前提声明全部内容全部来自下面廖雪峰网站，如果侵权联系我删除 1.小白学习看这篇，快速易懂入门，完整内容（半天完成学习本地和远程仓库建立） 简介 - Git教程 - 廖雪峰的官方网站 2.博客中…...

编程日记 2025/8/6 12:39:44

Yocto项目实战教程-第5章-5.1-5.2小节-BitBake的起源与源代码讲解

🔍 B站相应的视频教程： 📌 Yocto项目实战教程-第5章-5.1-5.2小节-BitBake的起源与源代码讲解记得三连，标为原始粉丝。 📚 系列持续更新中，B站搜索 “嵌入式 Jerry”，系统学 Yocto 不迷路&#…...

编程日记 2025/8/8 8:28:17

SQL注入相关知识

一、布尔盲注 1、布尔盲简介布尔盲注是一种SQL注入攻击技术，用于在无法直接获取数据库查询结果的情况下，通过页面的响应来判断注入语句的真假，从而获取数据库中的敏感信息 2、布尔盲注工作原理布尔盲注的核心在于利用SQL语句的布尔逻辑…...

编程日记 2025/8/10 22:58:55

Linux网络编程深入解析Linux TCP：TCP实操，三次握手和四次挥手的底层分析

知识点1【TCP编程概述】 1、TCP的概述客户端：主动连接服务器，和服务器进行通信服务器：被动被客户端连接，启动新的线程或进程，服务器客户端（并发服务器） 这里重复TCP和UDP特点 TCP&#x…...

编程日记 2025/8/10 0:47:50

实验4基于神经网络的模式识别实验

实验原理 1. BP学习算法是通过反向学习过程使误差最小，其算法过程从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点，而且含有一层或多层隐(层)节点。输入信号先向前…...

编程日记 2025/8/10 22:58:52

Rust网络编程实战：全面掌握reqwest库的高级用法

一、开篇导引 1.1 对比Python Requests解释为何reqwest是Rust生态的标杆HTTP客户端在Python生态中，Requests 库以其简洁易用的API成为了HTTP客户端的首选。它使得开发者能够轻松地发送各种HTTP请求，处理响应，而无需过多关注底层细节。然而…...

编程日记 2025/8/9 7:40:06

【漫话机器学习系列】211.驻点（Stationary Points）

驻点（Stationary Points）：理解函数导数为零的关键位置在数学分析、机器学习优化、物理建模等领域中，驻点（Stationary Points）是一个非常重要的概念。它们是函数图像中“停下来的点”，即导数为…...

编程日记 2025/8/10 22:57:06

图 - 最小生成树算法 - Kruskal - Prim

目录前言什么是最小生成树算法 Kruskal 克鲁斯卡尔 Prim 普利姆结语前言在图中一共有两类算法，一种是最短路径，还有一种就是本篇要讲解的最小生成树算法了其中，最短路径一共有三种，而最小生成树一共有两种&#xff…...

编程日记 2025/8/7 21:48:07

linux kernel irq相关函数详解

在Linux内核驱动开发中，处理中断涉及一系列关键函数，正确使用这些函数对确保驱动的稳定性和性能至关重要。以下是disable_irq、free_irq、platform_get_irq和request_irq等函数的详细解析，涵盖其功能、用法、注意事项及示例代码。一、核心函…...

编程日记 2025/8/7 8:14:49

聊聊Doris的数据模型，如何用结构化设计解决实时分析难题

传统 OLAP 系统的局限在大数据实时分析领域，数据模型设计直接决定了系统的查询性能、存储效率与业务适配性。Apache Doris作为新一代MPP分析型数据库，通过独创的多模型融合架构，在业内率先实现了"一份数据支持多种分析范式"的能力…...

编程日记 2025/8/5 9:53:33

[Swift]Xcode模拟器无法请求http接口问题

1.以前偷懒一直是这样设置 <key>NSAppTransportSecurity</key> <dict><key>NSAllowsArbitraryLoads</key><true/> </dict> 现在我在Xcode16.3上，这种设置方式在真机上能请求http（应该是设备开启了开发者模式…...

编程日记 2025/8/10 22:56:34

kafka认证部署

首先启动 zookeeper /home/kafka/bin/zookeeper-server-start.sh /home/kafka/config/zookeeper.properties 创建SCRAM证书 /home/kafka/bin/kafka-configs.sh --zookeeper localhost:2181 --alter --add-config SCRAM-SHA-256[iterations8192,passwordliebe],SCRAM-SHA-512[p…...

编程日记 2025/8/10 22:56:34

基于STM32中断讲解

基于STM32中断讲解一、NVIC讲解简介：当一个中断请求到达时，NVIC会确定其优先级并决定是否应该中断当前执行的程序，以便及时响应和处理该中断请求。这种设计有助于提高系统的响应速度和可靠性，特别是在需要处理大量中断请求的实…...

编程日记 2025/8/10 22:54:23

Java 动态代理教程（JDK 动态代理）（以RPC 过程为例）

1. 什么是动态代理在运行时为指定的接口自动生成代理对象，并通过 invoke 方法增强了这些对象的功能 2. 两个核心组件 java.lang.reflect.Proxy类这个类提供了方法：newProxyInstance()用来创建一个代理对象 public static Object newProxyInstance(…...

编程日记 2025/8/3 20:03:00

Linux Privilege Escalation： LD_PRELOAD

声明：本文所有操作需在授权环境下进行，严禁非法使用！ 0x01 什么是 LD_PRELOAD？ LD_PRELOAD 是 Linux 系统中一个特殊的环境变量，它允许用户在程序启动时优先加载自定义的动态链接库（.so 文件）&…...

编程日记 2025/8/10 22:54:25

Java 并发性能优化：线程池的最佳实践

Java 并发性能优化：线程池的最佳实践在 Java 并发编程的世界里，线程池堪称提高应用性能与稳定性的神器。恰如其分地运用线程池，能让我们在多线程任务调度时游刃有余，既能避免线程频繁创建销毁带来的开销，又能合理管控…...

编程日记 2025/8/10 22:57:07

QML动画--ParallelAnimation和SequentialAnimation

一、ParallelAnimation ParallelAnimation 是 QML 中用于并行执行多个动画的容器动画类型，可以同时运行多个子动画。基本用法 qml import QtQuick 2.15Rectangle {id: rectwidth: 100; height: 100color: "red"x: 0; y: 0; opacity: 1.0ParallelAnim…...

编程日记 2025/8/10 22:54:34

深入解析进程与线程：区别、联系及Java实现

引言在现代操作系统中，进程和线程是并发编程的两大核心概念。理解它们的区别与联系对开发高性能、高可靠性的程序至关重要。本文将通过原理分析和Java代码示例，深入探讨这两个关键概念。一、基本概念 1.1 进程（Process） 定义&…...

编程日记 2025/8/10 22:54:35

c++：线程（std::thread）

目录从第一性原理出发：为什么需要线程？ ✅ 本质定义： 📌 使用基本语法： 线程之间的“并发”与“并行”的区别线程安全与数据竞争（Race Condition） 如何让线程“安全地”访问数据&#x…...

编程日记 2025/7/31 5:11:58

基于LSTM-AutoEncoder的心电信号时间序列数据异常检测(PyTorch版)

心电信号（ECG）的异常检测对心血管疾病早期预警至关重要，但传统方法面临时序依赖建模不足与噪声敏感等问题。本文使用一种基于LSTM-AutoEncoder的深度时序异常检测框架，通过编码器-解码器结构捕捉心电信号的长期时空依赖特征&#…...

编程日记 2025/8/10 21:36:24

[密码学基础]GM/T 0018-2023 密码设备应用接口规范深度解析：技术革新与开发者实践

GM/T 0018-2023 密码设备应用接口规范深度解析：技术革新与开发者实践 GM/T 0018-2023《密码设备应用接口规范》是中国密码行业的重要标准，于2023年12月4日发布，2024年6月1日正式实施，替代了2012年版标准。该标准旨在规范密码设备…...

编程日记 2025/8/10 22:54:22

深入理解 Java 多线程：锁策略与线程安全

文章目录一、常见的锁策略1. 乐观锁&&悲观锁2. 读写锁3. 重量级锁&&轻量级锁4. 自旋锁5. 公平锁&&不公平锁6. 可重入锁 && 不可重入锁二、CAS1. 什么是 CAS2. CAS 是怎么实现的3.CAS 有哪些应用1) 实现原子类2) 实现自旋锁 4. CAS 的 ABA 问…...

编程日记 2025/8/10 22:54:34

Java从入门到“放弃”（精通）之旅——数组的定义与使用⑥

Java从入门到“放弃”（精通）之旅🚀——数组⑥ 前言——什么是数组？ 数组：可以看成是相同类型元素的一个集合，在内存中是一段连续的空间。比如现实中的车库，在java中，包含6个整形类…...

编程日记 2025/8/10 22:56:32

VsCode搭建

安全性问题的声明： VScode是一个由微软出品的开源软件编辑器 VScode下载 https://code.visualstudio.com/Download 官网直接下载即可，windows和linux的vscode使用命令是类似的。 VScode插件相关为了方便安装，推荐设置并使用vscode插件的…...

编程日记 2025/8/8 15:03:24

【NLP 65、实践 ⑯ 基于Agent优化文章】

羁绊由我而起，痛苦也由我承担 —— 25.4.18 一、⭐【核心函数】定义大模型调用函数 call_large_model prompt：用户传入的提示词（如 “请分析这篇作文的主题”），指导模型执行任务 client：Zhipu…...

编程日记 2025/8/9 5:43:14

【Redis】从单机架构到分布式，回溯架构的成长设计美学

前言 🌟🌟本期讲解关于分布式架构的发展相关知识介绍~~~ 🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客 🔥 你的点赞就是小编不断更新的最大动力 🎆那么废…...

编程日记 2025/8/10 5:07:10

增量式PID基础解析与代码实例：温控系统

目录 1. 前言 2. 增量式PID控制的基本原理 2.1 PID控制的基本概念 2.2 增量式PID控制的特点 3. 增量式PID控制的Python实现：温控系统 3.1 构建增量式PID控制器 3.2 使用增量式PID控制器 3.3 运行模拟 3.4 完整代码 4. 参数调整与优化 4.1 参数选择 4.2…...

编程日记 2025/8/10 7:19:49

数据结构——栈以及相应的操作

栈(Stack) 在维基百科中是这样定义的： 堆栈(stack) 又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合中的一端（称为堆栈顶端，top）进行加入数据（push）和…...

编程日记 2025/7/31 7:26:48

opencv 图像的旋转

图像的旋转 1 单点旋转2. 图片旋转（cv2.getRotationMatrix2D）3. 插值方法3.1 最近邻插值(cv2.INTER_NEAREST)3.2 双线性插值(cv2.INTER_LINEAR)3.3 像素区域插值（cv2.INTER_AREA）3.4 双三次插值（cv2.INTER_CUBIC&#…...

编程日记 2025/8/10 22:54:24

P3916 图的遍历

P3916 图的遍历题目来源-洛谷题意有向图中，找出每个节点能访问到的最大的节点思路每个节点的最大节点，不是最长距离，如果是每个节点都用dfs去找最大值，显然1e6*1e6 超时了，只能60分从第一个节点开始遍历&…...

编程日记 2025/8/8 10:25:24

Vue3 + Three.js 场景编辑器开发实践

文章目录前言项目背景与意义项目技术栈在线演示核心功能实现1. 智能化场景管理2. 专业级模型处理3. 可视化材质与照明4. 相机与渲染引擎5. 场景操作项目优势开发目标1. 几何模型和模型导入，场景新建按钮增加2. 提供场景内容的可视化编辑功能3. 渲染器场景&#xf…...

编程日记 2025/8/4 9:33:08

Vue3 本地打包启动白屏解决思路！! !

“为什么我访问 http://127.0.0.1:5501/index.html 白屏，删了 index.html 再访问 / 就又活过来了？” —— 你的项目与 SPA 路由的“宫斗大戏” 一、问题复现场景本地通过 VSCode Live Server（或其他静态服务器）启动了打包后的 V…...

编程日记 2025/8/8 4:29:57

Ubuntu 安装 Docker 教程（官方推荐方式）

✅ 步骤 1：卸载旧版本（如果有） for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done---### ✅ 步骤 2：更新 APT 索引并安装依赖项bash sudo a…...

编程日记 2025/8/9 17:16:52

WPF 点击按钮，显示隐藏另一个控件

<Button Content"显示隐藏" Click"operationDetails_Click" /> private void operationDetails_Click(object sender, RoutedEventArgs e) { 另一个控件的Name.Visibility 另一个控件的Name.Visibility Visibility.Visible ? Visibility.Col…...

编程日记 2025/8/6 4:20:32

RBAC的使用

1、简述RBAC的作用及工作流程 Rbac基于角色访问控制，用于管理用户对集群资源的访问权限，通过定义角色和绑定规则，将用户与权限进行关联，作用：权限精细化管理，操作便捷与统一管理，动态调整权限。…...

编程日记 2025/8/10 22:59:11

QML中的3D功能--模型导入与修改

在Qt 3D中导入和修改3D模型是开发3D应用程序的基础。以下是详细的流程和技术方案：一、模型导入基础 1. 支持的文件格式 Qt 3D支持多种3D模型格式： OBJ (Wavefront) FBX (Autodesk) DAE (Collada) GLTF/GLB (推荐格式) STL (3D打印格式) 2. 基本导入方法 qml import Qt3…...

编程日记 2025/8/5 4:22:52

树莓派超全系列教程文档--(33)树莓派启动选项

树莓派启动选项启动选项start_file ，fixup_filecmdlinekernelarm_64bitramfsfileramfsaddrinitramfsauto_initramfsdisable_poe_fandisable_splashenable_uartforce_eeprom_reados_prefixotg_mode （仅限Raspberry Pi 4）overlay_prefix配置属…...

编程日记 2025/8/10 1:09:17

dotnet core webapi 实现异常处理中间件

目录第一步：创建异常处理中间件类（自定义响应格式） 第二步：在 Program.cs 中使用中间件三、效果第一步：创建异常处理中间件类（自定义响应格式） public static class ExceptionMiddleware…...

编程日记 2025/8/8 17:51:32

实现Azure Function安全地请求企业内部API返回数据

需要编写一个Function在Azure云上运行，它需要访问企业内部的API获取JSON格式的数据，企业有网关和防火墙，API有公司的okta身份认证，通过公司的域账号来授权访问，现在需要创建一个专用的域账号，让Function访问…...

编程日记 2025/8/8 18:39:14

实现Azure Databricks安全地请求企业内部API返回数据

需要编写一个Databricks在Azure云上运行，它需要访问企业内部的API获取JSON格式的数据，企业有网关和防火墙，API有公司的okta身份认证，通过公司的域账号来授权访问，现在需要创建一个专用的域账号，让Databrick…...

编程日记 2025/7/31 7:26:24

结合建筑业务讲述TOGAF标准处理哪种架构

TOGAF标准处理哪种架构内容介绍业务架构业务策略，治理，组织和关键业务流程数据架构组织的逻辑和物理数据资产以及数据管理资源的结构应用架构待部署的各个应用程序，它们之间的交互以及与组织核心业务流程的关系的蓝图技术架构支持业务&#…...

编程日记 2025/8/5 1:20:54

深度学习--卷积神经网络CNN原理

文章目录一、CNN图像原理1、了解CNN如何处理图像二、CNN图像识别1、画面不变性2、主要表现1）平移不变性2）尺度不变性3）旋转不变性 3、传统神经网络1）数据预处理2）特征提取3）搭建神经网络模型4&#xff09…...

编程日记 2025/8/10 10:32:01

PostgreSQL 常用客户端工具

PostgreSQL 常用客户端工具 PostgreSQL 拥有丰富的客户端工具生态系统，以下是各类常用工具的详细分类和介绍： 一图形化客户端工具 1.1 跨平台工具工具名称特点适用场景许可证pgAdmin官方出品，功能全面开发/运维PostgreSQLDBeaver支持多…...

编程日记 2025/8/9 18:48:50

PostgreSQL数据库yum方式安装详解

PostgreSQL数据库yum方式安装 1. 基础环境配置2. 前期安装准备3. 软件安装3.1 YUM方式安装（PG 13）3.1.1 安装rpm仓库3.1.2 安装软件包PG133.1.3 初始化数据库3.1.4 启动数据库3.1.5 开机自启动3.1.6 编辑环境变量 4. 安装后配置 1. 基础环境配置 2. 前期…...

编程日记 2025/8/8 16:38:05

浅析vue2和vue3的区别

以下是 Vue 2 和 Vue 3 的主要区别：一、核心特性 1. 响应式机制 Vue 2：基于 Object.defineProperty 实现响应式。无法检测对象属性的新增和删除，需要使用 Vue.set 或 $set。Vue 3：使用 Proxy 替代 Object.defineProperty。能够直接检测对象属性的新增和删除，无需额外方…...

编程日记 2025/8/4 1:54:14

思路

状态设计

状态转移

边界条件

复杂度

代码

相关文章：