英语教学网站建设意见,标识设计网站,分销系统商城定制开发,网站内容质量Problem - D - Codeforces 米海打算去看电影。他只喜欢回文电影#xff0c;所以他想跳过一些(可能是零)场景#xff0c;让电影的其余部分变成回文。给你一个包含n个长度不超过3的非空字符串的列表#xff0c;代表Mihai的电影场景。如果s的子序列非空#xff0c;并且子序列中…Problem - D - Codeforces 米海打算去看电影。他只喜欢回文电影所以他想跳过一些(可能是零)场景让电影的其余部分变成回文。给你一个包含n个长度不超过3的非空字符串的列表代表Mihai的电影场景。如果s的子序列非空并且子序列中字符串的串联顺序为回文则称为awesome。你能帮Mihai检查是否至少有一个很棒的s子序列吗?一个回文是向后读和向前读一样的字符串例如字符串z aaa aba abccba是回文但是字符串codeforces reality ab不是。序列A是非空序列b的非空子序列如果A可以通过删除几个(可能为0butnotal) eleents。输入输入的第一行包含一个整数t (1 t 100)测试用例的数量。测试用例的描述如下。每个测试用例的第一行包含一个整数n (1 n 105)——电影中的场景数。然后是n行第i行包含一个长度不超过3的非空字符串s由小写拉丁字母组成。它保证所有测试用例的n和不超过105。输出对于每个测试用例如果存在一个很棒的s子序列则打印“YES”否则打印“NO”(不区分大小写)。
Example
input
Copy 6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab
output
Copy
YES
NO
NO
YES
YES
NO
题解: 这题思路并不难想,记录每个串的前缀即可,看后来的串整个反转或后缀反转.是否出现过即可
但是有一个很大的坑点,就是需要两个map来记录
为什么?
由于我们会记录前缀,长度为3时记录(01,012),前缀为0时不需要记录的,因为如果出现单个字母,则一定成立
长度为2时记录(01),理由同上
但是我们在询问反转后缀时会有这几种情况
长度为2时,询问整个反转(10)是否出现过,没什么问题
长度为3时,询问整个反转(210)是否出现过,也没什么问题
关键是
长度为3时,询问反转(21),肯能会出现与记录长度为3时(01)向匹配
类似abc dba,尽管前后缀相配,但却不对的
所以用两个map记录
记得特判首位相同的情况
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
#includeset
#includecstdio
using namespace std;
//#define int long long
const int N 2e5 10;
typedef pairint, int PII;
typedef long long ll;
void solve()
{int n;cin n;int ff 0;mapstring,int a;mapstring,int b;for(int i 1;i n;i){string s;cin s;string p(s),q(s);q.erase(0,1);reverse(q.begin(),q.end());reverse(p.begin(),p.end());if(a[q]||a[p]||b[p])ff 1;if(s.front() s.back() || s.size() 1)ff 1;a[s] 1;s.erase(s.size()-1,1);b[s] 1;}if(ff){cout YES\n;}else{cout NO\n;}
}//1 2 4
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t 1;
// cin t;
scanf(%d,t);while (t--) {solve();}
}
//1 1 1 0 1//1 1 1 0 1
//1 1 1 0 1
//1 1 1 0 1
//0 1 1 1 1
//0 1 1 1 1
