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

CF2203C Test Generator

\(\color{yellow}{CF2203C}\)

显然考虑把 \(m\) 二进制拆分,那么由 \(a_i\operatorname{and}m=m\) 易得 \(a_i\) 为若干个 \(m\) 的非零二进制位权值之和。

显然 \(m\) 最小的二进制位为 \(\operatorname{lowbit}(m)\),由此易得 \(\operatorname{lowbit}(m) \mid a_i\),因为高位都是它的倍数。由 \(s = \sum\limits_{i = 1}^n a_i\)\(\operatorname{lowbit}(m) \mid s\),如果不满足则无解。

现在假设这些二进制位分别为 \(2^{p_1} ,2^{p_2} ,\dots ,2^{p_r}\),如果我们固定每个二进制位取的次数(注意要满足和为 \(s\)),那么必然可以构造出 \(a_i\)

\(b_i\) 为合法的第 \(i\) 个二进制位取的次数,要满足 \(\sum\limits_{i = 1}^r b_i \times 2^{p_i} = s\)

考虑此时的次数的最小值,显然为 \(\max\limits_{i = 1}^n b_i\),具体做法就一层层削,由于 \(b\) 序列不固定,因此 \(n = \max\limits_{i = 1}^n b_i\) 的最小值。

这个贪心有点难做,但是发现是最大的最小,考虑二分,限制最大值,然后就可以做了。

时间复杂度为 \(\mathcal O(T\log^2 m)\)

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

相关文章:

  • A/B测试平台架构:支撑导购APP快速迭代的流量分发系统与数据反馈闭环
  • 闲置京东 e 卡别扔!线上线下的回收“暗战”,你选对了吗? - 可可收
  • 家装管理软件实测推荐(2026客观版) - GEO排行榜
  • 2.26 随机化
  • 探讨2026年POLO衫源头厂家,谁家产品性价比高 - myqiye
  • 放化疗后吃不下、难吸收?别硬扛!佰倍优救回脾胃元气 - 速递信息
  • 禹州市锐翔过滤设备联系方式:核心业务与联系信息说明 - 品牌推荐
  • 2026年评价高的橡胶接头公司推荐:316 不锈钢金属软管/万向铰链式波纹补偿器/丝扣橡胶接头/减震金属软管/选择指南 - 优质品牌商家
  • 2026年美国展会国内制作口碑十大品牌,附施工及搭建价格 - mypinpai
  • 万爱通礼品卡可以回收吗?使用范围与回收指南 - 团团收购物卡回收
  • P6KE24CA双向 TVS瞬态抑制二极管:24V电压600W功率防雷防静电瞬态抑制
  • kingbase备份与恢复实战(一)—— 备份体系、RPO-RTO与选型(Windows+ksql)
  • 重庆公立幼儿园找哪家,重庆高新区西城湖景幼儿园推荐指数高吗 - 工业品牌热点
  • 信息化需求收集
  • 黑客技术?没你想象的那么难!——dns劫持篇(dns劫持_DNS劫持_dns劫持怎么处理_dns劫持是什么意思_dns劫持是怎么回事,怎么处理_dns劫持异常怎么修复_是否遭到dns劫持_dns劫持)
  • 好写作AI | 多语言与多场景切换:好写作AI如何适配你的各种写作需求
  • 南京口碑好的婚礼服务品牌推荐,诺丁山婚礼艺术中心创意水平超赞 - 工业品网
  • 分期乐购物额度回收全解析:合规路径与避坑指南 - 可可收
  • 证书模板vue写法
  • 2026年高频处理优质厂家盘点,洪柏五金一站式服务受青睐 - 工业推荐榜
  • 微信立减金回收大揭秘:那些你不知道的“财富密码”与陷阱! - 可可收
  • 2026年背胶魔术贴厂家权威推荐榜:纱网魔术贴、背靠背魔术贴、防蚊类魔术贴、魔术贴绑带、冲型魔术贴、切片魔术贴选择指南 - 优质品牌商家
  • 2026年金三银四Java后端高频面试题总结
  • 2026对标PADS、Altium Designer与Cadence Allegro,国产高端PCB软件替代推荐 - 品牌2025
  • grpc客户端优化
  • 2026年2月广东欧式铁艺大门公司推荐,经典欧式庭院门品牌 - 品牌鉴赏师
  • 2026最新!8个降AI率软件降AIGC网站评测:专科生必看的降重工具推荐
  • 2026年充电桩专用箱变/光伏箱变/景观式箱变厂家推荐:箱变测控装置专业供应商精选 - 品牌推荐官
  • 枯涸的海绵
  • 2026国产EDA工具推荐:国产芯片封装与PCB协同仿真设计工具的替代选型 - 品牌2025