题解 : CF1628B Peculiar Movie Preferences

题目大意

T

次询问，每次询问有

N

个字符串，

\lvert s \rvert \leqslant 3

。
问是否能选出一些字符串，使它们按原序列的顺序拼接能形成一个回文字符串。

做法分析

STEP1

首先我们要能够判断一个字符串

s

是否为回文字符串。

CPP

bool check(string a) //判断回文
{
	int len=a.length();
	for(int i=0;i<len/2;i++)
		if(a[i]!=a[len-i-1]) return 0;
	return 1;
}

此处不做过多赘述。

STEP2

由于题目条件：

\forall s,\lvert s \rvert \leqslant 3

得出，若三个字符串

s1

，

s2

，

s3

能构成回文串，则

s1

，

s3

也能构成回文串。

所以一个字符串

s

想要拼成一个回文串，只有如下几种情况：

$s$ 本身为回文串。
$\lvert s \rvert = 2$ ，要么 $s$ 的倒序串之前出现过，要么前面出现过的字符串中前两位是 $s$ 的倒序串。
$\lvert s \rvert = 2$ ，要么 $s$ 后两位的倒序串之前出现过，要么 $s$ 前两位的倒序串在它之后能找到。

我们只需要用储存下之前出现过的字符串的倒序串，在判断和当前字符串匹配的字符串是否存在就可以了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
map<string,bool> m;
bool check(string a) //判断回文
{
	int len=a.length();
	for(int i=0;i<len/2;i++)
		if(a[i]!=a[len-i-1]) return 0;
	return 1;
}
string rev(string a) //翻转字符串,求倒序串
{
	int len=a.length();
	string b="";
	for(int i=len-1;i>=0;i--) b+=a[i];
	return b;
}
void solve()
{
	bool flot=0;
	m.clear(); //数据千万条，清空第一条。多测不清空，暴零两行泪
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		if(flot) continue;
		if(check(s)==true||m[s]==true) flot=1; // s 已经是回文或之前有和 s 匹配的字符串
		if(s.size()==2) //长度为2
		{
			for(int i=0;i<26;i++) //枚举连接字母( a ~ z )
			{
				string ss="";
				ss+=i+'a';ss+=s;
				if(m.count(ss)) flot=1; //判断是否存在
			}
		}
		if(s.size()==3) //长度为3
		{
			string ss="";
			ss+=s[1];ss+=s[2]; //第一个字符为连接字符
			if(m.count(ss)) flot=1;
		}
		m[rev(s)]=true; //存储该字符串的翻转字符
	}
	cout<<(flot?"YES\n":"NO\n");
	return ;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

题解 : CF1628B Peculiar Movie Preferences

文章操作

题目大意

做法分析

STEP1

STEP2

代码

相关推荐

评论

题解 : CF1628B Peculiar Movie Preferences