「PA 2019 Final」Pionki 题解

核心思路

1. 移动方向约束分析

棋子只能从 $(i,j,k)$ 移动到 $(i+1,j,k)$、$(i,j+1,k)$ 或 $(i,j,k+1)$，这意味着：

• 移动是有向的，从坐标小的位置流向坐标大的位置
• 构成一个三维网格 DAG（有向无环图）

2. 流量守恒建模

定义每个单元格的净需求量：

$$d_{i,j,k} = a_{i,j,k} - b_{i,j,k}$$

• 如果 $d_{i,j,k} > 0$：该格需要流出棋子
• 如果 $d_{i,j,k} < 0$：该格需要流入棋子
• 如果 $d_{i,j,k} = 0$：该格棋子数正好

3. 前缀和条件

对于任意 $(x,y,z)$，定义三维前缀和：

$$S(x,y,z) = \sum_{i=1}^x \sum_{j=1}^y \sum_{k=1}^z d_{i,j,k} $$

关键性质：状态可达的充要条件是：

1. $S(A,B,C) = 0$（题目已保证）
2. 对所有 $1 \le x \le A, 1 \le y \le B, 1 \le z \le C$，有 $S(x,y,z) \ge 0$

4. 直观解释

• $S(x,y,z)$ 表示从 $(1,1,1)$ 到 $(x,y,z)$ 这个子长方体中，初始比目标多出的棋子数
• 由于棋子只能向坐标增大的方向移动，多出的棋子可以送到后面，但缺少的棋子无法从后面补充
• 因此任何前缀区域都不能缺棋子（即 $S(x,y,z) \ge 0$）

算法实现

1. 三维前缀和计算

按 $(i,j,k)$ 字典序递增计算：

$$S(i,j,k) = S(i-1,j,k) + S(i,j-1,k) + S(i,j,k-1) - S(i-1,j-1,k) - S(i-1,j,k-1) - S(i,j-1,k-1) + S(i-1,j-1,k-1) + d_{i,j,k} $$

2. 可行性检查

遍历所有 $(i,j,k)$，检查 $S(i,j,k) \ge 0$ 是否成立。

3. 复杂度分析

• 每个测试点：$O(A \times B \times C)$
• 由于 $B,C \le 6$，且 $\sum A \le 10000$，总复杂度可接受