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

AtCoder Grand Contest 015 - E - Mr.Aoki Incubator

AtCoder Grand Contest 015 - E - Mr.Aoki Incubator

思路解析

设 $ f(S) $ 为初始感染集合为 $ S $。

哪些人能够被最终感染呢?

我们考虑将每个人视作一个点,感染他的人视作它的父亲。

再观察 $ f({i}) $ 是什么,将每个人视作点 $ (V_i, X_i) $ 画在一维平面中,两个点会相遇且仅当两个点的连续斜率 \(< 0\),并且斜率绝对值越小相遇越早。

通过图我们可以发现最终被感染的点在横坐标上是一段区间,也就是 $ (V_i, X_i) $ 左上角矩形最靠右的,以及 $ (V_i, X_i) $ 右下角矩形最靠右的。

求出每个点会染色的区间 $ [l_i, r_i] $ 后,问题就变成了选出某些区间使得能够完全覆盖 $ [1, n] $,询问有多少种方案。令 $ f_r $ 为选出的区间恰好覆盖前 \(i\) 个点的方案数,每次转移枚举 $ r = i $ 的区间,按照左端点从小到大枚举,每次将 $ f_{l-1}, f_l, \ldots, f_r $ 加到 $ f_r $ 上即可。可以使用前缀和优化解决。

总的时间复杂度为 $ O(n \log n) $。


后记

奇技淫巧

似乎可以通过主席树优化拓扑排序的方法实现?

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

相关文章:

  • 9.30 CSP-S模拟25 改题记录
  • 全球抗体药表达系统:CHO 细胞主导下,未来十年将迎哪些突破?
  • 完整教程:[论文阅读]Benchmarking Poisoning Attacks against Retrieval-Augmented Generation
  • 绕过Cloudflare IP白名单限制的技术解析
  • 撕裂的乡土:在人性荒原上寻找微光
  • 2025蔬菜配送服务公司 TOP 企业推荐排行榜,深圳、宝安、光明、松岗、东莞、长安、虎门、沙田、厚街、大岭山蔬菜配送推荐
  • 2025液压缸TOP企业品牌推荐排行榜!抓斗、伺服、大吨位、车辆、工程、拉杆、冶金、重载、港机液压缸推荐
  • 2025 年破胶机厂家品牌推荐榜单白皮书,多规格型号 610/710/810、大型、自动型、低温环保、节能省电、自动打块、轮胎破胶机公司推荐
  • 乱七八糟的国庆做题记录
  • 2025 年健身器材品牌 TOP 推荐排行榜,室内 / 健身房 / 体育 / 运动 / 家用 / 商用 / 单位 / 家庭 / 有氧 / 力量健身器材推荐
  • 详细介绍:给贾维斯加“手势控制”:从原理到落地,打造多模态交互的本地智能助
  • 完整教程:学术论文 Word 样式规范
  • 取印度孟买指数(SENSEX)实时行情API对接指南
  • 2025青海视频号运营优质公司推荐榜:专业服务与创新策略口碑
  • 2025 年发泡陶瓷厂家 TOP 企业品牌推荐排行榜,发泡陶瓷线条 / 构件 / 装饰构件 / 空心砖 / 窗套线 / 浮雕 / 装饰线条推荐这十家公司
  • Future相关并发类使用
  • 2025 年传感器厂家 TOP 企业品牌推荐排行榜,磁致伸缩 / 防爆 / 防水 / 隔爆 / 线性 / 矿用 / 直线 / 油缸位移传感器 / 液位传感器公司推荐!
  • 2025 年热转印花膜厂家 TOP 企业品牌推荐排行榜,硅胶 / 五金 / 塑胶 / ABS / 涂料桶 / PP / 水杯 / 温变 / 冰变热转印花膜加工厂推荐
  • 2025 年生物除臭设备厂家 TOP 品牌企业推荐排行榜揭晓:印染厂污水 / 食品厂污水 / 污水处理厂 / 污水泵站 / 污水站 / 餐厨垃圾 / 屠宰场 / 厨余垃圾生物除臭设备公司推荐
  • JUC:读写锁
  • 2025 年舞台厂家 TOP 品牌企业权威推荐榜单,铝合金舞台、活动舞台、快装舞台、舞台架、折叠舞台、演出舞台、演唱会舞台桁架、舞台设计公司推荐
  • 2025 年点胶机厂家 TOP 企业推荐排行榜,自动 / 果冻胶 / 无痕内衣 / 烫钻 / 珠宝热熔胶 / 水钻热熔胶 / 亮片热熔胶 / 金葱粉热熔胶点胶机推荐这十家公司!
  • 2025 年知识库应用工具系统平台推荐排行榜,企业 / 行业 / 专家 / 问答 / 智能 / 培训 / 协同 / 办公 / 内部 / 外部 / 个人 / 客服 / 营销知识库应用软件推荐!
  • 2025 年移民服务公司性价比排行:美国、加拿大等国 TOP 机构,综合费用与服务质量的考量!
  • 2025 年水泥墩公司推荐最新榜单白皮书发布,圆形 / 方形 / 光伏水泥墩 / 围挡水泥墩 / 护栏水泥墩 / 交通水泥墩 / 防撞水泥墩源头厂家推荐
  • 2025 年乡墅平台 TOP 服务机构平台推荐排行榜 ,乡墅设计 / 品牌 / 加盟 / 农村自建房 / 建别墅 / 一站式建 / 湖南 / 长沙乡墅服务商推荐这十家公司!
  • 2025 年美缝剂厂家 TOP 企业品牌推荐排行榜,深度剖析美缝剂公司实力与产品优势!
  • 深入理解 Qt 元对象系统:QMetaEnum 的应用与实践 - 指南
  • 2025 年褐藻寡糖厂家 TOP 企业品牌推荐排行榜,农业级 / 食品级 / G 型 / 化妆品级 / 饲料级 / 肥料用褐藻寡糖 / 褐藻寡糖钾盐 / 水剂 / 粉剂 / M 段公司推荐!
  • 2025换热器厂家最新推荐白皮书,不锈钢 / 钛 / 哈氏合金 / 碳钢 / 衬四氟 / 列管式 / 螺旋板 / 管壳式 / 缠绕式 / 复合材料换热器公司推荐!