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

Codeforces Round 1058 (Div. 2) A - D

我太菜了

A. MEX Partition

你可以发现最优的划分就是整个序列作为一个划分。因为需要 MEX 都相等,所以划分出来的子序列可以合并,合并完了就是原序列了,因此原序列的 MEX 即为答案。

读错题挂一发,火大。

B. Distinct Elements

先对 \(b\) 做差分,设为 \(d\)

你可以发现,如果 \(a _ i\)\(t\) 出现了,那它一定在 \([p,t](p \le t)\) 出现了。

因此 \(a _ i\) 的贡献是 \(i - m\),其中 \(m\) 代表 在 \(i\) 之前 \(a _ i\) 最后一次出现的位置,没有出现则为 \(0\)

现在我们需要 \(i - m = d _ i\),即 \(m = i - d _ i\),于是我们对每种 \(m\) 维护一个队列,每次取第 \(m\) 个队列的队首再将这个队首放进第 \(i\) 个队列里。

C. Reverse XOR

我们设 \(x\) 的二进制表示为 \(\overline{x _ 0 x _ 1 \dots x _ t}\),则 \(f(x) = \overline{x _ t x _ {t - 1} \dots x _ 0}\)\(x \oplus f(x) = \overline{(x _ 0 \oplus x _ t)(x _ 1 \oplus x _ {t - 1}) \dots (x _ t \oplus x _ 0)}\)

可以发现,\(x \oplus f(x)\) 是对称的,且若 \(t\) 为奇数,则 \(x _ {\frac{t}{2}} = 0\)

于是我们就可以枚举 \(n\) 包含前导 \(0\) 的长度,然后从两边往中间判断是否相等。

D. MAD Interactive Problem

差临门一脚就想出来,还是太菜了。

我们可以从 \(r = 2\) 开始查询 \([1,r](r \ge 2)\),如果返回值不为 \(0\),则说明 \(a _ r\) 一定是返回值,然后在之后的询问中就不问这个位置,这样我们用 \(2n - 1\) 次操作确定了 \(n\) 个位置。

然后,我们倒着再做一遍,查询 \([l,2n](l \le 2n - 1)\),若 \(a _ l\) 有值就不询问,这样我们就用 \(n - 1\) 次确定了所有位置,总次数 \(3n - 2\)

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

相关文章:

  • ACE-Step音乐生成大模型:开启AI音乐创作新纪元
  • c++操纵器std::ws
  • 2025 年计数包装机厂家最新推荐榜:聚焦高精度高效能品牌,助力企业智能化生产升级全自动/种子/五金/注塑件/纽扣计数包装机厂家推荐
  • JAVA工具包
  • 2025 年蝶阀厂家最新推荐:全金属 / 高压 / 美标 / 双偏心 / 三偏心等各类蝶阀优质厂家榜单及选择指南
  • 基于MATLAB的一维大地电磁反演程序实现
  • 2025 年国内发电机厂家最新推荐排行榜:汽油 / 柴油 / 10KW-200KW 多功率机型精选,全方位解读品牌实力助力精准选购
  • wqs二分学习笔记
  • Android系统中使用initrc脚本在开机时禁用selinux
  • 2025年10月氧化镁厂家最新推荐排行榜,轻烧氧化镁,重烧氧化镁,高纯氧化镁,活性氧化镁公司推荐!
  • Vector向量数据库对比
  • 2025 年最新推荐集装箱拖车供应厂家权威榜单:全方位解析优质企业实力,助力精准选择箱式 / 冷藏等拖车服务
  • 2025 年试验箱厂家最新推荐排行榜:聚焦高低温 / 恒温恒湿 / 冷热冲击等设备研发实力与 ISO 质量管控的标杆企业精选
  • 完整教程:PyTorch深度学习实战【12】之基于RNN的自然语言处理入门
  • IDA9.0中文版与相关插件安装详细教程
  • 2025 北京宽带安装公司最新推荐榜:专业口碑双优服务商汇总,企业家庭装机必看指南北京企业/北京无线/北京商务/北京商业/北京店铺宽带安装公司推荐
  • 2025年10月苹果仓源头厂家最新推荐榜单:专业仓储与高效配送的优质选择!
  • 2025年10月整平机厂家最新推荐排行榜,精密整平机,自动整平机,金属板材整平机公司推荐!
  • 2025 最新铝型材源头厂家推荐排行榜:优选企业深度解析,佛山龙头与新锐品牌选购指南
  • linux与window文件互传方式
  • 行业推荐:广州智建云工程管理软件/软件系统/软件App/软件平台/工程管理软件和验房系统公司获认可,专业方案成品质管控优选
  • 2025 聚合氯化铝厂家最新推荐榜:优质厂家选购指南与高口碑品牌全解析聚合氯化铝絮凝剂/水处理用聚合氯化铝/生产聚合氯化铝厂家推荐
  • 2025 年最新推荐!防水堵漏工程公司权威榜单重磅发布,覆盖地下室 / 污水池 / 伸缩缝等场景,帮业主避开乱象选靠谱企业
  • 2025 年最新留学机构权威最新推荐排行榜,深度解析顶尖机构服务特色与核心优势助力留学规划英国/澳洲/香港/美国/加拿大留学机构推荐
  • 2025 药包材辅导公司最新推荐榜:含 GMP 验证 / 质量管理体系 / 实验室装修等服务优质机构盘点公司推荐
  • 2025年10月氢氧化镁厂家最新推荐排行榜,阻燃剂氢氧化镁,环保型氢氧化镁,高纯度氢氧化镁公司推荐!
  • 2025年10月通风气楼厂家权威推荐:专业通风解决方案优选榜单
  • 多进程环境中解决 PHP 文件系统锁定问题指南
  • 2025年10月瑕疵检测设备厂家最新推荐排行榜,表面/薄膜/铝箔/陶瓷膜瑕疵在线检测,外观瑕疵检测机/仪公司推荐!
  • 2025年10月南通市婚纱摄影最新推荐榜单:创意拍摄与优质服务完美结合!