[OII 2025] 双色金字塔 题解

FFTotoro · 2025-11-18 15:04:29 · 题解

暴力预处理出第 0\sim 2 层所有立方体的颜色，观察到第 2 层里黑色立方体构成的图案必然形如“若干条不交的对角线”。证明可以考虑暴搜小规模底座，从而说明在第 2 层，以下情况不存在（0 表示白色，1 表示黑色）：

• 11  1
    1

  ：同一行 / 列连续的两个 1；

• 101
  010

  ：另一种两对角线相交的情况。

若查询 0\sim 2 层，直接输出表中预处理的答案；否则尝试查询是否有一条第 2 层的黑色对角线可以让该位置成为黑色（在对角线都不交的情况下，一条长度为 l 的对角线往上叠一层的结果是一条长度为 l-1 的对角线），具体地在一开始预处理出所有对角线，询问时可以借助 upper_bound 快速定位可能对应的对角线，或再通过一些预处理做到线性。

时间复杂度 O(N^2+Q\log N) 或 O(N^2+Q)，取决于实现。

考场代码写得比较难看就不放了，有需要可以私信。