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

NOIP模拟赛记录

T1

假设有 \((x,y)\) 表示 \(x\) 个瓜子 \(y\) 个皮,显然有 \(x/(x+y)\) 概率转移到 \((x-1,y+2)\),和 \(y/(x+y)\) 概率转移到 \((x,y-1)\)。连线后成为了一个 DAG。

\(dp_{x,y}\) 表示从 \((x,y)\) 状态到达终点 \((0,2n)\) 的期望,可以用记忆化搜索实现 dp 过程。

T2

对于每个位置 \(i\),钦定他就是第 \(k\) 大,也就是说区间中有 \(k-1\) 个比它大的。如果 \(1 \sim (i-1)\)\(x\) 个,\((i+1) \sim n\) 就有 \(k-1-x\) 个。也就是说,对于每个 \(i\),我们需要知道它前后第 \(j\) 个大于等于 \(a_i\) 的下标。例如序列 5 3 1 2 4\(3\) 前面有 1,后面有 5

我们可以把序列排序后,维护一个链表。一开始链表为 1-2-3-4-5,后来的每一个数都从链表上删掉一些节点。还是以 5 3 1 2 4 举例,排序后为 1 2 3 4 5,枚举到 \(3\) 时链表就变成了 1-5

知道怎么维护后,答案就成了对于每个位置往左找 \(i\) 个比它大的,往右找 \(k-1-i\) 个比它大的。假设找到的最左边和最右边为 \(L,R\),而找到左边第 \(i-1\) 个和右边 \(k-1-i-1\) 个比它大的为 \([L',R']\),则如果区间 \([l,r]\) 满足 \(L'<l\le L,R \le r < R'\),这个区间就满足条件。计数即可。

http://www.hskmm.com/?act=detail&tid=24227

相关文章:

  • 软件工程第一次作业--关于未来规划和自我发展
  • 2025太阳能厂家推荐天津龙腾,太阳能热水系统,发电系统,光伏热系统,热水工程系统,预加热系统,中央热水系统,彩图发电系统,分户储水系统,分户计量系统推荐
  • 集训模拟赛日志
  • 1688 商品采集 API 调用全流程分享:从准备到实操 - 实践
  • 2025最新推荐化妆品代工公司排行榜:含 OEM / ODM / 一站式服务企业,助力品牌方精准选合作方
  • 悟空博弈单元(WBUC)专题研究:面向可能性计算的结构化创新架构
  • 访问控制、用户认证、https - 实践
  • GO_基础
  • sg.完整布局演示
  • sg.justification用法
  • Set
  • SCCPC2021重现赛
  • Ros2_control浅析——一个机器人开发通用框架的结构(1)
  • 图的计数问题没做
  • 11_linux镜像下载
  • CF2152 Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) 游记
  • 框架系统在自然语言处理深度语义分析中的作用、挑战与未来展望 - 实践
  • 10_windows11安装virtualbox
  • 9_windows11安装docker
  • 英语语法填空
  • 从涌现到戏台:AI元人文构想的演进历程
  • 题解:P14124 [SCCPC 2021] Nihongo wa Muzukashii Desu
  • QBXT2025S Day3题
  • python+vue在线视频课程学习系统设计(源码+文档+调试+基础修改+答疑) - 详解
  • pdf翻译
  • 【做题记录】CF2600左右有趣的思维题1
  • 【Android】RuntimeShader 应用
  • 【Rive】rive-android源码分析
  • zkSync Era主网上线:首个zkEVM全面开放的技术突破
  • Microsoft Access SQL 查询中的通配符 - 详解