福建建设工程交易中心网站外贸网站建设 公司价格

Problem - D - Codeforces

米海打算去看电影。他只喜欢回文电影，所以他想跳过一些(可能是零)场景，让电影的其余部分变成回文。给你一个包含n个长度不超过3的非空字符串的列表，代表Mihai的电影场景。如果s的子序列非空，并且子序列中字符串的串联顺序为回文，则称为awesome。你能帮Mihai检查是否至少有一个很棒的s子序列吗?一个回文是向后读和向前读一样的字符串，例如字符串"z"， "aaa"， "aba"， "abccba"是回文，但是字符串"codeforces"， "reality"， "ab"不是。序列A是非空序列b的非空子序列，如果A可以通过删除几个(可能为0，butnotal) 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记录

记得特判首位相同的情况

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<cstdio>
using namespace std;
//#define int long long
const int N = 2e5 + 10;
typedef pair<int, int> PII;
typedef long long ll;
void solve() 
{int n;cin >> n;int ff = 0;map<string,int >  a;map<string,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