Codeforces 1629 D. pecuriar movie preferences - simple thinking, palindrome strings

This way

The question ：

Here you are. n A string , Each string is no longer than 3, You can select a subsequence so that the string constructed by the subsequence is a palindrome string .

Answer key ：

You can know that if a string itself is a palindrome string , Then it can be constructed .
There are two remaining cases ：
1. The length is 2 when , Suppose the string is ab.
① Find out if there is a length of 2 And the string is ba.
② Find out that the back length is 3 The last two characters of are ba.
2. The length is 3 when , Suppose the string is abc：
① Find out that the back length is 2 And the string is ba
② Find out that the back length is 3 And the string is cba.
You can see that the length is zero 2 and 3 The difference in time is the second , So we can use hash to do this problem .
map[0] The length stored is 2 String
map[1] The length stored is 3 String
The length is 3 There are two cases when querying the string of , So we make the length 3 In the case of a string, insert both cases into map[1] Inside .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
map<int,int>mp[2];
char ss[N][5];
int main()
{
    
    char s[5];
    int t;
    scanf("%d",&t);
    while(t--){
    
        int n,f=0;
        scanf("%d",&n);
        mp[0].clear(),mp[1].clear();
        for(int i=1;i<=n;i++)scanf("%s",ss[i]);
        for(int i=n;i;i--){
    
            strcpy(s,ss[i]);
            if(f)break;
            int has=0,len=strlen(s);
            if(len==1)f=1;
            else if(len==2){
    
                if(s[0]==s[1])f=1;
                has=(int)s[0]*1000+(int)s[1];
                if(mp[0][has]||mp[1][has])f=1;
                has=(int)s[1]*1000+(int)s[0];
                mp[0][has]=1;
            }
            else{
    
                if(s[0]==s[2])f=1;
                has=(int)s[0]*1000+(int)s[1];
                if(mp[0][has])f=1;
                has=has*1000+(int)s[2];
                if(mp[1][has])f=1;
                has=((int)s[2]*1000+(int)s[1])*1000+(int)s[0];
                mp[1][has]=1;
                has=(int)s[2]*1000+(int)s[1];
                mp[1][has]=1;
            }
        }
        printf("%s\n",f?"YES":"NO");
    }
    return 0;
}