CF923D Picking Strings
当变化规则不好分析的时候可以考虑自己随便模拟一下变化过程，总结浓缩出一些等价且更简单的变化规则。
尝试推出几个比较简单的变化关系：
-
\(\texttt{B}\rightarrow\texttt{AC}\rightarrow\texttt{AAB}\rightarrow\texttt{AAAC}\rightarrow\texttt{C}\rightarrow\texttt{AB}\rightarrow\texttt{AAC}\rightarrow\texttt{AAAB}\rightarrow\texttt{B}\)，这说明 \(\texttt{B}\) 和 \(\texttt{C}\) 是等价的。
-
\(\texttt{A}\rightarrow\texttt{BB}\)，这说明 \(\texttt{A}\) 可以被替换为 \(\texttt{BB}\)。
-
\(\texttt{B}\rightarrow\texttt{AB}\rightarrow\texttt{AAB}\rightarrow\texttt{AAAB}\rightarrow\texttt{B}\)，这说明 \(\texttt{B}\) 和 \(\texttt{AB}\) 等价，即一个 \(\texttt{B}\) 可以随意增减前面紧接着的 \(\texttt{A}\)。
现在有了三条简化的规则，就可以开始分析如何判断。
-
由规则 \(1\)，可以将 \(S\) 和 \(T\) 中的 \(\texttt{C}\) 全部换成 \(\texttt{B}\)。变成了 \(A\) 和 \(B\) 组成的串。
-
由规则 \(3\)，后缀的连续 \(\texttt{A}\) 无法增加，故 \(S\) 中的后缀连续 \(\texttt{A}\) 应该不多于 \(T\) 中的后缀连续 \(\texttt{A}\)。
-
如果 \(S\) 后缀的连续 \(\texttt{A}\) 和 \(T\) 的后缀连续 \(\texttt{A}\) 数量之差不是 \(3\) 的倍数，将多出的部分替换成 \(\texttt{BB}\)。
-
由规则 \(2\)、\(3\)，\(\texttt{B}\) 会两个两个地增加或不变，故 \(S\) 中 \(\texttt{B}\) 的数量应该不多于 \(T\) 中 \(\texttt{B}\) 的数量，且差值为偶数。
-
如果 \(S\) 中全是 \(\texttt{A}\)，\(T\) 中有 \(\texttt{B}\) 但后缀连续 \(\texttt{A}\) 的数量和 \(S\) 的长度相等则不行。
上文解法参考洛谷题解。
标签：总结,texttt,BB,后缀,练习,AB,规则,20230723,rightarrow From： https://www.cnblogs.com/dks-and-xiao-yu/p/17575373.html