首页 > 其他 > 详细

CCPC2018-湖南全国邀请赛 G String Transformation

时间:2018-05-19 23:44:18      阅读:574      评论:0      收藏:0      [点我收藏+]

String Transformation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 36    Accepted Submission(s): 8


Problem Description
Bobo has a string S=s技术分享图片1技术分享图片s技术分享图片2技术分享图片s技术分享图片n技术分享图片技术分享图片 consists of letter `a`, `b` and `c`.
He can transform the string by inserting or deleting substrings `aa`, `bb` and `abab`.

Formally, A=u°w°v技术分享图片 (``°技术分享图片 ‘‘ denotes string concatenation) can be transformed into A技术分享图片技术分享图片=u°v技术分享图片 and vice versa where u技术分享图片 , v技术分享图片 are (possibly empty) strings and w{aa,bb,abab}技术分享图片 .

Given the target string T=t技术分享图片1技术分享图片t技术分享图片2技术分享图片t技术分享图片m技术分享图片技术分享图片 , determine if Bobo can transform the string S技术分享图片 into T技术分享图片 .
 

 

Input
The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains a string s技术分享图片1技术分享图片s技术分享图片2技术分享图片s技术分享图片n技术分享图片技术分享图片 .
The second line contains a string t技术分享图片1技术分享图片t技术分享图片2技术分享图片t技术分享图片m技术分享图片技术分享图片 .
 

 

Output
For each test case, print `Yes` if Bobo can. Print `No` otherwise.

## Constraint

* 1n,m10技术分享图片4技术分享图片技术分享图片
* s技术分享图片1技术分享图片,s技术分享图片2技术分享图片,,s技术分享图片n技术分享图片,t技术分享图片1技术分享图片,t技术分享图片2技术分享图片,,t技术分享图片m技术分享图片{a,b,c}技术分享图片
* The sum of n技术分享图片 and m技术分享图片 does not exceed 250,000技术分享图片 .
 

 

Sample Input
ab ba ac ca a ab
 

 

Sample Output
Yes No No
Hint
For the first sample, Bobo can transform as `ab => aababb => babb => ba`.
 

 

Source
 
     麻烦的模拟题,不管多麻烦的ababa的式子(不含c时)最终只会化成三种形式:a,b,ab(或ba),题目中插入删除abab的意义所在就是告诉我们ab能够转化成ba
    我的思路:将两个式子化解成最优。
eg:abaabcaacabc  化简 accabc,化简使用队列,边放进去边判,队末尾是a,要放的也是a,那就pop(a)
        ababaccbac      化简 accbac
技术分享图片

 

然后在从队首把他们取出来进行比较,特判一下ab和ba是一样的。
#include <iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<deque>
#define ll long long
using namespace std;
char a[10005];
char b[10005];
deque<int>q1,q2;
int main()
{
    while(cin>>a>>b)
    {
        while(!q1.empty ()) q1.pop_back();
        while(!q2.empty ()) q2.pop_back();
        int la=strlen(a);
        int lb=strlen(b);
        int c1=0;
        int c2=0;
        for(int i=0;i<la;i++)
        {
            if(a[i]==c)
            {
                q1.push_back(3);
                c1++;
            }
            else if(a[i]==a)
            {
                if(q1.empty ()) 
                {
                    q1.push_back(1);
                    continue;
                }
                if(q1.back()==1)
                {
                    q1.pop_back();
                }
                else if(q1.back()==2)
                {
                    if(i<la-1&&a[i+1]==b)
                    {
                        q1.pop_back();
                        i++;
                        if(q1.empty ()||q1.back ()!=1) 
                        {
                            q1.push_back (1);
                        }
                        else if(q1.back ()==1)
                        {
                            q1.pop_back();
                        }

                    }
                    else q1.push_back (1);
                }
                else q1.push_back (1);

            }
            else if(a[i]==b)
            {
                if(q1.empty ()) 
                {
                    q1.push_back(2);
                    continue;
                }
                if(q1.back()==2)
                {
                    q1.pop_back();
                }
                else if(q1.back()==1)
                {
                    if(i<la-1&&a[i+1]==a)
                    {
                        q1.pop_back();
                        i++;
                        if(q1.empty ()||q1.back ()!=2) 
                        {
                            q1.push_back (2);
                        }
                        else if(q1.back ()==2)
                        {
                            q1.pop_back();
                        }

                    }
                    else q1.push_back(2);
                }
                else q1.push_back(2);
            }
        }
        for(int i=0;i<lb;i++)
        {
            if(b[i]==c)
            {
                q2.push_back(3);
                c2++;
            }
            else if(b[i]==a)
            {
                if(q2.empty ()) 
                {
                    q2.push_back(1);
                    continue;
                }
                if(q2.back()==1)
                {
                    q2.pop_back();
                }
                else if(q2.back()==2)
                {
                    if(i<lb-1&&b[i+1]==b)
                    {
                        q2.pop_back();
                        i++;
                        if(q2.empty ()||q2.back ()!=1) 
                        {
                            q2.push_back (1);
                        }
                        else if(q2.back ()==1)
                        {
                            q2.pop_back();
                        }

                    }
                    else q2.push_back (1);
                }
                else q2.push_back (1);

            }
            else if(b[i]==b)
            {
                if(q2.empty ()) 
                {
                    q2.push_back(2);
                    continue;
                }
                if(q2.back()==2)
                {
                    q2.pop_back();
                }
                else if(q2.back()==1)
                {
                    if(i<lb-1&&b[i+1]==a)
                    {
                        q2.pop_back();
                        i++;
                        if(q2.empty ()||q2.back ()!=2) 
                        {
                            q2.push_back (2);
                        }
                        else if(q2.back ()==2)
                        {
                            q2.pop_back();
                        }
                    }
                    else q2.push_back(2);
                    
                }
                else q2.push_back(2);
            }
        }
        bool f=1;
        if(c1!=c2||q1.size()!=q2.size()) f=0;
        else
        {
            while(!q1.empty ())
            {
                if(q1.front() ==1&&q2.front() ==2)
                {
                    q1.pop_front ();
                    q2.pop_front ();
                    if(q1.empty ())
                    {
                        f=0;
                        break;
                    }
                    else if(q1.front() ==2&&q2.front() ==1)
                    {
                        q1.pop_front ();
                        q2.pop_front ();
                    }
                    else 
                    {
                        f=0;
                        break;
                    }
                }
                else if(q1.front() ==2&&q2.front() ==1)
                {
                    q1.pop_front ();
                    q2.pop_front ();
                    if(q1.empty ())
                    {
                        f=0;
                        break;
                    }
                    else if(q1.front() ==1&&q2.front() ==2)
                    {
                        q1.pop_front ();
                        q2.pop_front ();
                    }
                    else 
                    {
                        f=0;
                        break;
                    }
                }
                else if(q1.front()==q2.front ())
                {
                    q1.pop_front();
                    q2.pop_front();
                }
                else 
                {
                    f=0;
                    break;
                }
            }
        }
        if(f) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

 

 

CCPC2018-湖南全国邀请赛 G String Transformation

原文:https://www.cnblogs.com/caiyishuai/p/9062114.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!