题目传送门

解析

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

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

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

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

将一个字符串

P

的每个字符入栈：

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

Code

CPP

#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记录

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

文章操作

题目传送门

解析

Code

相关推荐

评论

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