526互联

【AtCoder】Forbidden Pattern

发布时间 2023-04-27 19:11:45作者: alfalfa_w

题目链接

分析

首先考虑哪些串能被删空。下面只考虑长度为偶数的串。考虑这样一个（错误的）算法：从左往右依次加入串中的字符，然后能删则删。这个算法对于结尾为 A 的串一定能删空。对称地，开头为 B 的串也一定能被删空。

现在只需要考虑开头为 A 结尾为 B 的串。如果它能被删空，则一定存在最早的一个时刻，使得串的开头为 B 或结尾为 A。考虑把串表示成 A XX .. XX B 的形式，若某个 XX 为 AB 则肯定可以从开头/结尾一路删到它。

因此，如果能匹配下列模式串中至少一个，一个串就能被删空：

B XX XX .. X
X AB XX .. X
..
X XX .. AB X
X XX XX .. A

对于其它情况，每次删除可以等效于删除一个 XX，因此可以归纳出不能删空。

通过观察可以得到一个等价的条件：一个串能被删空，当且仅当它能被划分成若干个长为偶数的串，每个串的开头为 B 或结尾为 A。

接下来，我们可以考虑串 \(S\) 能否进行若干次删除得到 \(T\)。

如果 \(T_1=\texttt{A}\)，则可以找到 \(S\) 中的第一个位置 \(i\) 满足：

  • \(S_i=\texttt{A}\)
  • \(S_{1..i-1}\) 能被删空

然后去掉 \(S_{1..i}\) 和 \(T_1\)，继续做。

考虑反证，假设去掉之后不合法，而某个合法方案去掉的是 \(S_{1..j}\) (\(j>i\))。那么两种方案得到的 \(S\) 分别为：

XX .. XA XX ..
         XX ..

假设第二个串的某个前缀能被删空，那么第一个串右端点相同的前缀必然能被删空，矛盾。

如果 \(T_1=\texttt{B}\) 且 \(S_1=\texttt{A}\)，则可以找到最小的 \(2i\) 满足 \(S_{2i}=\texttt{A}\)，先删除 \(S_{1..2i}\)（通过上述的一个串被删空的等价条件得到）。

假设现在 \(S_1=\texttt{B}\)。如果 \(T_{1..2}=\texttt{BA}\)，可以找到最小的 \(2i\) 满足 \(S_{2i}=\texttt{A}\)，去掉 \(S_{1..2i}\) 和 \(T_{1..2}\)。这一定合法，且 \(\texttt{A}\) 的位置一定最靠左。

现在只剩 \(T_{1..2}=\texttt{BB}\) 的情况，我们找到最小的 \(2i\) 满足 \(S_{2i}=\texttt{B}\)，去掉 \(S_{1..2i-1}\) 和 \(T_1\)。根据上述的一个串被删空的等价条件，我们实际想要去掉 \(T_1\) 以及 \(S\) 中由如下三段字符串拼成的一个前缀：

  • 一段能被删空的串
  • B
  • 一段能被删空的串

满足 \(S\) 删掉这个前缀之后开头为 B。那么能观察到这个删法是最短的。