AtCoder -arc224_e ABC|AB|A 题解

Solution

对于一个字符串 \(S\)，设最优解中被删除的字符按原顺序依次拼接得到的字符串 \(T\) 为 \(S\) 的最优导出串。

我们先考虑最优导出串必然满足的结构。将每个删除的字符串（e.g. \(\texttt{A/AB/ABC}\)）看作一个结点。那么会形成一个森林。例如：

\[\texttt{(A(AB)B(ABC)C)(A(ABC)B(A\dots} \]

不难看出以下性质：

1. 每个点对应原串中一个连续段，该连续段中首尾字符都属于该点
2. 每个点恰好包含 \(1\) 个 \(\texttt{A}\)，位于开头
3. 从前向后遍历最优导出串的过程等价于按欧拉序分别遍历每棵树
4. 由于 \(\texttt{A,AB,ABC}\) 中前一个是后一个的前缀，栈顶结点可以在任何时刻合法弹出

考虑使用栈维护在最优导出串上遍历的过程。栈中依次保存当前链上各个节点已经被遍历到的前缀。调整法易证匹配过程满足贪心性质：每新增一个字符，从当前节点开始尝试加入，若失败就弹栈，尝试父节点，以此类推。

现在转而考虑原串。显然原串就是在最优导出串的不同树之间插入了若干个失配的 \(\texttt{B/C}\)。每个失配字符会把原串分成前后独立的两部分，此时直接清栈即可。结合性质 4 可知答案即为失配字符数量。

由以上论证可知，对于任意原串 \(S\)，最优导出串的每个字符一定会被删除，正确性自然得到保证。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],ans,n,t;
char s[N];
// 用数字代替所有可能出现的字符串前缀
// 1: A
// 2: AB
// 3: ABC
void solve(){cin>>s;n=strlen(s),t=ans=0;for(int i=0;i<n;++i) switch(s[i]){case 'A':a[++t]=1;break;case 'B':while(t&&a[t]!=1) --t;if(t&&a[t]==1) a[t]=2;else t=0,++ans;break;case 'C':while(t&&a[t]!=2) --t;if(t&&a[t]==2) --t;else t=0,++ans;}cout<<ans<<'\n';
}
signed main(){int T;cin>>T;while(T--) solve();return 0;
}