H. 避免分裂 详细题解

题目核心理解

生物初始只有细胞 $(0,0)$。 细胞 $(a,b)$ 可以分裂，分裂后会消失，并生成 $(a+1,b)$ 和 $(a,b+1)$，分裂只能在两个新细胞都不存在时进行。

给定若干禁止细胞，你需要判断：是否存在一种分裂方式，使得生物最终不包含任何禁止细胞。

核心思路

1. 关键性质

• 分裂顺序可以重新排列，我们只需要按对角线 $z = x + y$ 从小到大处理。
• 每一层的细胞数量只会传递到下一层，不会回头。
• 合法状态永远只有两种形态：
  1. $\boldsymbol{[\dots, 1, 2, 2, \dots, 2, 1, \dots]}$（两端 1，中间连续 2）
  2. $\boldsymbol{[\dots, 2, 2, \dots]}$（特殊情况）
• 一旦出现数字 3，过程永远无法结束，直接输出 NO。
• 禁止细胞不能击中中间的 2，否则会生成 3。

2. 判定规则

• 若禁止点落在中间 2 → 输出 NO
• 若某一层生成 3 → 输出 NO
• 若状态最终归零 → 输出 YES
• 只需维护：左 1 位置 $L$、右 1 位置 $R$、是否为特殊 $(2,2)$ 状态

算法流程

1. 将所有禁止细胞按对角线和 $z = x + y$ 分组排序。
2. 从 $z=0$ 开始逐层处理：
   • 检查当前对角线是否有禁止点击中中间 2。
   • 根据禁止点是否击中左右两端的 1，更新下一层的 $L$ 和 $R$。
   • 若出现 3，输出 NO。
3. 若状态归零，输出 YES。

公式与复杂度分析

对角线定义：

数量传递规则：

复杂度

• 排序：$O(n\log n)$
• 逐层处理：$O(n)$
• 总时间复杂度：$O(n\log n)$

可轻松处理：

• $t \le 10^4$
• $\sum n \le 10^6$
• $2$ 秒时限