题解：CF2155C The Ancient Wizards' Capes

· · 题解

此题解由 codeforces 官方题解翻译而来。

关键性质

假设哈利的列表至少对应一种斗篷安排。主要结论是：列表中任意两个连续值的差最多为 1。

分析

当哈利从位置 i 走到位置 i + 1 时，巫师 1 到 i - 1 以及 i + 2 到 n 的可见性不受影响。对于巫师 i 和 i + 1，存在四种可能情况：

情况 巫师 i 巫师 i+1 a_{i + 1} - a_i 说明
1 左侧 左侧 +1 巫师 i+1 变得可见，巫师 i 仍然可见
2 右侧 右侧 -1 巫师 i+1 保持可见，巫师 i 变得不可见
3 左侧 右侧 0 两个巫师都保持可见
4 右侧 左侧 0 巫师 i+1 变得可见，巫师 i 变得不可见

结论

这决定了整个斗篷安排的一种唯一可能性（可能无效），该可能性仅基于巫师 1 披斗篷的方式，前提是对于所有 1 \leq i < n，满足 |a_{i+1} - a_i| < 2。

因此，巫师斗篷的安排最多有两种可能。我们可以构建这两种安排，并检查它们是否与哈利的列表一致。

算法步骤

  1. 检查相邻 a_i 的差值是否都 \leq 1，如果不是直接输出 0。
  2. 构建两种可能的斗篷安排：
    • 方案1：巫师 1 披在左侧。
    • 方案2：巫师 1 披在右侧。
  3. 根据差值规则填充后续巫师的斗篷方向。
  4. 验证每种方案是否与完整列表一致。
  5. 输出有效方案的数量。

时间复杂度

注：本文由 deepseek 直接翻译，作者修改格式并检查错误。