CF81A Plug-in 题解

题意简述

给定一个字符串 $str$，去除其中重复的连续子串。

如果去除一些子串后又合成新的子串，这些重复的字串也要删除。

如样例 #2 就是如下得出的。

$\texttt{reallazy} \to \texttt{reaazy} \to \texttt{rezy}$

解题思路

我们可以用栈来实现。

我们首先将第一个字符压入栈中。

每次遇到与栈顶一样的字符，就将栈顶弹出，否则，将这个元素入栈。

最后，将所有元素从栈中弹出，用一个数组记录，倒序输出即可。

显然我用的是系统栈，但也许这道题用手写栈会更简单一些？

代码实现

#include<bits/stdc++.h>
using namespace std;
string str; char ans[1000005];
stack<char> st; int num;
int main() {
	cin>>str; st.push(str[0]);
	for(int i=1;i<str.size();i++) {
		if(!st.empty()&&st.top()==str[i]) st.pop();
		else st.push(str[i]);
	}
	while(!st.empty()) {
		ans[++num]=st.top();
		st.pop();
	}
	for(int i=num;i>=1;i--) printf("%c",ans[i]);
	return 0;
}
//code by TheCedar