D. Peculiar Movie Preferences(思维 + 一个坑)
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