题解 AT2059 【[AGC005A] STring】

· · 题解

提供几种不同的方法。

思路：从输入的字符串头扫到字符串尾，如果扫到的字符为 \texttt{T} 且上一个字符为 \texttt{S}，就将这两个字符删掉。

那怎么处理删除操作呢？

有三四种想法：

1.我会栈！我们可以使用栈来记录前面还有多少个可用字符。如果扫到 \texttt{T} 且栈顶为 \texttt{S} 就把栈顶弹出，否则就把该字符加入栈。最后栈中剩下的字符数量就是答案。考虑到可以统计删掉了多少个数，再用总数减去就是答案，且栈中最后剩下的字符一定是形如 \texttt{TT...TTSS...S} 的字符串，则可以统计栈中还有多少 \texttt{S} ，这样可以节省空间。

2.我会链表！我们可以使用链表，首先建一个数组pre[]表示每个字符的前一个字符的编号。如果扫到 \texttt{T} 且pre[i]为 \texttt{S} ，就将pre[i+1]修改为pre[pre[i]]。最后剩下的字符数量就是答案。

3.我会vector！直接使用vector中自带的erase就好了。

4.我会平衡树！只要你愿意用，没人拦你。

鉴于此题其他题解全都是使用栈来解决此题（虽然栈确实是解决此类问题最经典的方法），我的代码使用的是链表。

#include<bits/stdc++.h>
using namespace std;
int pre[200005],ans;
string s;
int main(){
    cin>>s;
    int l=s.size();
    for(int i=1;i<l;i++)
        pre[i]=i-1;
    for(int i=1;i<l;i++)
        if(s[pre[i]]=='S'&&s[i]=='T')pre[i+1]=pre[pre[i]],ans+=2;
    printf("%d",l-ans);
    return 0;
}