题解：P13414 [COCI 2012/2013 #4] ESEJ

yisit · 2025-07-23 18:57:34 · 题解

[COCI 2012/2013 #4] ESEJ

来热乎水题了！！！

一道很好的思维题~

题意解释

将相同的字母连线，刚好连完且线和线之间不交叉就是好单词，统计好单词数量。
这个问题和括号匹配类似，即后出现的字母必须优先与最近的相同字母配对，也使用栈。根据标签可以知道。

算法思路

• 因为是两两配对，所以直接排除长度为奇数的。
• 遍历字符串，如果当前字母和栈顶一样，即配对成功，就弹出栈顶。
• 判断栈的长度。

代码

#include <iostream>
#include <stack>
using namespace std;

bool isGoodWord(const string &s) {
    if (s.size() % 2 != 0) return false;
    stack<char> st;
    for (char c : s) {
        if (!st.empty() && st.top() == c) st.pop();
        else st.push(c);
    }
    return st.empty();
}

int main() {
    int N, cnt = 0;
    cin >> N;
    while (N--) {
        string s;
        cin >> s;
        if (isGoodWord(s)) cnt++;
    }
    cout << cnt;
    return 0;
}