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

2025icpc(Ⅱ)网络赛补题 GL

题意:

给定Alice和Bob的每一轮的概率p0,p1

给定Alice和Bob的初始数字x,y。

对于每一轮:

  • 如果Alice获胜,则bob的数字y需要减去x。(如果y≤0,Alice获胜)
  • 如果Bob获胜,则Alice的数字x需要减去y。(如果x≤0,Bob获胜)

重复上述游戏,直到出现胜利者。

问,Alice最终能赢得游戏的概率有多大。

思路:

可以直接用减法模拟,用除法加速,类似辗转相除法

当x>y时,x可以输x/y场,转移到(x%y,y)的状态,其他状态A必胜

当x≥y时,x必须赢y/x场,转移到(x,x%y)的状态,然后在考虑A必胜的情况

代码:

 

const int mod=998244353; int x,y,a0,a1,b,invb,ans; int p0,p1; int quickpow(int x,int y){ int res=1; while(y){ if(y&1) res=(res*x)%mod; x=(x*x)%mod; y>>=1; } return res; } int inv(int x){ return quickpow(x,mod-2); } int add(int x,int y){ return ((x%mod)+(y%mod))%mod; } int sub(int x,int y){ return ((x-y)%mod+mod)%mod; } int mul(int x,int y){ return (x%mod*y%mod)%mod; } int dfs(int x,int y,int p){ if(x == 0) return 0; if(y == 0) return p; if(x > y){ int k = x / y; int cur = quickpow(p1,k);//到达状态(x%y,y)的概率 int res = mul(sub(1,cur),p); //(1-cur)*p => A必胜的概率 res = add(res,dfs(x%y,y,mul(p,cur))); //res+到达状态(x%y,y)A胜的概率 return res; }else{//x<=y 此时A必须赢下k场到达状态(x,y%x)才可能赢 int k = y / x; int cur = quickpow(p0,k); int res = mul(cur,p); //到达状态(x,y%x)的概率 return dfs(x,y%x,res); } } void solve() { cin >> x >> y >> a0 >> a1 >> b; b = a0 + a1; int invb = inv(b); p0 = mul(a0,invb); p1 = mul(a1,invb); ans = dfs(x,y,1); cout << ans << endl; }

1|2L、502 Bad Gateway

题意:

给定一个T,每一步可以做以下两个操作:

1、减1

2、随机重置为[1,T]中的某个整数

求在最优策略下,得到0的期望步数

思路:

最优策略为选择一个阈值S,如果大于S的话,就重置;如果小于S的话就直接减到0

所以我们可以列出下面这个方程

E=S×(1+S)2×(S+1)×(T−S)T

可以解得

E=S−12+TS=S2+TS−12

所以能得到期望的最大值在S=2T取得

所以在⌊2T⌋和⌈2T⌉两点取

 

void solve(){ int t; cin >> t; int x1 = (int)sqrt(2*t); int x2 = min(t,x1+1); int fz1 = x1*x1 + 2*t - x1; int fm1 = 2*x1; int g1 = __gcd(fz1,fm1); fz1 /= g1; fm1 /= g1; int fz2 = x2*x2 + 2*t - x2; int fm2 = 2*x2; int g2 = __gcd(fz2,fm2); fz2 /= g2; fm2 /= g2; if(fz1*fm2<=fz2*fm1) cout << fz1 << " " << fm1 << endl; else cout << fz2 << " " << fm2 << endl; }

相关文章:

2025icpc(Ⅱ)网络赛补题 GL

题意&#xff1a; 给定Alice和Bob的每一轮的概率p0,p1 给定Alice和Bob的初始数字x,y。 对于每一轮&#xff1a; 如果Alice获胜&#xff0c;则bob的数字y需要减去x。&#xff08;如果y≤0&#xff0c;Alice获胜&#xff09;如果Bob获胜&#xff0c;则Alice的数字x需要减去y。…...

51c大模型~合集112

我自己的原文哦~ https://blog.51cto.com/whaosoft/13267449 #Guidance-Free Training (GFT) 无需引导采样&#xff0c;清华大学提出视觉模型训练新范式 引导采样 Classifier-Free Guidance&#xff08;CFG&#xff09;一直以来都是视觉生成模型中的关键技术。然而最近&am…...

Rust 文件读取:实现我们的 “迷你 grep”

1. 准备示例文件 首先&#xff0c;在项目根目录&#xff08;与 Cargo.toml 同级&#xff09;下新建一个名为 poem.txt 的文件。示例内容可参考 Emily Dickinson 的诗&#xff1a; Im nobody! Who are you? Are you nobody, too? Then theres a pair of us — dont tell! Th…...

【Unity3D】Jenkins Pipeline流水线自动构建Apk

目录 一、准备阶段 二、创建Pipeline流水线项目 三、注意事项 一、准备阶段 1、安装tomcat 10.0.5 Index of apache-local/tomcat/tomcat-10 2、安装jdk 17 Java Archive Downloads - Java SE 17.0.13 and later 3、下载Jenkins 2.492.1 (.war)包 War Jenkins Packa…...

信息收集-Web应用备案产权Whois反查域名枚举DNS记录证书特征相似查询

知识点&#xff1a; 1、信息收集-Web应用-机构产权&域名相关性 2、信息收集-Web应用-DNS&证书&枚举子域名 企业信息 天眼查 https://www.tianyancha.com/ 企业信息 小蓝本 https://www.xiaolanben.com/ 企业信息 爱企查 https://aiqicha.baidu.com/ 企业信息 企查…...

结合实际讲NR系列2—— SIB1

这是在基站抓取的sib1的一条信令 L3MessageContent BCCH-DL-SCH-Messagemessagec1systemInformationBlockType1cellSelectionInfoq-RxLevMin: -64q-QualMin: -19cellAccessRelatedInfoplmn-IdentityListPLMN-IdentityInfoplmn-IdentityListPLMN-IdentitymccMCC-MNC-Digit: 4MC…...

绿虫仿真软件如何预测组件衰减对收益的影响?

绿虫仿真软件通过其精细化的算法模型&#xff0c;能够有效预测组件衰减对光伏电站收益的影响&#xff0c;主要体现在以下几个方面&#xff1a; 1. 数据基础与模型构建 历史数据分析&#xff1a;绿虫软件整合了长达20年的历史数据&#xff0c;涵盖气象、地理、组件型号、逆变器…...

本地部署DeepSeek集成VSCode创建自己的AI助手

文章目录 安装Ollama和CodeGPT安装Ollama安装CodeGPT 下载并配置DeepSeek模型下载聊天模型&#xff08;deepseek-r1:1.5b&#xff09;下载自动补全模型&#xff08;deepseek-coder:1.3b&#xff09; 使用DeepSeek进行编程辅助配置CodeGPT使用DeepSeek模型开始使用AI助手 ✍️相…...

07贪心 + 动态规划(D1_基础学习)

目录 讲解一&#xff1a;贪心算法 一、什么是贪心算法&#xff1f; 二、贪心算法的应用场景 三、使用Java代码实现贪心算法 四、知识小结 -------------------------------- 讲解二&#xff1a;动态规划算法 一、什么是动态规划算法 二、动态规划算法求解问题需要具备的…...

redis之数据库

文章目录 服务器中的数据库切换数据库数据库键空间读写键空间时的维护操作 设置键的生存时间或过期时间保存过期时间过期键的判定过期键删除策略清性删除策略的实现定期删除策略的实现 总结 服务器中的数据库 Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结…...

【竞技宝】电竞世界杯:无畏契约首次入选正式项目!

北京时间2月12日&#xff0c;电竞世界杯基金会&#xff08;EWCF&#xff09;与知名游戏开发商拳头游戏&#xff08;Riot Games&#xff09;在近日共同宣布达成三年合作伙伴关系。同时&#xff0c;三大顶级电竞项目——《英雄联盟》《英雄联盟&#xff1a;云顶之弈》&#xff08…...

Golang GORM系列:GORM 高级查询教程

有效的数据检索是任何程序功能的基础。健壮的Go对象关系映射包&#xff08;称为GORM&#xff09;除了标准的CRUD操作之外&#xff0c;还提供了复杂的查询功能。这是学习如何使用GORM进行高级查询的综合资源。我们将涵盖WHERE条件、连接、关联、预加载相关数据&#xff0c;甚至涉…...

智能GUI Agent是什么,有什么应用领域

智能GUI Agent是什么 研究背景与目的:GUI长期主导人机交互,LLM特别是多模态模型的出现,为GUI自动化带来变革,催生了基于LLM的GUI智能体。这些智能体可理解自然语言指令,处理复杂GUI元素并执行操作,改变了用户与软件交互方式。论文旨在梳理该领域发展脉络,剖析关键要素,…...

k8s优雅操作pod容器组

k8s优雅操作pod容器组 回退备份 kubectl get deploy deployName -o yaml>>deployName-bak-date "%Y-%m-%d".yaml获取副本数 replicasecho | kubectl get -o template deploy/deployName --template{{.spec.replicas}}停止容器组 kubectl scale deployment …...

在 Mac ARM 架构上使用 nvm 安装 Node.js 版本 16.20.2

文章目录 1. 安装 nvm&#xff08;如果还没有安装的话&#xff09;2. 加载 nvm 配置3. 列出特定系列的 Node.js 版本&#xff08;远程&#xff09;&#xff1a;4. 安装 Node.js 16.20.25. 使用指定版本的 Node.js6. 验证安装 在 Mac ARM 架构上使用 nvm 安装 Node.js 版本 16.…...

MySQL创建存储过程和存储函数

【图书推荐】《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;》-CSDN博客 《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) MySQL9数据库技术_夏天又到了…...

PyQt学习记录03——批量设置水印

0. 目录 PyQt学习记录01——加法计算器 PyQt学习记录02——串口助手 1. 前言 本次主要是为了学习Qt中的 QFileDialog 函数&#xff0c; QFileDialog.getExistingDirectory&#xff1a;用于选择文件夹&#xff0c;返回的是一个文件夹路径。 QFileDialog.getOpenFileName&…...

vivo手机和Windows电脑连接同一个WiFi即可投屏!

虽然现在很多人喜欢刷手机&#xff0c;但是对于长时间需要使用手机办公的人来说&#xff0c;手机屏幕还是太小了&#xff0c;当人一天二十四小时中要花费近十个小时摆弄手机&#xff0c;就会渴望手机屏幕能够大一点&#xff0c;至少看的时候&#xff0c;眼睛舒服一点。 因为嫌弃…...

芯盾时代数据安全产品体系,筑牢数据安全防线

芯盾时代数据安全治理&#xff08;DSG&#xff09;框架&#xff0c;以国家法律法规、行业监管标准、行业最佳实践为依据&#xff0c;从数据安全战略出发&#xff0c;以数据分类分级为支撑&#xff0c;构数据安全管理体系、数据安全技术体系、数据安全运营体系与数据安全监督评价…...

异位妊娠唯一相关的是年龄(U型曲线)

异位妊娠唯一相关的是年龄&#xff08;U型曲线&#xff09; 简介 异位妊娠&#xff0c;俗称宫外孕&#xff0c;是指受精卵在子宫体腔以外着床发育的异常妊娠过程 。正常情况下&#xff0c;受精卵会在子宫内着床并发育成胎儿&#xff0c;但在异位妊娠中&#xff0c;受精卵却在…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...