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

[CF 516 E] Drazil and His Happy Friends

A 侧有 \(n\) 个点,B 侧有 \(m\) 个点,从 \(0\) 开始标号。已知初始有若干黑点,其它都是白点。第 \(i\)\(i \ge 0\))时刻,若 A 的第 \(i \bmod n\) 个点和 B 的第 \(i \bmod m\) 个点中存在一个黑色的点,则两个点都会被染成黑色。问经过多少天之后可以变成黑色。

下文认为 \(n, m\) 同阶,\(b, g\) 同阶。

不妨 \(n, m\) 互质,否则拆分成 \(\gcd(n, m)\) 组问题。

特判 A 和 B 都没有黑点的无解情况。

不妨先考虑 A 侧全部染色的时间,则 B 侧同理。

对于一个 A 侧的白点 \(t\),若它的黑色来自黑点 \(s\)(可以在 A 侧或 B 侧),需要找到最小非负整数 \(k\),满足 \(s + km \equiv t \pmod n\),则在第 \(s + km\) 时刻后被染色(在 A 侧待一轮不转移不优)。

考虑二分:判断 \(v\) 时刻后能否全部染色。

对于每个 \(s \le v\),求出满足 \(s + k m \le v\) 的最大整数 \(k = k_1\)。把 \(s\) 也表示成 \(s \equiv k_0 m \pmod n\),则 \(\forall k_0 \le K \le k_0 + k_1\)\(K m \bmod n\) 会被染色。

对于 A 侧的 \(s > v\),初始是黑色,可以认为它是一个 \(k_1 = 0\) 的段,只能覆盖 \(k_0\) 一个位置。

只需判断这些区间是否在 \(\bmod n\) 意义下覆盖了 \(0 \sim n - 1\) 的所有 \(K\),即可判断 A 侧是否全被染色。

直接对区间排序可以做到 \(O(b \log n \log b)\)。但是 \(k_0\) 是确定的,预先对 \(s\) 排序可以省掉一个 \(\log b\),优化到 \(O(b \log n)\)

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

相关文章:

  • NVIDIA Triton服务器漏洞危机:攻击者可远程执行代码,AI模型最高权限告急
  • 2025-10-21
  • 个人骗分导论
  • Java三大特性
  • 高级程序设计第二次作业
  • 10月21日日记
  • home-assistant.-Adding integrations
  • Windows系统内存占用过高,且任务管理器找不到对应进程
  • NOIP 二十五
  • 理想婚姻
  • equal和hashcode
  • Ancestral Problem 题解
  • AWS IAM角色最佳实践:构建云安全的核心防线
  • 正睿 2025 NOIP 20连测 Day6
  • Hetao P5593 删 题解 [ 蓝 ] [ 线性 DP ] [ DFS 序 ] [ 虚树 ]
  • o(N^2)找出所有回文子串
  • 第二次高级程序作业
  • 大学生需要认真听课的肌肉记忆(注意力训练)
  • 初始人工智能和机器学习
  • 10/21
  • 蛋白表达技术概述
  • 二叉树的中序遍历- 递归原理 - MKT
  • 友链测试
  • 二叉树的中序遍历- 二叉树基本-递归 - MKT
  • 做了一个概率小游戏,没想到服务器被打爆被攻击了!原因竟然是他?真没想到...
  • 接下来的目标
  • 阿里云对象存储OSS之Java - Soul
  • 敬启,致那时的我
  • 后量子密码学技术与标准化进程解析
  • 10月21日