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

CodeForces-1183F Topforces Strikes Back

*CodeForces-1183F Topforces Strikes Back

tag: *2100;思维题,贪心

给定长度为 \(n\) 的序列 \(a\),从中选出 最多 三个数,满足其中任两个之间没有倍数关系。求这三个数之和的最大值。

\(1\le n,q,\sum n\le2\cdot10^5\)\(2\le a_i\le2\cdot10^5\)

首先将 \(a\) 排序去重,不影响结果。

选一个数的情况是平凡的,先考虑选两个数 \(x,y\) 的情况。不妨设 \(x<y\)

注意到,如果 \(x,y\) 之间有倍数关系,那么一定有 \(x\le y/2\),即 \(x\) 可以等于 \(y/2,y/3,\cdots\) 等等。

结论\(y=A\)

证明:设 \(A=\max a\)。如果选出的数为 \(x,y\)\(y\ne A\)

  • 如果 \(x,y\) 中没有 \(A\) 的因数,则把 \(x\) 换成 \(A\)
  • 如果 \(x,y\) 中有一个数是 \(A\) 的因数,则把这个数换成 \(A\)
  • 如果 \(x,y\) 都是 \(A\) 的因数,则 \(x+y\le\dfrac A2+\dfrac A3<A\),还不如只选 \(A\)

再考虑三个数的情况。类似地,设选出的数为 \(x<y<z\)

结论:(i) \(z=A\),或 (ii) \((z,y,z)=\left(\dfrac A2,\dfrac A3,\dfrac A5\right)\)。证明与上面类似。

讨论这两种情况取 max。对于情况 (i),选 \(z=A\) 之后把 \(A\) 的所有因数去掉,再按选两个数的方法选 \(x,y\) 即可。

Submission #344419061 - Codeforces

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

相关文章:

  • WPF多语言实现
  • 16 倍性能提升,成本降低 98%! 解读 SLS 向量索引架构升级改造
  • unity设置外置文件,运行读取文件获取地址
  • CF981F Round Marriage
  • macOS直接使用pip安装报错
  • 2025 年最新螺旋地桩厂家推荐排行榜:聚焦光伏大棚等场景,甄选优质实力企业桩尖/大棚/组合/地螺丝螺旋地桩厂家推荐
  • CodeForces-1620D Exact Change
  • 2025 年蒸发器制造商最新推荐排行榜:聚焦节能环保领域,精选废水 / 多效 / 低温等类型设备实力品牌(TOP6)
  • K8S控制器压测调参
  • 第六周第四天6.4
  • Wireshark抓包教程:JSON和HTTPS抓取
  • 2025 年电子万能试验机生产厂家最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • 禁用内核模块,是否需要执行脚本 $ sudo update-initramfs -u $ sudo update-grub ? - 详解
  • Spring AI Alibaba Admin 正式开源!!
  • snack4-jsonpath v4.0.2 发布
  • 2025 年东莞钢结构厂房施工公司最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • Python 字符串和 数字(int、float、Decimal、Fraction 等) 的一些使用技巧
  • Python 类、对象、继承、方法 的一些使用技巧
  • Python 列表、字典、集合、生成器、迭代器 的一些使用技巧
  • 上海AI短视频获客企业口碑榜:技术实力、服务案例及市场覆盖率的深度解析
  • 【为美好CTF献上祝福】杂项笔记
  • 权威调研榜单:扬州公考笔试机构TOP3榜单好评深度解析
  • PyOCD使用指南
  • 嵌入式主板全景解析:从选型到趋势,读懂工业智能的核心载体
  • 2025 年唐山油漆生产厂家最新推荐榜单:精选优质企业,解析专业品牌选购指南唐山油漆批发/唐山油漆生产公司推荐
  • vscode创建快捷代码块,同时配置vue2和vue3的快捷代码块
  • DolphinScheduler依赖机制、Open-Falcon告警推送与监控的优化实践
  • Tailwind CSS 使用入门
  • 2025 年托管班加盟品牌最新推荐排行榜:聚焦国内优质机构,为投资者精选靠谱加盟项目托管班机构加盟/儿童托管班中心加盟/课后托管班加盟/小学托管班加盟连锁推荐
  • 终于能打出生僻字了!麒麟系统搜狗输入法完整安装指南 - 实践