专栏文章

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

yyisit
P13414题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioru9t5
此快照首次捕获于
2025/12/03 00:07
3 个月前
此快照最后确认于
2025/12/03 00:07
3 个月前
查看原文

[COCI 2012/2013 #4] ESEJ

来热乎水题了！！！
一道很好的思维题~

题意解释

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

算法思路

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

代码

CPP

#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...