AtCoder Beginner Contest 454 D 题解

题目大意

(xx) <=> xx，那么 \(A\) 是否能转化成 \(B\) ？

注意到题目中有 字串 一词，我们便可以发现：

• (xx) 能变成 xx
• (xxx) 只能变成 ((xx)x)

于是我们的主要思路是“规范化”，看“规范化”的字符串是否一样

A串=>A'
B串=>B'
如果A'=B'
那么A串=B串了。

思考

首先考虑暴力，即：

while (有`(xx)`)(xx) = xx

这样的代码在下数据会退化成 \(O(n^2)\)

((((((((((((xx))))))))))))

所以我们考虑处理括号串的通用方法：stack （栈）

栈优化

我们用一个 string 来代表栈

遍历字符串，将字符逐个压入一个栈。

每当栈顶的四个字符恰好组成 (xx) 时，立即将其替换为 xx。

重复此过程直到字符串末尾。

Code

string res;
for (char c : s)
{res.push_back(c);if (res.size() >= 4){int n = res.size();if (res[n - 4] == '(' && res[n - 3] == 'x' &&res[n - 2] == 'x' && res[n - 1] == ')'){res.pop_back(); // ')'res.pop_back(); // 'x'res.pop_back(); // 'x'res.pop_back(); // '('res.push_back('x');res.push_back('x');}}
}
return res;

给个赞把