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

Dual_Ego · 2025-07-24 11:12:34 · 题解

题目传送门

解析

观察题目，不难发现以下规则：

1. 设字符串 P ,如果 P 是两个相同的字母，则 P 为“好单词”。
2. 设字符串 P,Q，若 P,Q 均为“好单词”,则字符串 PQ 和字符串 QP 为“好单词”。
3. 设字符串 P，若 P 为“好单词”，则字符串APA或BPB为“好单词”。

（因为如果相同字符的弧线不相交，这些弧线要么并列，要么一个弧在一个弧的上方或下方。）

这些规则可以构造出任何一个“好单词”，我们可以根据这些规则和性质推断出本题做法是栈。（而不是看标签）

将一个字符串 P 的每个字符入栈：

• 当出现两个相同字符时，根据规则一，这是一个“好单词”，根据栈的性质和规则二三，接下来无论入栈什么字符，都不会使这个“好单词”变坏，所以直接将这两个字符出栈。
• 因为每次入栈时，我们都会判断或出栈，所以一个字符入栈时，可以确定，这个字符的入栈前栈中没有“好单词”，因此如果已经将字符全部入栈，而栈中没有没出栈的字符，说明这是一个“好单词”，反之，则不是。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
string s[114];
int cheak(string a){
    int len=a.size(),cnt=0;
    char x[N];//栈 
    for(int i=0;i<len;i++){
        x[++cnt]=a[i];
        if(cnt>1){
            if(x[cnt]==x[cnt-1]) cnt-=2;//出栈
        }
    }
    if(cnt>0) return 0;//坏单词
    else return 1;//好单词
}
int main(){
    cin >> n;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        ans+=cheak(s[i]);//如果是好单词，+1，否则+0
    }
    cout << ans;
    return 0;
}

AC记录