A. Space Navigation

统计四个方向的移动分别有多少,只保留走向目标向量对应方向的移动,判断是否可达。

B. New Colony

观察数据范围 $n,h_i\le 100$ 最多扔 $10^4$ 个石头就结束了,模拟 $\text O(n^2h)$ 即可。

C. Fence Painting

首先如果最后一次涂色不在 $b_i$ 里,肯定无解。

然后如果所有涂色不能满足将所有 $a_i$ 和 $b_i$ 不一样的位置覆盖为 $b_i$ ,则无解。

剩下的情况必定有解,一种构造方法:

对每种颜色 $c$ 预处理出来所有 $a_i$ 和 $b_i$ 不同且 $b_i=c$ 的位置集合 $S_c$ 。

首先确定最后一次涂色的位置 $pos_m$ :

若 $S_{c_m}$ 为空,则令 $pos_m$ 为任意一个 $b_i=c_m$ 的位置。

若 $S_{c_m}$ 不为空,则让 $pos_m$ 为 $S_{c_m}$ 中的任意一个,并将该位置移出 $S_{c_m}$ 。

然后时间倒序考虑,对于当前颜色 $c_j$ :

若 $S_{c_j}$ 为空,那么让 $pos_j=pos_m$ ,因为第 $m$ 次操作是最后一次,所以肯定会覆盖。

若 $S_{c_j}$ 不为空,则让 $pos_j$ 为 $S_{c_j}$ 中任意一个位置,然后将该位置移除 $S_{c_j}$ 即可。

D. AB Graph

首先奇数长度一定有解,在两个点之间来回跑就可以了。

考虑偶数长度,如果存在连接两个点的一组边类型相同,那么就一直在这两个点之间来回跑就可以了。

剩余的情况就是每一组边都是一条 $A$ 一条 $B$ ,那么对于 $n\ge 3$ 时很容易证明:

存在一个点 $x$ ,满足存在另两个点 $y,z$ ,边 $x\to y$ 和 $x\to z$ 的类型不同。


反证法:假设对于任意的点,所有的出边类型相同,入边类型相同,且两种边类型不同。

不妨设点 $x$ 的所有出边类型均为 $A$ ,也就是说对于其他任意的点的入边类型均为 $A$ (由假设性质)

那么对于任意另外两个点 $y,z$ 之间的边的类型,存在矛盾:

$z$ 的入边由上知类型为 $A$ ,则 $y\to z$ 是 $z$ 的入边,类型必须为 $A$。

$y$ 的出边与入边类型相反,则 $y\to z$ 是 $y$ 的出边,类型必须为 $B$ 。


因此只需要 $\text O(n)$ 枚举 $x$ ,$\text O(n)$ 扫描其他点,判断是否存在 $y,z$ 即可。

对于 $m = 4k$ 的情况,构造解形如 $x\ y\ x\ y\cdots x\ y\ x\ z\ x\ \cdots z\ x\ z\ x$ 即可。

对于 $m = 4k+2$ 的情况,构造解形如 $y\ x\ y\ x\ y\cdots x\ y\ x\ z\ x\ \cdots z\ x\ z\ x\ z$ 即可。

E. Sorting Books