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

AT_arc210_e [ARC210E] Subset Sum Gaps

对于全体子序列考察的题目可以考虑增量法。

考虑增量,此时我们知道了 \(n\) 的答案,需要推到到 \(n + 1\),不妨先来分析一下 \(n\) 时的答案形式长什么样:

  • 所有子序列的和排成一排,有一些相邻对满足条件。

这很简单对吧,考虑令此时这个集合为 \(S\),不妨来分析一下 \(S + a_{n + 1}\) 时答案的形态:

  • 可以证明,由于乘上的数 \(> 1\),所以当原本存在两个数 \(1.01x > y\)\(x, y\) 来说,那么 \(1.01(x + a_{n + 1}) > y + a_{n + 1}\)

这启发我们维护每个由这样的条件构成的连续段,那么我们只需要维护开头结尾的信息,每次将这些连续段暴力合并,可以证明复杂度是一个值域的 \(\log\)

这个做法同时也解释了为什么答案个数是有限个的。

http://www.jsqmd.com/news/425322/

相关文章:

  • 选配
  • nodejs+php+vue课程线上考试系统设计与实现
  • 零基础部署 OpenClaw:从 0 到跑起来(新手可直接照做)
  • 华为 vs H3C交换机常用命令差异
  • 单目相机当深度传感器用,不用双目/结构光。通过阴影估测3D高度。
  • 高并发下如何保证接口的幂等性
  • CF958F2 Lightsabers (medium)题解
  • 【AI渗透】——专为渗透测试工程师和安全研究员设计的新一代集成化安全测试平台(Venom)
  • 一款基于 .NET 开源免费、高效且用户友好文件搜索工具!
  • 基于粒子群算法的含分布式电源的主动配电网电压—有功-无功优化研究:以IEEE33节点为例
  • .Android Compose 基础系列:您的第一个 Kotlin 程序
  • 借助MongoDB实现大数据的分布式存储
  • MiniRAG + LLM (二)
  • 一文梳理清大数据领域CAP定理,轻松驾驭数据
  • 电动汽车充放电调度优化:全局与局部方案的比较及性能分析
  • 鸿蒙应用开发UI基础第十四节:文本显示组件Text核心讲解与实战演示 - 鸿蒙
  • Java求职面试实战:微服务与安全框架场景问题解析
  • 玩转STM32F1驱动双雄:BLDC与PMSM的攻防战
  • 从 Java 到 Go:一场性能革命
  • 使用C语言实现STM的启动文件
  • 探索大数据领域Doris的核心特性与优势
  • AI推理能力革命:如何打造高性能原生应用?
  • Android 开发问题:FileProvider: java.lang.SecurityException: Provider must not be exported
  • 大数据时代:用户画像助力企业精准营销
  • 使用 pkgutil 实现动态插件系统
  • 自注意力机制详解:从原理到计算过程
  • 东莞直饮水机服务商怎么选?靠谱服务商推荐 - 小坤哥
  • 记一次AI Agent开发的思维误区
  • 其他-vscode-配置
  • 最小二乘问题详解:线性最小二乘实例