Codeforces1629D Peculiar Movie Preferences(STL)

Codeforces1629D Peculiar Movie Preferences(STL)

题目链接

题目大意就是给你N个字符串，问你是否存在一个子序列中字符串按顺序连接是回文串。

分析: 显然长度为1 一定存在，长度为2的 只需要存在一个与它相反的串即可，长度为3的，假设abc 那么检查是否存在cba 以及 abc+ba // cb+abc
注意位置关系以及某个字符串是否多次出现(WA死我了，一直没想到一个字符串可能多次出现)

 #include
#include
#include
#include
#include
#include
#include
#include 
#include 
#include 
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
templatevoid read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;

vectorG[111111];
maps;
  string ok[211111];
signed main(){

    ll t;
    read(t);
    while(t--)
    {
        ll n;
        read(n);
        ll now=0;
        s.clear();
        ll cnt=0;
        for(int i=1; i<=n; i++)
        {
            cin>>ok[i];
            if(!s[ok[i]])s[ok[i]]=(++cnt);
            G[s[ok[i]]].push_back(i);
        }

        for(int i=1; i<=n; i++)
        {
            if(ok[i].size()==1)
            {
                now=1;
                break;
            }
            if(ok[i].size()==2)
            {   if(ok[i][0]==ok[i][1]){
                 now=1;
                 break;
                }
                string p="";
                for(int j=ok[i].size()-1; j>=0; j--)
                {
                    p+=ok[i][j];
                } 
                if(!s[p])continue;
                if(G[s[p]].size())
                {
                    now=1;
                    break;
                }
            }
            if(ok[i].size()==3)
            {
                if(ok[i][0]==ok[i][2]){
                now=1;
                break;
                }
                //  abcdef
                //  cba     abc  cba
                //  cb  abc ba
                string p="";
                string q="";
                //   string l="";
                string r="";
                for(int j=ok[i].size()-1; j>=0; j--)
                {
                    p=p+ok[i][j]; //cba   abc   cba
                }
                for(int j=ok[i].size()-2; j>=0; j--)
                {
                    //abc
                    q=q+ok[i][j]; // ba
                }
                for(int j=ok[i].size()-1; j>=1; j--)
                {
                    r=r+ok[i][j];  // cb
                }
                if(G[s[p]].size()){
                    now=1;
                    break;
                }
                if(G[s[q]].size()){
                 ll fuck=G[s[q]].size();
                 fuck--;
                 ll pos=G[s[q]][fuck];
                 if(pos>i){
                    now=1;
                    break;
                 }

                }
                if(G[s[r]].size()){
                 ll pos=G[s[r]][0];
                 if(pos					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5710841.html