AABB

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

Description

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).

Inspired by this observation, Jamie created a simple game. You are given two strings: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:
Add the letter A to the end of the string.
Reverse the string and then add the letter B to the end of the string.
Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

Input

-
The length of initial will be between 1 and 999, inclusive.
-
The length of target will be between 2 and 1000, inclusive.
-
target will be longer than initial.
-
Each character in initial and each character in target will be either 'A' or 'B'.

Output

Class:
ABBA
Method:
canObtain
Parameters:
string, string
Returns:
string
Method signature:
string canObtain(string initial, string target)
(be sure your method is public)

Sample Input

"BBBBABABBBBBBA"

"BBBBABABBABBBBBBABABBBBBBBBABAABBBAA"

Sample Output

"Possible"

HINT

题意

给你一个字符串和一个目标串，通过下列两种操作，问你能不能从字符串跑到目标串：

在后面加一个A

翻转后，再后面加一个B

题解：

倒推，倒着推的顺序是确定的

至于交换和删除，都用标记就好了，是O（1）的

代码

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

class ABBA{

public:

    int a[];

    int b[];

    string canObtain(string initial, string target){

        for(int i=;i<initial.size();i++)

            if(initial[i]=='A')

                a[i]=;

            else

                a[i]=;

        for(int i=;i<target.size();i++)

            if(target[i]=='A')

                b[i]=;

            else

                b[i]=;

        int l=,r=target.size()-;

        while(abs(l-r)+!=initial.size())

        {

            if(b[r]==)

            {

                if(l<r)

                    r--;

                else

                    r++;

                swap(l,r);

            }

            else

            {

                if(l<r)

                    r--;

                else

                    r++;

            }

        }

        int flag=;

        if(l<r)

        {

            for(int i=;i<initial.size();i++)

            {

                if(a[i]!=b[i+l])

                    break;

                if(i==initial.size()-)

                    flag=;

            }

        }

        else

        {

            for(int i=;i<initial.size();i++)

            {

                if(a[i]!=b[r-i])

                    break;

                if(i==initial.size()-)

                    flag=;

            }

        }

        if(flag)

            return "Possible";

        else

            return "Impossible";

    }

};

巴特西

TC SRM 663 div2 B AABB 逆推

AABB

题目连接

Description

HINT

最新文章

热门文章