题解 : CF1628B Peculiar Movie Preferences

frzFRZ · 2025-08-05 19:21:48 · 题解

题目大意

题目传送门
有 T 次询问，每次询问有 N 个字符串，\lvert s \rvert \leqslant 3。\ 问是否能选出一些字符串，使它们按原序列的顺序拼接能形成一个回文字符串。

做法分析

STEP1

首先我们要能够判断一个字符串 s 是否为回文字符串。

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

由于题目条件：

得出，若三个字符串 s1，s2，s3 能构成回文串，则 s1，s3 也能构成回文串。

所以一个字符串 s 想要拼成一个回文串，只有如下几种情况：

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

代码

#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;
}