QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2025-12-12 23:58:45

Last updated: 2025-12-12 23:58:48

Back to Problem

题解

我们先把目标串 $T'$ 直接加在开头,问题变成删除掉一个环(这个环也就是反过来的 $T'$ 加上原来的 $T$)。

如果这个环绕原点的圈数非零,则显然无解。否则一定存在一个凸出来的部分凹进去后不经过原点,我们把让这部分凹进去,就能删除两个操作,不断重复直到删空即可。例如 $\texttt{NEEEEES}$ 凹进去后可以是 $\texttt{EEEEENS}$,那么我们就能删掉 $\texttt{NS}$,

证明: 如果有连续两个操作是 $\texttt{NS},\texttt{SN},\texttt{EW},\texttt{WE}$ 中的一个,则已经满足条件。 若路径上有一个点 $(x,y)$ 满足 $|x|\ge 2$ 或 $|y|\ge 2$,不妨设 $y\ge 2$,那么显然能找到一段形如 $\texttt{NEEES}$ 或 $\texttt{NWWWS}$ 的操作,且凹进去后仍然满足 $y\ge 1$,因此满足条件。 否则,若路径非空,则只能是在原点周围绕圈,显然无解。

Comments

No comments yet.