QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: yangzichen1203

Posted at: 2026-07-21 16:17:11

Last updated: 2026-07-21 16:43:57

Back to Problem

New Editorial for Problem #857

结论题。

发现操作是可逆的,考虑从 $A,B$ 到达一个中间状态 $M$,然后反转 $B\to M$ 得到 $A\to M\to B$。

直接给出正确的构造:

设置任意点为根,对节点按深度从大到小考虑,每次尝试把一个物体移动到该节点,然后将该节点状态固定,并考虑下一个节点。

每次尝试时先将每个物体向远离节点的方向移动一步,再寻找是否存在一个物体能移动到节点,可以证明这样做是充要的。

发现这样做完后一定会达到字典序最大的一个可达状态,判断两个中间状态是否相同即可。

每次的操作次数最多为 $2n^2$,一共不超过 $4n^2$,可以通过。

AC 记录:https://qoj.ac/submission/2649369

Comments

No comments yet.