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
题意: 给定Alice和Bob的每一轮的概率p0,p1 给定Alice和Bob的初始数字x,y。 对于每一轮: 如果Alice获胜,则bob的数字y需要减去x。(如果y≤0,Alice获胜)如果Bob获胜,则Alice的数字x需要减去y。…...
51c大模型~合集112
我自己的原文哦~ https://blog.51cto.com/whaosoft/13267449 #Guidance-Free Training (GFT) 无需引导采样,清华大学提出视觉模型训练新范式 引导采样 Classifier-Free Guidance(CFG)一直以来都是视觉生成模型中的关键技术。然而最近&am…...
Rust 文件读取:实现我们的 “迷你 grep”
1. 准备示例文件 首先,在项目根目录(与 Cargo.toml 同级)下新建一个名为 poem.txt 的文件。示例内容可参考 Emily Dickinson 的诗: 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记录证书特征相似查询
知识点: 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…...
绿虫仿真软件如何预测组件衰减对收益的影响?
绿虫仿真软件通过其精细化的算法模型,能够有效预测组件衰减对光伏电站收益的影响,主要体现在以下几个方面: 1. 数据基础与模型构建 历史数据分析:绿虫软件整合了长达20年的历史数据,涵盖气象、地理、组件型号、逆变器…...
本地部署DeepSeek集成VSCode创建自己的AI助手
文章目录 安装Ollama和CodeGPT安装Ollama安装CodeGPT 下载并配置DeepSeek模型下载聊天模型(deepseek-r1:1.5b)下载自动补全模型(deepseek-coder:1.3b) 使用DeepSeek进行编程辅助配置CodeGPT使用DeepSeek模型开始使用AI助手 ✍️相…...
07贪心 + 动态规划(D1_基础学习)
目录 讲解一:贪心算法 一、什么是贪心算法? 二、贪心算法的应用场景 三、使用Java代码实现贪心算法 四、知识小结 -------------------------------- 讲解二:动态规划算法 一、什么是动态规划算法 二、动态规划算法求解问题需要具备的…...
redis之数据库
文章目录 服务器中的数据库切换数据库数据库键空间读写键空间时的维护操作 设置键的生存时间或过期时间保存过期时间过期键的判定过期键删除策略清性删除策略的实现定期删除策略的实现 总结 服务器中的数据库 Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结…...
【竞技宝】电竞世界杯:无畏契约首次入选正式项目!
北京时间2月12日,电竞世界杯基金会(EWCF)与知名游戏开发商拳头游戏(Riot Games)在近日共同宣布达成三年合作伙伴关系。同时,三大顶级电竞项目——《英雄联盟》《英雄联盟:云顶之弈》(…...
Golang GORM系列:GORM 高级查询教程
有效的数据检索是任何程序功能的基础。健壮的Go对象关系映射包(称为GORM)除了标准的CRUD操作之外,还提供了复杂的查询功能。这是学习如何使用GORM进行高级查询的综合资源。我们将涵盖WHERE条件、连接、关联、预加载相关数据,甚至涉…...
智能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(如果还没有安装的话)2. 加载 nvm 配置3. 列出特定系列的 Node.js 版本(远程):4. 安装 Node.js 16.20.25. 使用指定版本的 Node.js6. 验证安装 在 Mac ARM 架构上使用 nvm 安装 Node.js 版本 16.…...
MySQL创建存储过程和存储函数
【图书推荐】《MySQL 9从入门到性能优化(视频教学版)》-CSDN博客 《MySQL 9从入门到性能优化(视频教学版)(数据库技术丛书)》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) MySQL9数据库技术_夏天又到了…...
PyQt学习记录03——批量设置水印
0. 目录 PyQt学习记录01——加法计算器 PyQt学习记录02——串口助手 1. 前言 本次主要是为了学习Qt中的 QFileDialog 函数, QFileDialog.getExistingDirectory:用于选择文件夹,返回的是一个文件夹路径。 QFileDialog.getOpenFileName&…...
vivo手机和Windows电脑连接同一个WiFi即可投屏!
虽然现在很多人喜欢刷手机,但是对于长时间需要使用手机办公的人来说,手机屏幕还是太小了,当人一天二十四小时中要花费近十个小时摆弄手机,就会渴望手机屏幕能够大一点,至少看的时候,眼睛舒服一点。 因为嫌弃…...
芯盾时代数据安全产品体系,筑牢数据安全防线
芯盾时代数据安全治理(DSG)框架,以国家法律法规、行业监管标准、行业最佳实践为依据,从数据安全战略出发,以数据分类分级为支撑,构数据安全管理体系、数据安全技术体系、数据安全运营体系与数据安全监督评价…...
异位妊娠唯一相关的是年龄(U型曲线)
异位妊娠唯一相关的是年龄(U型曲线) 简介 异位妊娠,俗称宫外孕,是指受精卵在子宫体腔以外着床发育的异常妊娠过程 。正常情况下,受精卵会在子宫内着床并发育成胎儿,但在异位妊娠中,受精卵却在…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
